core/vnl/vnl_sparse_matrix.txx
Go to the documentation of this file.
00001 // This is core/vnl/vnl_sparse_matrix.txx
00002 #ifndef vnl_sparse_matrix_txx_
00003 #define vnl_sparse_matrix_txx_
00004 //:
00005 // \file
00006 
00007 #include "vnl_sparse_matrix.h"
00008 
00009 #include <vcl_cassert.h>
00010 #include <vcl_algorithm.h>
00011 #include <vcl_iostream.h>
00012 
00013 #include <vnl/vnl_math.h>
00014 #include <vnl/vnl_complex_traits.h>
00015 
00016 #ifdef DEBUG_SPARSE
00017 # include <vnl/vnl_matrix.h>
00018 #endif
00019 
00020 // Implementation of vnl_sparse_matrix
00021 //------------------------------------------------------------
00022 
00023 //: Construct an empty matrix
00024 template <class T>
00025 vnl_sparse_matrix<T>::vnl_sparse_matrix()
00026   : rs_(0), cs_(0)
00027 {
00028 }
00029 
00030 //------------------------------------------------------------
00031 //: Construct an empty m*n matrix.  There are m rows and n columns.
00032 template <class T>
00033 vnl_sparse_matrix<T>::vnl_sparse_matrix(unsigned int m, unsigned int n)
00034   : elements(m), rs_(m), cs_(n)
00035 {
00036 }
00037 
00038 //------------------------------------------------------------
00039 //: Construct an m*n Matrix and copy rhs into it.
00040 template <class T>
00041 vnl_sparse_matrix<T>::vnl_sparse_matrix(const vnl_sparse_matrix<T>& rhs)
00042   : elements(rhs.elements), rs_(rhs.rs_), cs_(rhs.cs_)
00043 {
00044 }
00045 
00046 //------------------------------------------------------------
00047 //: Copy another vnl_sparse_matrix<T> into this.
00048 template <class T>
00049 vnl_sparse_matrix<T>& vnl_sparse_matrix<T>::operator=(const vnl_sparse_matrix<T>& rhs)
00050 {
00051   if (this == &rhs)
00052     return *this;
00053 
00054   elements = rhs.elements;
00055   rs_ = rhs.rs_;
00056   cs_ = rhs.cs_;
00057 
00058   return *this;
00059 }
00060 
00061 //------------------------------------------------------------
00062 //: Multiply this*rhs, another sparse matrix.
00063 template <class T>
00064 void vnl_sparse_matrix<T>::mult(vnl_sparse_matrix<T> const& rhs, vnl_sparse_matrix<T>& result) const
00065 {
00066   assert(rhs.rows() == columns());
00067   assert(this != &result); // make sure not to overwrite *this
00068   assert(&rhs != &result); // make sure not to overwrite rhs
00069   unsigned int result_rows = rows();
00070   unsigned int result_cols = rhs.columns();
00071 
00072   // Early return: empty result matrix
00073   if (result_rows <= 0 || result_cols <= 0) return;
00074 
00075   result.cs_ = result_cols;
00076   if (result.rows() != result_rows)
00077   {
00078     // Clear result matrix.
00079     result.elements.clear();
00080     // give the result matrix enough rows (but only if not yet correct).
00081     result.elements.resize(result_rows);
00082     result.rs_ = result_rows;
00083     for (unsigned row_id=0; row_id<result_rows; ++row_id)
00084       result.elements[row_id] = row();
00085   }
00086 
00087   // Now, iterate over non-zero rows of this.
00088   for (unsigned row_id=0; row_id<elements.size(); ++row_id) {
00089     // Get the row from this matrix (lhs).
00090     row const& this_row = elements[row_id];
00091 
00092     // Skip to next row if empty.
00093     if (this_row.empty())
00094       continue;
00095 
00096     // Get the new row in the result matrix.
00097     row& result_row = result.elements[row_id];
00098 
00099     // Iterate over the row.
00100     for (typename row::const_iterator col_iter = this_row.begin();
00101          col_iter != this_row.end();
00102          ++col_iter)
00103     {
00104       // Get the element from the row.
00105       vnl_sparse_matrix_pair<T> const & entry = *col_iter;
00106       unsigned const col_id = entry.first;
00107 
00108       // So we are at (row_id,col_id) = this_val in lhs matrix (this).
00109       // This must be multiplied by each entry in row col_id in
00110       // the rhs matrix, and the result added to result_row[col_id].
00111 
00112       // If that row in rhs is empty, there is nothing to do.
00113       row const & rhs_row = rhs.elements[col_id];
00114       if (rhs_row.empty())
00115         continue;
00116 
00117       // Else iterate over rhs's row.
00118       typename row::iterator result_col_iter = result_row.begin();
00119       for (typename row::const_iterator rhs_col_iter = rhs_row.begin();
00120            rhs_col_iter != rhs_row.end();
00121            ++rhs_col_iter)
00122       {
00123         const vnl_sparse_matrix_pair<T>& rhs_entry = *rhs_col_iter;
00124         unsigned int const dest_col = rhs_entry.first;
00125 
00126         // Calculate the product.
00127         T prod = entry.second * rhs_entry.second;
00128 
00129         // This must be added into result_row, at column dest_col.
00130         while ((result_col_iter != result_row.end()) &&
00131                ((*result_col_iter).first < dest_col))
00132           ++result_col_iter;
00133 
00134         if ((result_col_iter == result_row.end()) ||
00135             ((*result_col_iter).first != dest_col))
00136         {
00137           // Add new column to the row.
00138           result_col_iter = result_row.insert(result_col_iter, vnl_sparse_matrix_pair<T>(dest_col,prod));
00139         }
00140         else
00141         {
00142           // Else add product to existing contents.
00143           (*result_col_iter).second += prod;
00144         }
00145       }
00146     }
00147   }
00148 }
00149 
00150 //------------------------------------------------------------
00151 //: Multiply this*p, a fortran order matrix.
00152 //  The matrix p has n rows and m columns, and is in fortran order, ie. columns first.
00153 template <class T>
00154 void vnl_sparse_matrix<T>::mult(unsigned int prows, unsigned int pcols,
00155                                 T const* p, T* q) const
00156 {
00157   assert(prows == columns());
00158 
00159   // Clear q matrix.
00160   int size = prows*pcols;
00161   for (int temp=0; temp<size; temp++)
00162     q[temp] = T(0);
00163 
00164 #ifdef DEBUG_SPARSE
00165   vnl_matrix<double> md(rows(),columns());
00166   for (int rr = 0; rr<rows(); rr++)
00167     for (int cc = 0; cc<columns(); cc++)
00168       md(rr,cc) = (*this)(rr,cc);
00169 
00170   vnl_matrix<double> pd(prows,pcols);
00171   for (int rr = 0; rr<prows; rr++)
00172     for (int cc = 0; cc<pcols; cc++)
00173       pd(rr,cc) = p[rr + cc*prows];
00174 
00175   vcl_cout << "Initial p:\n";
00176   for (int rr = 0; rr<prows; rr++) {
00177     for (int cc = 0; cc<pcols; cc++) {
00178       T pval = p[rr + cc*prows];
00179       vcl_cout << pval << ' ';
00180     }
00181     vcl_cout << '\n';
00182   }
00183 #endif
00184 
00185   // Now, iterate over non-zero rows of this.
00186   for (unsigned row_id=0; row_id<elements.size(); ++row_id) {
00187     // Get the row from this matrix (lhs).
00188     row const & this_row = elements[row_id];
00189 
00190     // Skip to next row if empty.
00191     if (this_row.empty())
00192       continue;
00193 
00194     // Iterate over the row.
00195     for (typename row::const_iterator col_iter = this_row.begin();
00196          col_iter != this_row.end();
00197          ++col_iter)
00198     {
00199       // Get the element from the row.
00200       vnl_sparse_matrix_pair<T> const & entry = *col_iter;
00201       unsigned const col_id = entry.first;
00202 
00203       // So we are at (row_id,col_id) = this_val in lhs matrix
00204       // (this).  This must be multiplied by each entry in row
00205       // col_id in the p matrix, and the result added to
00206       // (row_id,p_col_id) in the q matrix.
00207       //
00208 
00209       // Iterate over p's row.
00210       for (unsigned int p_col_id = 0; p_col_id < pcols; p_col_id++) {
00211         // Get the correct position from p.
00212         T pval = p[col_id + p_col_id*prows];
00213 
00214         // Calculate the product.
00215         T prod = entry.second * pval;
00216 
00217         // Add the product into the correct position in q.
00218         q[row_id + p_col_id*prows] += prod;
00219       }
00220     }
00221   }
00222 
00223 #ifdef DEBUG_SPARSE
00224   vcl_cout << "Final q:\n";
00225   for (int rr = 0; rr<prows; rr++) {
00226     for (int cc = 0; cc<pcols; cc++) {
00227       T pval = q[rr + cc*prows];
00228       vcl_cout << pval << ' ';
00229     }
00230     vcl_cout << '\n';
00231   }
00232   vcl_cout << "nonsparse: " << md*pd << '\n';
00233 #endif
00234 }
00235 
00236 
00237 //------------------------------------------------------------
00238 //: Multiply this*rhs, a vector.
00239 template <class T>
00240 void vnl_sparse_matrix<T>::mult(vnl_vector<T> const& rhs, vnl_vector<T>& result) const
00241 {
00242   assert(rhs.size() == columns());
00243 
00244   result.set_size( rows() );
00245   result.fill(T(0));
00246 
00247   int rhs_row_id =0;
00248   typename vcl_vector<row>::const_iterator lhs_row_iter = elements.begin();
00249   for ( ; lhs_row_iter != elements.end(); ++lhs_row_iter, rhs_row_id++ ) {
00250     row const & lhs_row = *lhs_row_iter;
00251     if (lhs_row.empty()) continue;
00252 
00253     typename row::const_iterator lhs_col_iter = lhs_row.begin();
00254     for ( ; lhs_col_iter != lhs_row.end(); ++lhs_col_iter) {
00255       vnl_sparse_matrix_pair<T> const & entry = *lhs_col_iter;
00256       unsigned const lhs_col_id = entry.first;
00257 
00258       result[ rhs_row_id ] += rhs[ lhs_col_id ] * entry.second;
00259     }
00260   }
00261 }
00262 
00263 //------------------------------------------------------------
00264 //: Multiply lhs*this, where lhs is a vector
00265 template <class T>
00266 void vnl_sparse_matrix<T>::pre_mult(const vnl_vector<T>& lhs, vnl_vector<T>& result) const
00267 {
00268   assert(lhs.size() == rows());
00269 
00270   // Resize and clear result vector
00271   result.set_size( columns() );
00272   result.fill(T(0));
00273 
00274   // Now, iterate over lhs values and rows of rhs
00275   unsigned lhs_col_id = 0;
00276   for (typename vcl_vector<row>::const_iterator rhs_row_iter = elements.begin();
00277        rhs_row_iter != elements.end();
00278        ++rhs_row_iter, lhs_col_id++ )
00279   {
00280     // Get the row from rhs matrix.
00281     row const & rhs_row = *rhs_row_iter;
00282 
00283     // Skip to next row if empty.
00284     if (rhs_row.empty()) continue;
00285 
00286     // Iterate over values in rhs row
00287     for (typename row::const_iterator rhs_col_iter = rhs_row.begin();
00288          rhs_col_iter != rhs_row.end();
00289          ++rhs_col_iter)
00290     {
00291       // Get the element from the row.
00292       vnl_sparse_matrix_pair<T> const& entry = *rhs_col_iter;
00293       unsigned const rhs_col_id = entry.first;
00294 
00295       result[ rhs_col_id ] += lhs[ lhs_col_id ] * entry.second;
00296     }
00297   }
00298 }
00299 
00300 //------------------------------------------------------------
00301 //: Add rhs to this.
00302 template <class T>
00303 void vnl_sparse_matrix<T>::add(const vnl_sparse_matrix<T>& rhs,
00304                                vnl_sparse_matrix<T>& result) const
00305 {
00306   assert((rhs.rows() == rows()) && (rhs.columns() == columns()));
00307 
00308   // Clear result matrix.
00309   result.elements.clear();
00310 
00311   // Now give the result matrix enough rows.
00312   result.elements.resize(rows());
00313   result.rs_ = rows();
00314   result.cs_ = columns();
00315 
00316   // Now, iterate over non-zero rows of this.
00317   unsigned int row_id = 0;
00318   for (typename vcl_vector<row>::const_iterator row_iter = elements.begin();
00319        row_iter != elements.end();
00320        ++row_iter, ++row_id)
00321   {
00322     // Get the row from this matrix (lhs).
00323     row const & this_row = *row_iter;
00324 
00325     // Get the new row in the result matrix.
00326     row& result_row = result.elements[row_id];
00327 
00328     // Store this into result row.
00329     result_row = this_row;
00330 
00331     // If rhs row is empty, we are done.
00332     if (rhs.empty_row(row_id))
00333       continue;
00334 
00335     // Get the rhs row.
00336     row const& rhs_row = rhs.elements[row_id];
00337 
00338     // Iterate over the rhs row.
00339     for (typename row::const_iterator col_iter = rhs_row.begin();
00340          col_iter != rhs_row.end();
00341          ++col_iter)
00342     {
00343       // Get the element from the row.
00344       vnl_sparse_matrix_pair<T> const& entry = *col_iter;
00345       unsigned const col_id = entry.first;
00346 
00347       // So we are at (row_id,col_id) in rhs matrix.
00348       result(row_id,col_id) += entry.second;
00349     }
00350   }
00351 }
00352 
00353 //------------------------------------------------------------
00354 //: Subtract rhs from this.
00355 template <class T>
00356 void vnl_sparse_matrix<T>::subtract(const vnl_sparse_matrix<T>& rhs,
00357                                     vnl_sparse_matrix<T>& result) const
00358 {
00359   assert((rhs.rows() == rows()) && (rhs.columns() == columns()));
00360 
00361   // Clear result matrix.
00362   result.elements.clear();
00363 
00364   // Now give the result matrix enough rows.
00365   result.elements.resize(rows());
00366   result.rs_ = rows();
00367   result.cs_ = columns();
00368 
00369   // Now, iterate over non-zero rows of this.
00370   unsigned int row_id = 0;
00371   for (typename vcl_vector<row>::const_iterator row_iter = elements.begin();
00372        row_iter != elements.end();
00373        ++row_iter, ++row_id)
00374   {
00375     // Get the row from this matrix (lhs).
00376     row const& this_row = *row_iter;
00377 
00378     // Get the new row in the result matrix.
00379     row& result_row = result.elements[row_id];
00380 
00381     // Store this into result row.
00382     result_row = this_row;
00383 
00384     // If rhs row is empty, we are done.
00385     if (rhs.empty_row(row_id))
00386       continue;
00387 
00388     // Get the rhs row.
00389     row const& rhs_row = rhs.elements[row_id];
00390 
00391     // Iterate over the rhs row.
00392     for (typename row::const_iterator col_iter = rhs_row.begin();
00393          col_iter != rhs_row.end();
00394          ++col_iter)
00395     {
00396       // Get the element from the row.
00397       vnl_sparse_matrix_pair<T> const& entry = *col_iter;
00398       unsigned const col_id = entry.first;
00399 
00400       // So we are at (row_id,col_id) in rhs matrix.
00401       result(row_id,col_id) -= entry.second;
00402     }
00403   }
00404 }
00405 
00406 //------------------------------------------------------------
00407 //: Get a reference to an entry in the matrix.
00408 template <class T>
00409 T& vnl_sparse_matrix<T>::operator()(unsigned int r, unsigned int c)
00410 {
00411   assert((r < rows()) && (c < columns()));
00412   row& rw = elements[r];
00413   typename row::iterator ri;
00414   for (ri = rw.begin(); (ri != rw.end()) && ((*ri).first < c); ++ri)
00415     /*nothing*/;
00416 
00417   if ((ri == rw.end()) || ((*ri).first != c)) {
00418     // Add new column to the row.
00419     ri = rw.insert(ri, vnl_sparse_matrix_pair<T>(c,T()));
00420   }
00421 
00422   return (*ri).second;
00423 }
00424 
00425 //------------------------------------------------------------
00426 //: Get the value of an entry in the matrix.
00427 template <class T>
00428 T vnl_sparse_matrix<T>::operator()(unsigned int r, unsigned int c) const
00429 {
00430   assert((r < rows()) && (c < columns()));
00431   row const& rw = elements[r];
00432   typename row::const_iterator ri = rw.begin();
00433   while (ri != rw.end() && (*ri).first < c)
00434     ++ri;
00435   if (ri == rw.end() || (*ri).first != c)
00436     return T(); // uninitialised value (default constructor) is returned
00437   else
00438     return (*ri).second;
00439 }
00440 
00441 //------------------------------------------------------------
00442 //: Get an entry in the matrix.
00443 //  This is the "const" version of operator().
00444 template <class T>
00445 T vnl_sparse_matrix<T>::get(unsigned int r, unsigned int c) const
00446 {
00447   assert((r < rows()) && (c < columns()));
00448   row const& rw = elements[r];
00449   typename row::const_iterator ri = rw.begin();
00450   while (ri != rw.end() && (*ri).first < c)
00451     ++ri;
00452   if (ri == rw.end() || (*ri).first != c)
00453     return T(); // uninitialised value (default constructor) is returned
00454   else
00455     return (*ri).second;
00456 }
00457 
00458 //------------------------------------------------------------
00459 //: Put (i.e., add or overwrite) an entry into the matrix.
00460 template <class T>
00461 void vnl_sparse_matrix<T>::put(unsigned int r, unsigned int c, T v)
00462 {
00463   assert((r < rows()) && (c < columns()));
00464   row& rw = elements[r];
00465   typename row::iterator ri = rw.begin();
00466   while (ri != rw.end() && (*ri).first < c)
00467     ++ri;
00468 
00469   if (ri == rw.end() || (*ri).first != c) {
00470     // Add new column to the row.
00471     rw.insert(ri, vnl_sparse_matrix_pair<T>(c,v));
00472   }
00473   else
00474     (*ri).second = v;
00475 }
00476 
00477 template <class T>
00478 void vnl_sparse_matrix<T>::diag_AtA(vnl_vector<T> & result) const
00479 {
00480   result.set_size( columns() );
00481   result.fill(T(0));
00482 
00483   typename vcl_vector<row>::const_iterator row_iter = elements.begin();
00484   for ( ; row_iter != elements.end(); ++row_iter) {
00485     row const& this_row = *row_iter;
00486     typename row::const_iterator col_iter = this_row.begin();
00487     for ( ; col_iter != this_row.end(); ++col_iter) {
00488       vnl_sparse_matrix_pair<T> const& entry = *col_iter;
00489       unsigned const col_id = entry.first;
00490       result[col_id] += entry.second * entry.second;
00491     }
00492   }
00493 }
00494 
00495 //------------------------------------------------------------
00496 //: Set row in the matrix.
00497 
00498 template <class T>
00499 vnl_sparse_matrix<T>&
00500 vnl_sparse_matrix<T>::set_row(unsigned int r,
00501                               vcl_vector<int> const& colz,
00502                               vcl_vector<T> const& vals)
00503 {
00504   assert (r < rows());
00505   assert (colz.size() == vals.size());
00506 
00507   row& rw = elements[r];
00508   if (rw.size() != colz.size()) rw = row(colz.size());
00509   for (unsigned int i=0; i < colz.size(); ++i)
00510     rw[i] = vnl_sparse_matrix_pair<T>(colz[i], vals[i]);
00511   typedef typename vnl_sparse_matrix_pair<T>::less less;
00512   vcl_sort(rw.begin(), rw.end(), less());
00513   return *this;
00514 }
00515 
00516 template <class T>
00517 vnl_sparse_matrix<T>&
00518 vnl_sparse_matrix<T>::vcat(vnl_sparse_matrix<T> const& A)
00519 {
00520   if (rs_ == 0) {
00521     rs_ = A.rs_;
00522     cs_ = A.cs_;
00523     elements = A.elements;
00524   }
00525   else {
00526     assert(cs_ == A.cs_);
00527     rs_ += A.rs_;
00528     elements.insert(elements.end(), A.elements.begin(), A.elements.end());
00529   }
00530   return *this;
00531 }
00532 
00533 
00534 //------------------------------------------------------------
00535 //: This is occasionally useful.  Sums a row of the matrix efficiently.
00536 template <class T>
00537 T vnl_sparse_matrix<T>::sum_row(unsigned int r)
00538 {
00539   assert(r < rows());
00540   row & rw = elements[r];
00541   T sum = T(0);
00542   for (typename row::iterator ri = rw.begin(); ri != rw.end(); ++ri)
00543     sum += (*ri).second;
00544 
00545   return sum;
00546 }
00547 
00548 template <class T>
00549 vnl_sparse_matrix<T>&
00550 vnl_sparse_matrix<T>::scale_row(unsigned int r, T scale)
00551 {
00552   assert(r < rows());
00553   row& rw = elements[r];
00554   for (typename row::iterator ri = rw.begin(); ri != rw.end(); ++ri)
00555     (*ri).second *= scale;
00556   return *this;
00557 }
00558 
00559 //------------------------------------------------------------
00560 //: Resizes the matrix so that it has r rows and c columns, clearing the current contents.
00561 //
00562 template <class T>
00563 void vnl_sparse_matrix<T>::set_size( int r, int c)
00564 {
00565   rs_ = r;
00566   cs_ = c;
00567   elements.resize(r);
00568   typename vnl_sparse_matrix_elements::iterator ie;
00569   for (ie = elements.begin(); ie != elements.end(); ++ie)
00570   {
00571     // just set matrix to 0
00572     ie->clear();
00573   }
00574   reset(); // reset iterator
00575 }
00576 
00577 //------------------------------------------------------------
00578 //: Resizes the matrix so that it has r rows and c columns, leaving the current contents.
00579 // This is more wasteful of resources than set_size, but it preserves the contents.
00580 //
00581 template <class T>
00582 void vnl_sparse_matrix<T>::resize( int r, int c)
00583 {
00584   unsigned int oldCs = cs_;
00585 
00586   rs_ = r;
00587   cs_ = c;
00588   elements.resize(r);
00589 
00590   // If the array has fewer columns now, we also need to cut them out
00591   if (oldCs > cs_) {
00592     for (unsigned int i = 0; i < elements.size(); ++i) {
00593       row& rw = elements[i];
00594       typename row::iterator iter;
00595       for (iter = rw.begin(); iter != rw.end() && (*iter).first<cs_ ; ++iter)
00596         /*nothing*/;
00597       if (iter != rw.end()) rw.erase(iter,rw.end());
00598     }
00599   }
00600 
00601   reset(); // reset iterator
00602 }
00603 
00604 //------------------------------------------------------------
00605 //: Resets the internal iterator
00606 template <class T>
00607 void vnl_sparse_matrix<T>::reset() const
00608 {
00609   itr_isreset = true;
00610   itr_row = 0;
00611 }
00612 
00613 //------------------------------------------------------------
00614 //: Moves the internal iterator to next non-zero entry in matrix.
00615 // Returns true if there is another value, false otherwise. Use
00616 // in combination with methods reset, getrow, getcolumn, and value.
00617 //
00618 template <class T>
00619 bool vnl_sparse_matrix<T>::next() const
00620 {
00621   if ( itr_row >= rows() )
00622     return false;
00623 
00624   if ( itr_isreset ) {
00625     // itr_cur is not pointing to an entry
00626     itr_row = 0;
00627     itr_isreset = false;
00628   }
00629   else {
00630     // itr_cur is pointing to an entry.
00631     // Try to move to next entry in current row.
00632     itr_cur++;
00633     if ( itr_cur != elements[itr_row].end() )
00634       return true;  // found next entry in current row
00635     else
00636       itr_row++;
00637   }
00638 
00639   // search for next entry starting at row itr_row
00640   while ( itr_row < rows() ) {
00641     itr_cur = elements[itr_row].begin();
00642     if ( itr_cur != elements[itr_row].end() )
00643       return true;
00644     else
00645       itr_row++;
00646   }
00647 
00648   return itr_row < rows();
00649 }
00650 
00651 //------------------------------------------------------------
00652 //: Returns the row of the entry pointed to by internal iterator.
00653 //
00654 template <class T>
00655 int vnl_sparse_matrix<T>::getrow() const
00656 {
00657   return itr_row;
00658 }
00659 
00660 //------------------------------------------------------------
00661 //: Returns the column of the entry pointed to by internal iterator.
00662 //
00663 template <class T>
00664 int vnl_sparse_matrix<T>::getcolumn() const
00665 {
00666   return (*itr_cur).first;
00667 }
00668 
00669 //------------------------------------------------------------
00670 //: Returns the value pointed to by the internal iterator.
00671 //
00672 template <class T>
00673 T vnl_sparse_matrix<T>::value() const
00674 {
00675   return (*itr_cur).second;
00676 }
00677 
00678 //------------------------------------------------------------
00679 //: Comparison
00680 //
00681 template <class T>
00682 bool vnl_sparse_matrix<T>::operator==(vnl_sparse_matrix<T> const& rhs) const
00683 {
00684   // first of all, sizes must match:
00685   if (rhs.rows() != rows() || rhs.columns() != columns()) {
00686 #ifdef DEBUG_SPARSE
00687     vcl_cerr << "Sizes are different: " << rows() << 'x' << columns() << ' ' << rhs.rows() << 'x' << rhs.columns() << '\n';
00688 #endif
00689     return false;
00690   }
00691 
00692   // Now, iterate over non-zero rows of this and of rhs.
00693   unsigned int row_id = 0;
00694   for (typename vcl_vector<row>::const_iterator row_iter = elements.begin();
00695        row_iter != elements.end();
00696        ++row_iter, ++row_id)
00697   {
00698     // Get the row from this matrix (lhs).
00699     row const& this_row = *row_iter;
00700 
00701     // Get the rhs row.
00702     row const& rhs_row = rhs.elements[row_id];
00703 
00704     // first of all, row sizes must match:
00705     if (rhs_row.size() != this_row.size())
00706       return false;
00707 
00708     // Iterate over the rhs row.
00709     for (typename row::const_iterator col_iter = rhs_row.begin();
00710          col_iter != rhs_row.end();
00711          ++col_iter)
00712     {
00713       // Get the element from the row.
00714       vnl_sparse_matrix_pair<T> const& entry = *col_iter;
00715       unsigned const col_id = entry.first;
00716 
00717       // So we are at (row_id,col_id) in rhs matrix.
00718       if (get(row_id,col_id) != entry.second)
00719         return false;
00720     }
00721   }
00722   // if we reach this point, all comparisons succeeded:
00723   return true;
00724 }
00725 
00726 //: Unary minus
00727 template <class T>
00728 vnl_sparse_matrix<T> vnl_sparse_matrix<T>::operator-() const
00729 {
00730   // The matrix to be returned:
00731   vnl_sparse_matrix<T> result(rows(), columns());
00732 
00733   // Iterate over non-zero rows of this matrix.
00734   unsigned int row_id = 0;
00735   for (typename vcl_vector<row>::const_iterator row_iter = elements.begin();
00736        row_iter != elements.end();
00737        ++row_iter, ++row_id)
00738   {
00739     // Get the row.
00740     row const& this_row = *row_iter;
00741 
00742     // Iterate over the row.
00743     for (typename row::const_iterator col_iter = this_row.begin();
00744          col_iter != this_row.end();
00745          ++col_iter)
00746     {
00747       // Assign the corresponding result element.
00748       vnl_sparse_matrix_pair<T> const& entry = *col_iter;
00749       result(row_id, entry.first) = - entry.second;
00750     }
00751   }
00752   return result;
00753 }
00754 
00755 //: addition
00756 template <class T>
00757 vnl_sparse_matrix<T> vnl_sparse_matrix<T>::operator+(vnl_sparse_matrix<T> const& rhs) const
00758 {
00759   vnl_sparse_matrix<T> result(rows(), columns());
00760   add(rhs, result);
00761   return result;
00762 }
00763 
00764 //: subtraction
00765 template <class T>
00766 vnl_sparse_matrix<T> vnl_sparse_matrix<T>::operator-(vnl_sparse_matrix<T> const& rhs) const
00767 {
00768   vnl_sparse_matrix<T> result(rows(), columns());
00769   subtract(rhs, result);
00770   return result;
00771 }
00772 
00773 //: multiplication
00774 template <class T>
00775 vnl_sparse_matrix<T> vnl_sparse_matrix<T>::operator*(vnl_sparse_matrix<T> const& rhs) const
00776 {
00777   vnl_sparse_matrix<T> result(rows(), rhs.columns());
00778   mult(rhs, result);
00779   return result;
00780 }
00781 
00782 //: in-place scalar multiplication
00783 template <class T>
00784 vnl_sparse_matrix<T>& vnl_sparse_matrix<T>::operator*=(T const& rhs)
00785 {
00786   // Iterate over non-zero rows of this matrix.
00787   for (typename vcl_vector<row>::iterator row_iter = elements.begin();
00788        row_iter != elements.end();
00789        ++row_iter)
00790   {
00791     // Get the row.
00792     row& this_row = *row_iter;
00793 
00794     // Iterate over the row.
00795     for (typename row::iterator col_iter = this_row.begin();
00796          col_iter != this_row.end();
00797          ++col_iter)
00798     {
00799       // Change the corresponding element.
00800       col_iter->second *= rhs;
00801     }
00802   }
00803   return *this;
00804 }
00805 
00806 //: in-place scalar division
00807 template <class T>
00808 vnl_sparse_matrix<T>& vnl_sparse_matrix<T>::operator/=(T const& rhs)
00809 {
00810   // Iterate over non-zero rows of this matrix.
00811   for (typename vcl_vector<row>::iterator row_iter = elements.begin();
00812        row_iter != elements.end();
00813        ++row_iter)
00814   {
00815     // Get the row.
00816     row& this_row = *row_iter;
00817 
00818     // Iterate over the row.
00819     for (typename row::iterator col_iter = this_row.begin();
00820          col_iter != this_row.end();
00821          ++col_iter)
00822     {
00823       // Change the corresponding element.
00824       col_iter->second /= rhs;
00825     }
00826   }
00827   return *this;
00828 }
00829 
00830 //: scalar multiplication
00831 template <class T>
00832 vnl_sparse_matrix<T> vnl_sparse_matrix<T>::operator*(T const& rhs) const
00833 {
00834   vnl_sparse_matrix<T> result = *this;
00835   return result *= rhs;
00836 }
00837 
00838 //: scalar division
00839 template <class T>
00840 vnl_sparse_matrix<T> vnl_sparse_matrix<T>::operator/(T const& rhs) const
00841 {
00842   vnl_sparse_matrix<T> result = *this;
00843   return result /= rhs;
00844 }
00845 
00846 //: in-place addition
00847 template <class T>
00848 vnl_sparse_matrix<T>& vnl_sparse_matrix<T>::operator+=(vnl_sparse_matrix<T> const& rhs)
00849 {
00850   return *this = operator+(rhs);
00851 }
00852 
00853 //: in-place subtraction
00854 template <class T>
00855 vnl_sparse_matrix<T>& vnl_sparse_matrix<T>::operator-=(vnl_sparse_matrix<T> const& rhs)
00856 {
00857   return *this = operator-(rhs);
00858 }
00859 
00860 //: in-place multiplication
00861 template <class T>
00862 vnl_sparse_matrix<T>& vnl_sparse_matrix<T>::operator*=(vnl_sparse_matrix<T> const& rhs)
00863 {
00864   return *this = operator*(rhs);
00865 }
00866 
00867 //: Make each row of the matrix have unit norm.
00868 // All-zero rows are ignored.
00869 template<class T>
00870 vnl_sparse_matrix<T>& vnl_sparse_matrix<T>::normalize_rows()
00871 {
00872   typedef typename vnl_numeric_traits<T>::abs_t Abs_t;
00873   typedef typename vnl_numeric_traits<T>::real_t Real_t;
00874   typedef typename vnl_numeric_traits<Real_t>::abs_t abs_real_t;
00875 
00876   // Iterate through the matrix rows, and normalize one at a time:
00877   for (typename vcl_vector<row>::iterator row_iter = elements.begin();
00878        row_iter != elements.end();
00879        ++row_iter)
00880   {
00881     // Get the row.
00882     row& this_row = *row_iter;
00883 
00884     Abs_t norm(0); // double will not do for all types.
00885 
00886     // Iterate over the row
00887     for (typename row::iterator col_iter = this_row.begin();
00888          col_iter != this_row.end();
00889          ++col_iter)
00890     {
00891       vnl_sparse_matrix_pair<T>& entry = *col_iter;
00892       norm += vnl_math_squared_magnitude(entry.second);
00893     }
00894     if (norm != 0) {
00895       abs_real_t scale = abs_real_t(1)/(vcl_sqrt((abs_real_t)norm));
00896       // Iterate again over the row
00897       for (typename row::iterator col_iter = this_row.begin();
00898            col_iter != this_row.end();
00899            ++col_iter)
00900       {
00901         vnl_sparse_matrix_pair<T>& entry = *col_iter;
00902         entry.second = T(Real_t(entry.second) * scale);
00903       }
00904     }
00905   }
00906   return *this;
00907 }
00908 
00909 //: Fill this matrix with 1s on the main diagonal and 0s elsewhere.
00910 template<class T>
00911 vnl_sparse_matrix<T>& vnl_sparse_matrix<T>::set_identity()
00912 {
00913   // Iterate through the matrix rows, and set one at a time:
00914   unsigned int rownum = 0;
00915   for (typename vcl_vector<row>::iterator row_iter = elements.begin();
00916        row_iter != elements.end() && rownum < cols();
00917        ++row_iter, ++rownum)
00918   {
00919     row& rw = *row_iter;
00920     rw.clear();
00921     rw[0] = vnl_sparse_matrix_pair<T>(rownum,T(1));
00922   }
00923   return *this;
00924 }
00925 
00926 //: returns a new sparse matrix, viz. the transpose of this
00927 template<class T>
00928 vnl_sparse_matrix<T> vnl_sparse_matrix<T>::transpose() const
00929 {
00930   vnl_sparse_matrix<T> result(cols(), rows());
00931   unsigned int rownum = 0; // row number in this matrix
00932   // iterate through the rows of this matrix,
00933   // and add every element thus found to the new result matrix
00934   for (typename vcl_vector<row>::const_iterator row_iter = elements.begin();
00935        row_iter != elements.end();
00936        ++row_iter, ++rownum)
00937   {
00938     row const& this_row = *row_iter;
00939     for (typename row::const_iterator col_iter = this_row.begin();
00940          col_iter != this_row.end();
00941          ++col_iter)
00942     {
00943       vnl_sparse_matrix_pair<T> entry = *col_iter; // new copy of element
00944       row& rw = result.elements[entry.first];
00945       entry.first = rownum; // modify element: its column number is now rownum
00946       rw.insert(rw.end(), entry); // insert at the end of the row
00947     }
00948   }
00949   return result;
00950 }
00951 
00952 //: returns a new sparse matrix, viz. the conjugate (or Hermitian) transpose of this
00953 template<class T>
00954 vnl_sparse_matrix<T> vnl_sparse_matrix<T>::conjugate_transpose() const
00955 {
00956   vnl_sparse_matrix<T> result(transpose());
00957   for (typename vcl_vector<row>::iterator row_iter = result.elements.begin();
00958        row_iter != result.elements.end();
00959        ++row_iter)
00960   {
00961     row& this_row = *row_iter;
00962     for (typename row::iterator col_iter = this_row.begin();
00963          col_iter != this_row.end();
00964          ++col_iter)
00965     {
00966       vnl_sparse_matrix_pair<T>& entry = *col_iter;
00967       entry.second = vnl_complex_traits<T>::conjugate(entry.second);
00968     }
00969   }
00970   return result;
00971 }
00972 
00973 #define VNL_SPARSE_MATRIX_INSTANTIATE(T) \
00974 template class vnl_sparse_matrix<T >
00975 
00976 #endif // vnl_sparse_matrix_txx_