My Project  debian-1:4.1.2-p1+ds-2
Public Member Functions | Private Attributes
KMatrix< K > Class Template Reference

#include <kmatrix.h>

Public Member Functions

 KMatrix ()
 
 KMatrix (const KMatrix &)
 
 KMatrix (int, int)
 
 ~KMatrix ()
 
void copy_delete (void)
 
void copy_new (int)
 
void copy_zero (void)
 
void copy_unit (int)
 
void copy_shallow (KMatrix &)
 
void copy_deep (const KMatrix &)
 
get (int, int) const
 
void set (int, int, const K &)
 
int row_is_zero (int) const
 
int column_is_zero (int) const
 
int column_pivot (int, int) const
 
int gausseliminate (void)
 
int rank (void) const
 
int solve (K **, int *)
 
multiply_row (int, const K &)
 
add_rows (int, int, const K &, const K &)
 
int swap_rows (int, int)
 
set_row_primitive (int)
 
int is_quadratic (void) const
 
int is_symmetric (void) const
 
determinant (void) const
 

Private Attributes

K * a
 
int rows
 
int cols
 

Detailed Description

template<class K>
class KMatrix< K >

Definition at line 41 of file kmatrix.h.

Constructor & Destructor Documentation

◆ KMatrix() [1/3]

template<class K >
KMatrix< K >::KMatrix
inline

Definition at line 234 of file kmatrix.h.

235 {
236  copy_zero( );
237 }
void copy_zero(void)
Definition: kmatrix.h:167

◆ KMatrix() [2/3]

template<class K >
KMatrix< K >::KMatrix ( const KMatrix< K > &  m)
inline

Definition at line 244 of file kmatrix.h.

245 {
246  copy_deep( m );
247 }
int m
Definition: cfEzgcd.cc:121
void copy_deep(const KMatrix &)
Definition: kmatrix.h:209

◆ KMatrix() [3/3]

template<class K >
KMatrix< K >::KMatrix ( int  r,
int  c 
)

Definition at line 254 of file kmatrix.h.

255 {
256  int n = r*c;
257 
258  copy_new( n );
259 
260  rows = r;
261  cols = c;
262 
263  for( int i=0; i<n; i++ )
264  {
265  a[i]=(K)0;
266  }
267 }
int i
Definition: cfEzgcd.cc:125
int cols
Definition: kmatrix.h:48
K * a
Definition: kmatrix.h:46
void copy_new(int)
Definition: kmatrix.h:119
int rows
Definition: kmatrix.h:47

◆ ~KMatrix()

template<class K >
KMatrix< K >::~KMatrix

Definition at line 274 of file kmatrix.h.

275 {
276  copy_delete( );
277 }
void copy_delete(void)
Definition: kmatrix.h:108

Member Function Documentation

◆ add_rows()

template<class K >
K KMatrix< K >::add_rows ( int  src,
int  dest,
const K &  factor_src,
const K &  factor_dest 
)

Definition at line 423 of file kmatrix.h.

425 {
426  #ifdef KMATRIX_DEBUG
427  test_row( src );
428  test_row( dest );
429  #endif
430 
431  int i;
432  int i_src = src*cols;
433  int i_dest = dest*cols;
434 
435  for( i=0; i<cols; i++,i_src++,i_dest++ )
436  {
437  a[i_dest] = a[i_src]*factor_src + a[i_dest]*factor_dest;
438  }
439 
440  return factor_dest;
441 }

◆ column_is_zero()

template<class K >
int KMatrix< K >::column_is_zero ( int  c) const

Definition at line 470 of file kmatrix.h.

471 {
472  #ifdef KMATRIX_DEBUG
473  test_col( c );
474  #endif
475 
476  for( int r=0; r<rows; r++ )
477  {
478  if( a[r*cols+c] != (K)0 ) return FALSE;
479  }
480  return TRUE;
481 }
#define TRUE
Definition: auxiliary.h:100
#define FALSE
Definition: auxiliary.h:96

◆ column_pivot()

template<class K >
int KMatrix< K >::column_pivot ( int  r0,
int  c 
) const

Definition at line 490 of file kmatrix.h.

491 {
492  #ifdef KMATRIX_DEBUG
493  test_row( r0 );
494  test_col( c );
495  #endif
496 
497  int r;
498  // find first nonzero entry in column c
499 
500  for( r=r0; r<rows && a[r*cols+c]==(K)0; r++ );
501 
502  if( r == rows )
503  {
504  // column is zero
505 
506  return -1;
507  }
508  else
509  {
510  double val = a[r*cols+c].complexity( );
511  double val_new = 0.0;
512  int pivot = r;
513 
514  for( ; r<rows; r++ )
515  {
516  if( a[r*cols+c] != (K)0 &&
517  ( val_new = a[r*cols+c].complexity( ) ) < val )
518  {
519  val = val_new;
520  pivot = r;
521  }
522  }
523  return pivot;
524  }
525 }
bool pivot(const matrix aMat, const int r1, const int r2, const int c1, const int c2, int *bestR, int *bestC, const ring R)
This code computes a score for each non-zero matrix entry in aMat[r1..r2, c1..c2].

◆ copy_deep()

template<class K >
void KMatrix< K >::copy_deep ( const KMatrix< K > &  m)
inline

Definition at line 209 of file kmatrix.h.

210 {
211  if( m.a == (K*)NULL )
212  {
213  copy_zero( );
214  }
215  else
216  {
217  int n=m.rows*m.cols;
218  copy_new( n );
219  rows = m.rows;
220  cols = m.cols;
221 
222  for( int i=0; i<n; i++ )
223  {
224  a[i] = m.a[i];
225  }
226  }
227 }
#define NULL
Definition: omList.c:12

◆ copy_delete()

template<class K >
void KMatrix< K >::copy_delete ( void  )
inline

Definition at line 108 of file kmatrix.h.

109 {
110  if( a != (K*)NULL && rows > 0 && cols > 0 ) delete [] a;
111  copy_zero( );
112 }

◆ copy_new()

template<class K >
void KMatrix< K >::copy_new ( int  k)
inline

Definition at line 119 of file kmatrix.h.

120 {
121  if( k > 0 )
122  {
123  a = new K[k];
124 
125  #ifndef SING_NDEBUG
126  if( a == (K*)NULL )
127  {
128  #ifdef KMATRIX_PRINT
129  #ifdef KMATRIX_IOSTREAM
130  cerr << "void KMatrix::copy_new( int k )";
131  cerr << ": no memory left ..." << endl;
132  #else
133  fprintf( stderr,"void KMatrix::copy_new( int k )" );
134  fprintf( stderr,": no memory left ...\n" );
135  #endif
136  #endif
137 
138  exit( 1 );
139  }
140  #endif
141  }
142  else if( k == 0 )
143  {
144  a = (K*)NULL;
145  }
146  else
147  {
148  #ifdef KMATRIX_PRINT
149  #ifdef KMATRIX_IOSTREAM
150  cerr << "void KMatrix::copy_new( int k )";
151  cerr << ": k < 0 ..." << endl;
152  #else
153  fprintf( stderr,"void KMatrix::copy_new( int k )" );
154  fprintf( stderr,": k < 0 ...\n" );
155  #endif
156  #endif
157 
158  exit( 1 );
159  }
160 }
int k
Definition: cfEzgcd.cc:92

◆ copy_shallow()

template<class K >
void KMatrix< K >::copy_shallow ( KMatrix< K > &  m)
inline

Definition at line 197 of file kmatrix.h.

198 {
199  a = m.a;
200  rows = m.rows;
201  cols = m.cols;
202 }

◆ copy_unit()

template<class K >
void KMatrix< K >::copy_unit ( int  rank)
inline

Definition at line 178 of file kmatrix.h.

179 {
180  int r,n=rank*rank;
181  copy_new( n );
182  rows = cols = rank;
183 
184  for( r=0; r<n; a[r++]=(K)0 );
185 
186  for( r=0; r<rows; r++ )
187  {
188  a[r*cols+r] = (K)1;
189  }
190 }
int rank(void) const
Definition: kmatrix.h:693

◆ copy_zero()

template<class K >
void KMatrix< K >::copy_zero ( void  )
inline

Definition at line 167 of file kmatrix.h.

168 {
169  a = (K*)NULL;
170  rows = cols = 0;
171 }

◆ determinant()

template<class K >
K KMatrix< K >::determinant ( void  ) const

Definition at line 867 of file kmatrix.h.

868 {
869  if( !is_quadratic( ) )
870  {
871  return 0;
872  }
873 
874  KMatrix<K> dummy( *this );
875 
876  int r,c,rank = 0;
877  K g;
878  K frank,fr;
879  K det = 1;
880 
881  // make sure that the elements of each row have gcd=1
882  // this is useful for pivoting
883 
884  for( r=0; r<dummy.rows; r++ )
885  {
886  det *= dummy.set_row_primitive( r );
887  }
888 
889  // search a pivoting element in each column
890  // perform Gauss elimination
891 
892  for( c=0; c<cols && rank<dummy.rows; c++ )
893  {
894  if( ( r = dummy.column_pivot( rank,c )) >= 0 )
895  {
896  det *= dummy.swap_rows( rank,r );
897 
898  for( r=rank+1; r<dummy.rows; r++ )
899  {
900  if( dummy.a[r*cols+c] != (K)0 )
901  {
902  g = gcd( dummy.a[r*cols+c],dummy.a[rank*cols+c] );
903 
904  frank = -dummy.a[r*cols+c]/g;
905  fr = dummy.a[rank*cols+c]/g;
906 
907  det /= dummy.add_rows( rank,r,frank,fr );
908  det *= dummy.set_row_primitive( r );
909  }
910  }
911  rank++;
912  }
913  }
914 
915  if( rank != dummy.rows )
916  {
917  return 0;
918  }
919 
920  for( r=0; r<dummy.rows; r++ )
921  {
922  det *= dummy.a[r*cols+r];
923  }
924 
925  return det;
926 }
g
Definition: cfModGcd.cc:4031
int is_quadratic(void) const
Definition: kmatrix.h:827
int gcd(int a, int b)
Definition: walkSupport.cc:836

◆ gausseliminate()

template<class K >
int KMatrix< K >::gausseliminate ( void  )

Definition at line 553 of file kmatrix.h.

554 {
555  int r,c,rank = 0;
556  K g;
557 
558  // make sure that the elements of each row have gcd=1
559  // this is useful for pivoting
560 
561  for( r=0; r<rows; r++ )
562  {
563  set_row_primitive( r );
564  }
565 
566  // search a pivoting element in each column
567  // perform Gauss elimination
568 
569  for( c=0; c<cols && rank<rows; c++ )
570  {
571  if( ( r = column_pivot( rank,c )) >= 0 )
572  {
573  swap_rows( rank,r );
574 
575  for( r=rank+1; r<rows; r++ )
576  {
577  if( a[r*cols+c] != (K)0 )
578  {
579  g = gcd( a[r*cols+c],a[rank*cols+c] );
580  add_rows( rank,r,-a[r*cols+c]/g,a[rank*cols+c]/g );
581  set_row_primitive( r );
582  }
583  }
584  rank++;
585  }
586  }
587  return rank;
588 }
int swap_rows(int, int)
Definition: kmatrix.h:372
int column_pivot(int, int) const
Definition: kmatrix.h:490
K set_row_primitive(int)
Definition: kmatrix.h:532
K add_rows(int, int, const K &, const K &)
Definition: kmatrix.h:423

◆ get()

template<class K >
K KMatrix< K >::get ( int  r,
int  c 
) const

Definition at line 339 of file kmatrix.h.

340 {
341  #ifdef KMATRIX_DEBUG
342  test_row( r );
343  test_col( c );
344  #endif
345 
346  return a[r*cols+c];
347 }

◆ is_quadratic()

template<class K >
int KMatrix< K >::is_quadratic ( void  ) const

Definition at line 827 of file kmatrix.h.

828 {
829  return ( rows == cols ? TRUE : FALSE );
830 }

◆ is_symmetric()

template<class K >
int KMatrix< K >::is_symmetric ( void  ) const

Definition at line 838 of file kmatrix.h.

839 {
840  if( is_quadratic( ) )
841  {
842  int r,c;
843 
844  for( r=1; r<rows; r++ )
845  {
846  for( c=0; c<r; c++ )
847  {
848  if( a[r*cols+c] != a[c*cols+r] )
849  {
850  return FALSE;
851  }
852  }
853  }
854  return TRUE;
855  }
856  else
857  {
858  return FALSE;
859  }
860 }

◆ multiply_row()

template<class K >
K KMatrix< K >::multiply_row ( int  r,
const K &  factor 
)

Definition at line 400 of file kmatrix.h.

401 {
402  #ifdef KMATRIX_DEBUG
403  test_row( r );
404  #endif
405 
406  int i_src = r*cols;
407 
408  for( int i=0; i<cols; i++,i_src++ )
409  {
410  a[i_src] *= factor;
411  }
412  return factor;
413 }
CanonicalForm factor
Definition: facAbsFact.cc:101

◆ rank()

template<class K >
int KMatrix< K >::rank ( void  ) const

Definition at line 693 of file kmatrix.h.

694 {
695  KMatrix<K> dummy( *this );
696 
697  return dummy.gausseliminate( );
698 }

◆ row_is_zero()

template<class K >
int KMatrix< K >::row_is_zero ( int  r) const

Definition at line 450 of file kmatrix.h.

451 {
452  #ifdef KMATRIX_DEBUG
453  test_row( r );
454  #endif
455 
456  for( int c=0; c<cols; c++ )
457  {
458  if( a[r*cols+c] != (K)0 ) return FALSE;
459  }
460  return TRUE;
461 }

◆ set()

template<class K >
void KMatrix< K >::set ( int  r,
int  c,
const K &  value 
)

Definition at line 354 of file kmatrix.h.

355 {
356  #ifdef KMATRIX_DEBUG
357  test_row( r );
358  test_col( c );
359  #endif
360 
361  a[r*cols+c] = value;
362 }

◆ set_row_primitive()

template<class K >
K KMatrix< K >::set_row_primitive ( int  r)

Definition at line 532 of file kmatrix.h.

533 {
534  #ifdef KMATRIX_DEBUG
535  test_row( r );
536  #endif
537 
538  K g = gcd( &(a[r*cols]),cols );
539 
540  for( int c=0; c<cols; c++ )
541  {
542  a[r*cols+c] /= g;
543  }
544  return g;
545 }

◆ solve()

template<class K >
int KMatrix< K >::solve ( K **  solution,
int *  k 
)

Definition at line 599 of file kmatrix.h.

600 {
601  int r,c,rank = 0;
602  K g;
603 
604  // ----------------------------------------------------
605  // make sure that the elements of each row have gcd=1
606  // this is useful for pivoting
607  // ----------------------------------------------------
608 
609  for( r=0; r<rows; r++ )
610  {
611  set_row_primitive( r );
612  }
613 
614  // ------------------------------------------
615  // search a pivoting element in each column
616  // perform Gauss elimination
617  // ------------------------------------------
618 
619  for( c=0; c<cols && rank < rows; c++ )
620  {
621  if( ( r = column_pivot( rank,c )) >= 0 )
622  {
623  swap_rows( rank,r );
624 
625  for( r=0; r<rank; r++ )
626  {
627  if( a[r*cols+c] != (K)0 )
628  {
629  g = gcd( a[r*cols+c],a[rank*cols+c] );
630  add_rows( rank,r,-a[r*cols+c]/g,a[rank*cols+c]/g );
631  set_row_primitive( r );
632  }
633  }
634 
635  for( r=rank+1; r<rows; r++ )
636  {
637  if( a[r*cols+c] != (K)0 )
638  {
639  g = gcd( a[r*cols+c],a[rank*cols+c] );
640  add_rows( rank,r,-a[r*cols+c]/g,a[rank*cols+c]/g );
641  set_row_primitive( r );
642  }
643  }
644 
645  rank++;
646  }
647  }
648 
649  if( rank < cols )
650  {
651  // ----------------------
652  // equation is solvable
653  // copy solutions
654  // ----------------------
655 
656  *solution = new K[cols-1];
657  *k = cols - 1;
658 
659  for( c=0; c<cols-1; c++ )
660  {
661  (*solution)[c] = (K)0;
662  }
663 
664  for( r=0; r<rows; r++ )
665  {
666  for( c=0; c<cols && a[r*cols+c] == (K)0; c++ );
667 
668  if( c < cols-1 )
669  {
670  (*solution)[c] = ((K)a[(r+1)*cols-1])/a[r*cols+c];
671  }
672  }
673  }
674  else
675  {
676  // --------------------------
677  // equation is not solvable
678  // --------------------------
679 
680  *solution = (K*)NULL;
681  *k = 0;
682  }
683 
684  return rank;
685 }

◆ swap_rows()

template<class K >
int KMatrix< K >::swap_rows ( int  r1,
int  r2 
)

Definition at line 372 of file kmatrix.h.

373 {
374  #ifdef KMATRIX_DEBUG
375  test_row( r1 );
376  test_row( r2 );
377  #endif
378 
379  if( r1 == r2 ) return 1;
380 
381  K tmp;
382 
383  for( int c=0; c<cols; c++ )
384  {
385  tmp = a[r1*cols+c];
386  a[r1*cols+c] = a[r2*cols+c];
387  a[r2*cols+c] = tmp;
388  }
389 
390  return -1;
391 }

Field Documentation

◆ a

template<class K >
K* KMatrix< K >::a
private

Definition at line 46 of file kmatrix.h.

◆ cols

template<class K >
int KMatrix< K >::cols
private

Definition at line 48 of file kmatrix.h.

◆ rows

template<class K >
int KMatrix< K >::rows
private

Definition at line 47 of file kmatrix.h.


The documentation for this class was generated from the following file: