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 &)
K	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 *)
K	multiply_row (int, const K &)
K	add_rows (int, int, const K &, const K &)
int	swap_rows (int, int)
K	set_row_primitive (int)
int	is_quadratic (void) const
int	is_symmetric (void) const
K	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.

{
    copy_zero( );
}

KMatrix() [2/3]

template<class K >

KMatrix< K >::KMatrix ( const KMatrix< K > &  m )

inline

Definition at line 244 of file kmatrix.h.

{
    copy_deep( m );
}

KMatrix() [3/3]

template<class K >

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

Definition at line 254 of file kmatrix.h.

{
    int n = r*c;
 
    copy_new( n );
 
    rows = r;
    cols = c;
 
    for( int i=0; i<n; i++ )
    {
        a[i]=(K)0;
    }
}

~KMatrix()

template<class K >

KMatrix< K >::~KMatrix

Definition at line 274 of file kmatrix.h.

{
    copy_delete( );
}

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.

{
    #ifdef KMATRIX_DEBUG
        test_row( src  );
        test_row( dest );
    #endif
 
    int i;
    int i_src  = src*cols;
    int i_dest = dest*cols;
 
    for( i=0; i<cols; i++,i_src++,i_dest++ )
    {
        a[i_dest] = a[i_src]*factor_src + a[i_dest]*factor_dest;
    }
 
    return factor_dest;
}

column_is_zero()

template<class K >

int KMatrix< K >::column_is_zero

(

int

c

)

const

Definition at line 470 of file kmatrix.h.

{
    #ifdef KMATRIX_DEBUG
        test_col( c );
    #endif
 
    for( int r=0; r<rows; r++ )
    {
        if( a[r*cols+c] != (K)0 ) return FALSE;
    }
    return TRUE;
}

column_pivot()

template<class K >

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

Definition at line 490 of file kmatrix.h.

{
    #ifdef KMATRIX_DEBUG
        test_row( r0 );
        test_col( c  );
    #endif
 
    int r;
    //  find first nonzero entry in column  c
 
    for( r=r0; r<rows && a[r*cols+c]==(K)0; r++ );
 
    if( r == rows )
    {
        //  column is zero
 
        return -1;
    }
    else
    {
        double val     = a[r*cols+c].complexity( );
        double val_new = 0.0;
        int pivot   = r;
 
        for( ; r<rows; r++ )
        {
            if( a[r*cols+c] != (K)0 &&
                ( val_new = a[r*cols+c].complexity( ) ) < val )
            {
                val = val_new;
                pivot = r;
            }
        }
        return pivot;
    }
}

copy_deep()

template<class K >

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

inline

Definition at line 209 of file kmatrix.h.

{
    if( m.a == (K*)NULL )
    {
        copy_zero( );
    }
    else
    {
        int n=m.rows*m.cols;
        copy_new( n );
        rows = m.rows;
        cols = m.cols;
 
        for( int i=0; i<n; i++ )
        {
            a[i] = m.a[i];
        }
    }
}

copy_delete()

template<class K >

void KMatrix< K >::copy_delete ( void  )

inline

Definition at line 108 of file kmatrix.h.

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

copy_new()

template<class K >

void KMatrix< K >::copy_new ( int  k )

inline

Definition at line 119 of file kmatrix.h.

{
    if( k > 0 )
    {
        a = new K[k];
 
        #ifndef SING_NDEBUG
        if( a == (K*)NULL )
        {
            #ifdef KMATRIX_PRINT
            #ifdef KMATRIX_IOSTREAM
                cerr << "void KMatrix::copy_new( int k )";
                cerr << ": no memory left ..." << endl;
            #else
                fprintf( stderr,"void KMatrix::copy_new( int k )" );
                fprintf( stderr,": no memory left ...\n" );
            #endif
            #endif
 
            exit( 1 );
        }
        #endif
    }
    else if( k == 0 )
    {
        a = (K*)NULL;
    }
    else
    {
        #ifdef KMATRIX_PRINT
        #ifdef KMATRIX_IOSTREAM
            cerr << "void KMatrix::copy_new( int k )";
            cerr << ": k < 0 ..." << endl;
        #else
            fprintf( stderr,"void KMatrix::copy_new( int k )" );
            fprintf( stderr,": k < 0 ...\n" );
        #endif
        #endif
 
        exit( 1 );
    }
}

copy_shallow()

template<class K >

void KMatrix< K >::copy_shallow ( KMatrix< K > &  m )

inline

Definition at line 197 of file kmatrix.h.

{
    a = m.a;
    rows = m.rows;
    cols = m.cols;
}

copy_unit()

template<class K >

void KMatrix< K >::copy_unit ( int  rank )

inline

Definition at line 178 of file kmatrix.h.

{
    int r,n=rank*rank;
    copy_new( n );
    rows = cols = rank;
 
    for( r=0; r<n; a[r++]=(K)0 );
 
    for( r=0; r<rows; r++ )
    {
        a[r*cols+r] = (K)1;
    }
}

copy_zero()

template<class K >

void KMatrix< K >::copy_zero ( void  )

inline

Definition at line 167 of file kmatrix.h.

{
    a = (K*)NULL;
    rows = cols = 0;
}

determinant()

template<class K >

K KMatrix< K >::determinant

(

void

)

const

Definition at line 867 of file kmatrix.h.

{
    if( !is_quadratic( ) )
    {
        return 0;
    }
 
    KMatrix<K> dummy( *this );
 
    int r,c,rank = 0;
    K g;
    K frank,fr;
    K det = 1;
 
    //  make sure that the elements of each row have gcd=1
    //  this is useful for pivoting
 
    for( r=0; r<dummy.rows; r++ )
    {
        det *= dummy.set_row_primitive( r );
    }
 
    //  search a pivoting element in each column
    //  perform Gauss elimination
 
    for( c=0; c<cols && rank<dummy.rows; c++ )
    {
        if( ( r = dummy.column_pivot( rank,c )) >= 0 )
        {
            det *= dummy.swap_rows( rank,r );
 
            for( r=rank+1; r<dummy.rows; r++ )
            {
                if( dummy.a[r*cols+c] != (K)0 )
                {
                    g = gcd( dummy.a[r*cols+c],dummy.a[rank*cols+c] );
 
                    frank = -dummy.a[r*cols+c]/g;
                    fr    = dummy.a[rank*cols+c]/g;
 
                    det /= dummy.add_rows( rank,r,frank,fr );
                    det *= dummy.set_row_primitive( r );
                }
            }
            rank++;
        }
    }
 
    if( rank != dummy.rows )
    {
        return 0;
    }
 
    for( r=0; r<dummy.rows; r++ )
    {
        det *= dummy.a[r*cols+r];
    }
 
    return  det;
}

gausseliminate()

template<class K >

int KMatrix< K >::gausseliminate

(

void

)

Definition at line 553 of file kmatrix.h.

{
    int r,c,rank = 0;
    K g;
 
    //  make sure that the elements of each row have gcd=1
    //  this is useful for pivoting
 
    for( r=0; r<rows; r++ )
    {
        set_row_primitive( r );
    }
 
    //  search a pivoting element in each column
    //  perform Gauss elimination
 
    for( c=0; c<cols && rank<rows; c++ )
    {
        if( ( r = column_pivot( rank,c )) >= 0 )
        {
            swap_rows( rank,r );
 
            for( r=rank+1; r<rows; r++ )
            {
                if( a[r*cols+c] != (K)0 )
                {
                    g = gcd( a[r*cols+c],a[rank*cols+c] );
                    add_rows( rank,r,-a[r*cols+c]/g,a[rank*cols+c]/g );
                    set_row_primitive( r );
                }
            }
            rank++;
        }
    }
    return rank;
}

get()

template<class K >

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

Definition at line 339 of file kmatrix.h.

{
    #ifdef KMATRIX_DEBUG
        test_row( r );
        test_col( c );
    #endif
 
    return a[r*cols+c];
}

is_quadratic()

template<class K >

int KMatrix< K >::is_quadratic

(

void

)

const

Definition at line 827 of file kmatrix.h.

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

is_symmetric()

template<class K >

int KMatrix< K >::is_symmetric

(

void

)

const

Definition at line 838 of file kmatrix.h.

{
    if( is_quadratic( ) )
    {
        int r,c;
 
        for( r=1; r<rows; r++ )
        {
            for( c=0; c<r; c++ )
            {
                if( a[r*cols+c] != a[c*cols+r] )
                {
                    return  FALSE;
                }
            }
        }
        return  TRUE;
    }
    else
    {
        return  FALSE;
    }
}

multiply_row()

template<class K >

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

Definition at line 400 of file kmatrix.h.

{
    #ifdef KMATRIX_DEBUG
        test_row( r );
    #endif
 
    int i_src = r*cols;
 
    for( int i=0; i<cols; i++,i_src++ )
    {
        a[i_src] *= factor;
    }
    return  factor;
}

rank()

template<class K >

int KMatrix< K >::rank

(

void

)

const

Definition at line 693 of file kmatrix.h.

{
    KMatrix<K> dummy( *this );
 
    return dummy.gausseliminate( );
}

row_is_zero()

template<class K >

int KMatrix< K >::row_is_zero

(

int

r

)

const

Definition at line 450 of file kmatrix.h.

{
    #ifdef KMATRIX_DEBUG
        test_row( r );
    #endif
 
    for( int c=0; c<cols; c++ )
    {
        if( a[r*cols+c] != (K)0 ) return FALSE;
    }
    return TRUE;
}

set()

template<class K >

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

Definition at line 354 of file kmatrix.h.

{
    #ifdef KMATRIX_DEBUG
        test_row( r );
        test_col( c );
    #endif
 
    a[r*cols+c] = value;
}

set_row_primitive()

template<class K >

K KMatrix< K >::set_row_primitive

(

int

r

)

Definition at line 532 of file kmatrix.h.

{
    #ifdef KMATRIX_DEBUG
        test_row( r );
    #endif
 
    K   g = gcd( &(a[r*cols]),cols );
 
    for( int c=0; c<cols; c++ )
    {
        a[r*cols+c] /= g;
    }
    return  g;
}

solve()

template<class K >

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

Definition at line 599 of file kmatrix.h.

{
    int r,c,rank = 0;
    K g;
 
    // ----------------------------------------------------
    //  make sure that the elements of each row have gcd=1
    //  this is useful for pivoting
    // ----------------------------------------------------
 
    for( r=0; r<rows; r++ )
    {
        set_row_primitive( r );
    }
 
    // ------------------------------------------
    //  search a pivoting element in each column
    //  perform Gauss elimination
    // ------------------------------------------
 
    for( c=0; c<cols && rank < rows; c++ )
    {
        if( ( r = column_pivot( rank,c )) >= 0 )
        {
            swap_rows( rank,r );
 
            for( r=0; r<rank; r++ )
            {
                if( a[r*cols+c] != (K)0 )
                {
                    g = gcd( a[r*cols+c],a[rank*cols+c] );
                    add_rows( rank,r,-a[r*cols+c]/g,a[rank*cols+c]/g );
                    set_row_primitive( r );
                }
            }
 
            for( r=rank+1; r<rows; r++ )
            {
                if( a[r*cols+c] != (K)0 )
                {
                    g = gcd( a[r*cols+c],a[rank*cols+c] );
                    add_rows( rank,r,-a[r*cols+c]/g,a[rank*cols+c]/g );
                    set_row_primitive( r );
                }
            }
 
            rank++;
        }
    }
 
    if( rank < cols )
    {
        // ----------------------
        //  equation is solvable
        //  copy solutions
        // ----------------------
 
        *solution = new K[cols-1];
        *k        = cols - 1;
 
        for( c=0; c<cols-1; c++ )
        {
            (*solution)[c] = (K)0;
        }
 
        for( r=0; r<rows; r++ )
        {
            for( c=0; c<cols && a[r*cols+c] == (K)0; c++ );
 
            if( c < cols-1 )
            {
                (*solution)[c] = ((K)a[(r+1)*cols-1])/a[r*cols+c];
            }
        }
    }
    else
    {
        // --------------------------
        //  equation is not solvable
        // --------------------------
 
        *solution = (K*)NULL;
        *k   = 0;
    }
 
    return rank;
}

swap_rows()

template<class K >

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

Definition at line 372 of file kmatrix.h.

{
    #ifdef KMATRIX_DEBUG
        test_row( r1 );
        test_row( r2 );
    #endif
 
    if( r1 == r2 ) return 1;
 
    K   tmp;
 
    for( int c=0; c<cols; c++ )
    {
        tmp          = a[r1*cols+c];
        a[r1*cols+c] = a[r2*cols+c];
        a[r2*cols+c] = tmp;
    }
 
    return -1;
}

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:

• kernel/spectrum/kmatrix.h