sparse_matrix.h
00001 /* Copyright (C) 2003-2005  Martin Förg
00002 
00003  * This library is free software; you can redistribute it and/or
00004  * modify it under the terms of the GNU Lesser General Public
00005  * License as published by the Free Software Foundation; either
00006  * version 2.1 of the License, or (at your option) any later version.
00007  * 
00008  * This library is distributed in the hope that it will be useful,
00009  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00010  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00011  * Lesser General Public License for more details.
00012  * 
00013  * You should have received a copy of the GNU Lesser General Public
00014  * License along with this library; if not, write to the Free Software
00015  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
00016  *
00017  * Contact:
00018  *   martin.o.foerg@googlemail.com
00019  *
00020  */
00021 
00022 #ifndef sparse_matrix_h
00023 #define sparse_matrix_h
00024 
00025 #include "matrix.h"
00026 #include "square_matrix.h"
00027 #include "types.h"
00028 #include "_memory.h"
00029 
00030 namespace fmatvec {
00031 
00043   template <class AT>
00044     class Matrix<Sparse,Ref,Ref,AT> {
00045 
00046       protected:
00047 
00049     
00050         Memory<AT> memEle;
00051         Memory<int> memI, memJ;
00052         AT *ele;
00053         int *I, *J;
00054         int m, n, k;
00055 
00056         void deepCopy(const Matrix<Sparse,Ref,Ref,AT> &x);
00057 
00058         void deepCopy(const SquareMatrix<Ref,AT> &A);
00059         void deepCopy(const Matrix<Symmetric, Var, Var,AT> &A);
00060 
00062 
00063 
00064       public:
00065 
00070         Matrix() : memEle(), memI(), memJ(), ele(0), I(0), J(0), m(0), n(0), k(0) { }
00071 
00072 //        template<class Ini=All<AT> >
00073 //          Matrix(int n_, Ini ini=All<AT>()) : memEle(n_*n_), memI(n_+1), memJ(n_*n_), ele((AT*)memEle.get()), I((int*)memI.get()), J((int*)memJ.get()), m(n_), n(n_), k(n_*n_) {
00074 //            init(ini);
00075 //          }
00076 //        template<class Ini=All<AT> >
00077 //          Matrix(int m_, int n_, Ini ini) : memEle(n_*n_), memI(n_+1), memJ(n_*n_), ele((AT*)memEle.get()), I((int*)memI.get()), J((int*)memJ.get()), m(n_), n(n_), k(n_*n_) {  
00078 //            init(ini);
00079 //          }
00080 
00081         Matrix(int m_, int n_, int k_, Noinit) : memEle(k_), memI(n_+1), memJ(k_), ele((AT*)memEle.get()), I((int*)memI.get()), J((int*)memJ.get()), m(n_), n(n_), k(k_) { }
00082         Matrix(int m_, int n_, int k_, Init ini=INIT, const AT &a=0) : memEle(k_), memI(n_+1), memJ(k_), ele((AT*)memEle.get()), I((int*)memI.get()), J((int*)memJ.get()), m(n_), n(n_), k(k_) {  init(a); }
00083 
00084         Matrix(int n_, Noinit) : memEle(n_*n_), memI(n_+1), memJ(n_*n_), ele((AT*)memEle.get()), I((int*)memI.get()), J((int*)memJ.get()), m(n_), n(n_), k(n_*n_) { }
00085         Matrix(int n_, Init ini=INIT, const AT &a=0) : memEle(n_*n_), memI(n_+1), memJ(n_*n_), ele((AT*)memEle.get()), I((int*)memI.get()), J((int*)memJ.get()), m(n_), n(n_), k(n_*n_) { init(a); }
00086 
00087         Matrix(int m_, int n_, Noinit) : memEle(n_*n_), memI(n_+1), memJ(n_*n_), ele((AT*)memEle.get()), I((int*)memI.get()), J((int*)memJ.get()), m(n_), n(n_), k(n_*n_) { }
00088         Matrix(int m_, int n_, Init ini=INIT, const AT &a=0) : memEle(n_*n_), memI(n_+1), memJ(n_*n_), ele((AT*)memEle.get()), I((int*)memI.get()), J((int*)memJ.get()), m(n_), n(n_), k(n_*n_) { init(a); }
00089 
00090 
00098         Matrix(const Matrix<Sparse,Ref,Ref,AT> &A) : memEle(A.memEle), memI(A.memI), memJ(A.memJ), ele(A.ele), I(A.I), J(A.J), m(A.m), n(A.n), k(A.k) {
00099         }
00100 
00103         ~Matrix() {
00104         }
00105 
00106         Matrix<Sparse,Ref,Ref,AT>& resize() {
00107             m = n = k = 0;
00108             memEle.resize(0);
00109             memI.resize(0);
00110             memJ.resize(0);
00111             ele = 0;
00112             I = J = 0;
00113             return *this;
00114         }
00115 
00116         Matrix<Sparse,Ref,Ref,AT>& resize(int n_, int k_, Noinit) {
00117             m = n_; n = n_; k = k_;
00118             memEle.resize(k);
00119             memI.resize(m+1);
00120             memJ.resize(k);
00121             ele = (AT*)memEle.get();
00122             I = (int*)memI.get();
00123             J = (int*)memJ.get();
00124             return *this;
00125         }
00126 
00127         Matrix<Sparse,Ref,Ref,AT>& resize(int n, int k, Init ini=INIT, const AT &a=0) { return resize(m,k,Noinit()).init(a); }
00128 
00135         inline Matrix<Sparse,Ref,Ref,AT>& operator<<(const Matrix<Sparse,Ref,Ref,AT> &A);
00136 
00143         inline Matrix<Sparse,Ref,Ref,AT>& operator>>(const Matrix<Sparse,Ref,Ref,AT> &A);
00144 
00149         inline Matrix<Sparse,Ref,Ref,AT>& operator<<(const SquareMatrix<Ref,AT> &A);
00150 
00155   inline Matrix<Sparse,Ref,Ref,AT>& operator<<(const Matrix<Symmetric, Var, Var ,AT> &A);
00156 
00165         inline Matrix<Sparse,Ref,Ref,AT>& operator=(const Matrix<Sparse,Ref,Ref,AT> &A);
00166 
00171         const AT* operator()() const {
00172           return ele;
00173         };
00174 
00180         AT* operator()() {
00181           return ele;
00182         };
00183 
00188         const int* Ip() const {
00189           return I;
00190         };
00191 
00196         int* Ip() {
00197           return I;
00198         };
00199 
00204         const int* Jp() const {
00205           return J;
00206         };
00207 
00212         int* Jp() {
00213           return J;
00214         };
00215 
00220         int rows() const {return m;};
00221 
00226         int cols() const {return n;};
00227 
00233         Matrix<Sparse,Ref,Ref,AT> copy() const;
00234 
00242         Matrix<Sparse,Ref,Ref,AT>& init(const AT &a);
00243         inline Matrix<Sparse,Ref,Ref,AT>& init(Init, const AT &a=0) { return init(a); }
00244         inline Matrix<Sparse,Ref,Ref,AT>& init(Noinit, const AT &a=0) { return *this; }
00245 
00246     };
00247   // ------------------------- Constructors -------------------------------------
00248   // ----------------------------------------------------------------------------
00249 
00250   template <class AT>
00251     inline Matrix<Sparse,Ref,Ref,AT>& Matrix<Sparse,Ref,Ref,AT>::operator>>(const Matrix<Sparse,Ref,Ref,AT> &A) { 
00252 
00253       m=A.m;
00254       n=A.n;
00255       k=A.k;
00256       memEle = A.memEle;
00257       memI = A.memI;
00258       memJ = A.memJ;
00259       ele = A.ele;
00260       I = A.I;
00261       J = A.J;
00262       k = A.k;
00263 
00264       return *this;
00265     }
00266 
00267   template <class AT>
00268     inline Matrix<Sparse,Ref,Ref,AT>& Matrix<Sparse,Ref,Ref,AT>::operator=(const Matrix<Sparse,Ref,Ref,AT> &A) { 
00269 
00270       if(!ele) {
00271         m = A.m;
00272         n = A.n;
00273         k = A.k;
00274         memEle.resize(k);
00275         memI.resize(m+1);
00276         memJ.resize(k);
00277         ele = (AT*)memEle.get();
00278         I = (int*)memI.get();
00279         J = (int*)memJ.get();
00280       }
00281       else {
00282 #ifndef FMATVEC_NO_SIZE_CHECK
00283         assert(m == A.m);
00284         assert(n == A.n);
00285         assert(k == A.k);
00286 #endif
00287       }
00288 
00289       deepCopy(A);
00290 
00291       return *this;
00292     }
00293 
00294   template <class AT>
00295     inline Matrix<Sparse,Ref,Ref,AT>& Matrix<Sparse,Ref,Ref,AT>::operator<<(const Matrix<Sparse,Ref,Ref,AT> &A) { 
00296 
00297       if(m!=A.m || n!=A.n || k!=A.k) {
00298         m = A.m;
00299         n = A.n;
00300         k = A.k;
00301         memEle.resize(k);
00302         memI.resize(m+1);
00303         memJ.resize(k);
00304         ele = (AT*)memEle.get();
00305         I = (int*)memI.get();
00306         J = (int*)memJ.get();
00307       }
00308 
00309       deepCopy(A);
00310 
00311       return *this;
00312     }
00313 
00314   template <class AT>
00315     inline Matrix<Sparse,Ref,Ref,AT>& Matrix<Sparse,Ref,Ref,AT>::operator<<(const SquareMatrix<Ref,AT> &A) { 
00316 
00317       if(m!=A.rows() || n!=A.cols()) {
00318         m = A.rows();
00319         n = A.cols();
00320         k = countElements(A);
00321         memEle.resize(k);
00322         memI.resize(m+1);
00323         memJ.resize(k);
00324         ele = (AT*)memEle.get();
00325         I = (int*)memI.get();
00326         J = (int*)memJ.get();
00327       } else {
00328         int k_ = countElements(A);
00329         if(k != k_) {
00330           k = k_;
00331           memEle.resize(k);
00332           memJ.resize(k);
00333           ele = (AT*)memEle.get();
00334           J = (int*)memJ.get();
00335         }
00336       }
00337 
00338       deepCopy(A);
00339 
00340       return *this;
00341     }
00342 
00343   template <class AT>
00344   inline Matrix<Sparse, Ref, Ref, AT>& Matrix<Sparse, Ref, Ref, AT>::operator<<(const Matrix<Symmetric, Var, Var, AT> &A) {
00345 
00346       if (m != A.rows() || n != A.cols()) {
00347         m = A.rows();
00348         n = A.cols();
00349         k = countElementsLT(A) * 2 - A.rows();
00350         memEle.resize(k);
00351         memI.resize(m + 1);
00352         memJ.resize(k);
00353         ele = (AT*) memEle.get();
00354         I = (int*) memI.get();
00355         J = (int*) memJ.get();
00356       }
00357       else {
00358         int k_ = countElementsLT(A) * 2 - A.rows();
00359         if (k != k_) {
00360           k = k_;
00361           memEle.resize(k);
00362           memJ.resize(k);
00363           ele = (AT*) memEle.get();
00364           J = (int*) memJ.get();
00365         }
00366       }
00367 
00368       deepCopy(A);
00369 
00370       return *this;
00371   }
00372 
00373   template <class AT>
00374     Matrix<Sparse,Ref,Ref,AT> Matrix<Sparse,Ref,Ref,AT>::copy() const {
00375 
00376       Matrix<Sparse,Ref,Ref,AT> A(m,NONINIT);
00377 
00378       A.deepCopy(*this);
00379 
00380       return A;
00381     }
00382 
00383   template <class AT>
00384     void Matrix<Sparse,Ref,Ref,AT>::deepCopy(const Matrix<Sparse,Ref,Ref,AT> &A) { 
00385       for(int i=0; i<=m; i++) {
00386         I[i] = A.I[i];
00387       }
00388       for(int i=0; i<k; i++) {
00389         ele[i] = A.ele[i];
00390         J[i] = A.J[i];
00391       }
00392     }
00393 
00394   template <class AT> void Matrix<Sparse,Ref,Ref,AT>::deepCopy(const SquareMatrix<Ref,AT> &A) { 
00395       int k=0;
00396       int i;
00397       for(i=0; i<A.size(); i++) {
00398         ele[k]=A(i,i);
00399         J[k]=i;
00400         I[i]=k++;
00401         for(int j=0; j<i; j++) {
00402           // TODO eps
00403           if(fabs(A(i,j))>1e-16) {
00404             ele[k]=A(i,j);
00405             J[k++]=j;
00406           }
00407         }
00408         for(int j=i+1; j<A.size(); j++) {
00409           // TODO eps
00410           if(fabs(A(i,j))>1e-16) {
00411             ele[k]=A(i,j);
00412             J[k++]=j;
00413           }
00414         }
00415       }
00416       if(n) I[i]=k;
00417     }
00418 
00419   template <class AT> void Matrix<Sparse,Ref,Ref,AT>::deepCopy(const Matrix<Symmetric, Var, Var,AT> &A) {
00420       int k=0;
00421       int i;
00422       for(i=0; i<A.size(); i++) {
00423         ele[k]=A(i,i);
00424         J[k]=i;
00425         I[i]=k++;
00426         for(int j=0; j<i; j++) {
00427           // TODO eps
00428           if(fabs(A(i,j))>1e-16) {
00429             ele[k]=A(i,j);
00430             J[k++]=j;
00431           }
00432         }
00433         for(int j=i+1; j<A.size(); j++) {
00434           // TODO eps
00435           if(fabs(A(i,j))>1e-16) {
00436             ele[k]=A(i,j);
00437             J[k++]=j;
00438           }
00439         }
00440       }
00441       if(n) I[i]=k;
00442   }
00443 
00444   template <class AT>
00445     Matrix<Sparse,Ref,Ref,AT>&  Matrix<Sparse,Ref,Ref,AT>::init(const AT& val) {
00446       for(int i=0; i<k; i++) {
00447         ele[i] = val;
00448       }
00449       return *this;
00450     }
00451 
00452 /* template <class AT> template <class Type> void Matrix<Sparse,Ref,Ref,AT>::deepCopy(const Matrix<Type, AT> &A) { 
00453       k=0;
00454       AT *eleBuf = new AT[m*n];
00455       int *JBuf = new int[m*n];
00456       int i;
00457       for(i=0; i<A.rows(); i++) {
00458         eleBuf[k]=A(i,i);
00459         JBuf[k]=i;
00460         I[i]=k++;
00461         for(int j=0; j<i; j++) {
00462           // TODO eps
00463           if(fabs(A(i,j))>1e-16) {
00464             eleBuf[k]=A(i,j);
00465             JBuf[k++]=j;
00466           }
00467         }
00468         for(int j=i+1; j<A.cols(); j++) {
00469           // TODO eps
00470           if(fabs(A(i,j))>1e-16) {
00471             eleBuf[k]=A(i,j);
00472             JBuf[k++]=j;
00473           }
00474         }
00475       }
00476       I[i]=k;
00477       memEle.resize(k);
00478       memJ.resize(k);
00479       ele = (AT*)memEle.get();
00480       J = (int*)memJ.get();
00481       for(int i=0; i<k; i++) {
00482         ele[i] = eleBuf[i];
00483         J[i] = JBuf[i];
00484       }
00485 
00486       delete [] eleBuf;
00487       delete [] JBuf;
00488     }
00489 
00490     */
00491 
00492   //template <> extern void Matrix<Sparse,Ref,Ref,double>::deepCopy(const Matrix<Sparse,Ref,Ref,double> &A);
00493 
00494 }
00495 
00496 #endif