aboutsummaryrefslogtreecommitdiffhomepage
path: root/doc/TutorialSparse.dox
diff options
context:
space:
mode:
authorGravatar Gael Guennebaud <g.gael@free.fr>2009-02-04 09:44:44 +0000
committerGravatar Gael Guennebaud <g.gael@free.fr>2009-02-04 09:44:44 +0000
commit44a527dfa50ce9c473cbf1f446b8b6f406d4bc91 (patch)
treea0f045d2a4c22a38e08e1b1d1ce0e17e630898c7 /doc/TutorialSparse.dox
parentb0dd22cc7271523ba83d2bc8a85504b8445587b5 (diff)
* classify and sort the doxygen "related pages"
by tweaking the filename and adding 2 categories: Troubleshooting and Advanced * use the EXCLUDE_SYMBOLS to clean the class list (insteaded of a homemade bash script) * remove the broken "exemple list" * re-structure the unsupported directory as mentionned in the ML and integrate the doc as follow: - snippets of the unsupported directory are directly imported from the main snippets/CMakefile.txt (no need to duplicate code) - add a top level "Unsupported modules" group - unsupported modules have to defined their own sub group and nest it using \ingroup Unsupported_modules - then a pair of //@{ //@} will put everything in the submodule - this is just a proposal !
Diffstat (limited to 'doc/TutorialSparse.dox')
-rw-r--r--doc/TutorialSparse.dox240
1 files changed, 0 insertions, 240 deletions
diff --git a/doc/TutorialSparse.dox b/doc/TutorialSparse.dox
deleted file mode 100644
index a8bfe006e..000000000
--- a/doc/TutorialSparse.dox
+++ /dev/null
@@ -1,240 +0,0 @@
-namespace Eigen {
-
-/** \page TutorialSparse Tutorial - Getting started with the sparse module
- \ingroup Tutorial
-
-<div class="eimainmenu">\ref index "Overview"
- | \ref TutorialCore "Core features"
- | \ref TutorialGeometry "Geometry"
- | \ref TutorialAdvancedLinearAlgebra "Advanced linear algebra"
- | \b Sparse \b matrix
-</div>
-
-\b Table \b of \b contents \n
- - \ref TutorialSparseIntro
- - \ref TutorialSparseFilling
- - \ref TutorialSparseFeatureSet
- - \ref TutorialSparseDirectSolvers
-<hr>
-
-\section TutorialSparseIntro Sparse matrix representations
-
-In many applications (e.g., finite element methods) it is common to deal with very large matrices where only a few coefficients are different than zero. Both in term of memory consumption and performance, it is fundamental to use an adequate representation storing only nonzero coefficients. Such a matrix is called a sparse matrix.
-
-\b Declaring \b sparse \b matrices \b and \b vectors \n
-The SparseMatrix class is the main sparse matrix representation of the Eigen's sparse module which offers high performance, low memory usage, and compatibility with most of sparse linear algebra packages. Because of its limited flexibility, we also provide a DynamicSparseMatrix variante taillored for low-level sparse matrix assembly. Both of them can be either row major or column major:
-
-\code
-#include <Eigen/Sparse>
-SparseMatrix<std::complex<float> > m1(1000,2000); // declare a 1000x2000 col-major compressed sparse matrix of complex<float>
-SparseMatrix<double,RowMajor> m2(1000,2000); // declare a 1000x2000 row-major compressed sparse matrix of double
-DynamicSparseMatrix<std::complex<float> > m1(1000,2000); // declare a 1000x2000 col-major dynamic sparse matrix of complex<float>
-DynamicSparseMatrix<double,RowMajor> m2(1000,2000); // declare a 1000x2000 row-major dynamic sparse matrix of double
-\endcode
-
-Although a sparse matrix could also be used to represent a sparse vector, for that purpose it is better to use the specialized SparseVector class:
-\code
-SparseVector<std::complex<float> > v1(1000); // declare a column sparse vector of complex<float> of size 1000
-SparseVector<double,RowMajor> v2(1000); // declare a row sparse vector of double of size 1000
-\endcode
-Note that here the size of a vector denotes its dimension and not the number of nonzero coefficients which is initially zero (like sparse matrices).
-
-
-\b Overview \b of \b the \b internal \b sparse \b storage \n
-In order to get the best of the Eigen's sparse objects, it is important to have a rough idea of the way they are internally stored. The SparseMatrix class implements the common and generic Compressed Column/Row Storage scheme. It consists of three compact arrays storing the values with their respective inner coordinates, and pointer indices to the begining of each outer vector. For instance, let \c m be a column-major sparse matrix. Then its nonzero coefficients are sequentially stored in memory in a column-major order (\em values). A second array of integer stores the respective row index of each coefficient (\em inner \em indices). Finally, a third array of integer, having the same length than the number of columns, stores the index in the previous arrays of the first element of each column (\em outer \em indices).
-
-Here is an example, with the matrix:
-<table>
-<tr><td>0</td><td>3</td><td>0</td><td>0</td><td>0</td></tr>
-<tr><td>22</td><td>0</td><td>0</td><td>0</td><td>17</td></tr>
-<tr><td>7</td><td>5</td><td>0</td><td>1</td><td>0</td></tr>
-<tr><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr>
-<tr><td>0</td><td>0</td><td>14</td><td>0</td><td>8</td></tr>
-</table>
-
-and its internal representation using the Compressed Column Storage format:
-<table>
-<tr><td>Values:</td> <td>22</td><td>7</td><td>3</td><td>5</td><td>14</td><td>1</td><td>17</td><td>8</td></tr>
-<tr><td>Inner indices:</td> <td> 1</td><td>2</td><td>0</td><td>2</td><td> 4</td><td>2</td><td> 1</td><td>4</td></tr>
-</table>
-Outer indices:<table><tr><td>0</td><td>2</td><td>4</td><td>5</td><td>6</td><td>\em 7 </td></tr></table>
-
-As you can guess, here the storage order is even more important than with dense matrix. We will therefore often make a clear difference between the \em inner and \em outer dimensions. For instance, it is easy to loop over the coefficients of an \em inner \em vector (e.g., a column of a column-major matrix), but completely inefficient to do the same for an \em outer \em vector (e.g., a row of a col-major matrix).
-
-The SparseVector class implements the same compressed storage scheme but, of course, without any outer index buffer.
-
-Since all nonzero coefficients of such a matrix are sequentially stored in memory, random insertion of new nonzeros can be extremely costly. To overcome this limitation, Eigen's sparse module provides a DynamicSparseMatrix class which is basically implemented as an array of SparseVector. In other words, a DynamicSparseMatrix is a SparseMatrix where the values and inner-indices arrays have been splitted into multiple small and resizable arrays. Assuming the number of nonzeros per inner vector is relatively low, this slight modification allow for very fast random insertion at the cost of a slight memory overhead and a lost of compatibility with other sparse libraries used by some of our highlevel solvers. Note that the major memory overhead comes from the extra memory preallocated by each inner vector to avoid an expensive memory reallocation at every insertion.
-
-To summarize, it is recommanded to use a SparseMatrix whenever this is possible, and reserve the use of DynamicSparseMatrix for matrix assembly purpose when a SparseMatrix is not flexible enough. The respective pro/cons of both representations are summarized in the following table:
-
-<table>
-<tr><td></td> <td>SparseMatrix</td><td>DynamicSparseMatrix</td></tr>
-<tr><td>memory usage</td><td>***</td><td>**</td></tr>
-<tr><td>sorted insertion</td><td>***</td><td>***</td></tr>
-<tr><td>random insertion \n in sorted inner vector</td><td>**</td><td>**</td></tr>
-<tr><td>sorted insertion \n in random inner vector</td><td>-</td><td>***</td></tr>
-<tr><td>random insertion</td><td>-</td><td>**</td></tr>
-<tr><td>coeff wise unary operators</td><td>***</td><td>***</td></tr>
-<tr><td>coeff wise binary operators</td><td>***</td><td>***</td></tr>
-<tr><td>matrix products</td><td>***</td><td>**(*)</td></tr>
-<tr><td>transpose</td><td>**</td><td>***</td></tr>
-<tr><td>redux</td><td>***</td><td>**</td></tr>
-<tr><td>*= scalar</td><td>***</td><td>**</td></tr>
-<tr><td>Compatibility with highlevel solvers \n (TAUCS, Cholmod, SuperLU, UmfPack)</td><td>***</td><td>-</td></tr>
-</table>
-
-
-\b Matrix \b and \b vector \b properties \n
-
-Here mat and vec represents any sparse-matrix and sparse-vector types respectively.
-
-<table>
-<tr><td>Standard \n dimensions</td><td>\code
-mat.rows()
-mat.cols()\endcode</td>
-<td>\code
-vec.size() \endcode</td>
-</tr>
-<tr><td>Sizes along the \n inner/outer dimensions</td><td>\code
-mat.innerSize()
-mat.outerSize()\endcode</td>
-<td></td>
-</tr>
-<tr><td>Number of non \n zero coefficiens</td><td>\code
-mat.nonZeros() \endcode</td>
-<td>\code
-vec.nonZeros() \endcode</td></tr>
-</table>
-
-
-\b Iterating \b over \b the \b nonzero \b coefficients \n
-
-Iterating over the coefficients of a sparse matrix can be done only in the same order than the storage order. Here is an example:
-<table>
-<tr><td>
-\code
-SparseMatrixType mat(rows,cols);
-for (int k=0; k\<m1.outerSize(); ++k)
- for (SparseMatrixType::InnerIterator it(mat,k); it; ++it)
- {
- it.value();
- it.row(); // row index
- it.col(); // col index (here it is equal to k)
- it.index(); // inner index, here it is equal to it.row()
- }
-\endcode
-</td><td>
-\code
-SparseVector<double> vec(size);
-for (SparseVector<double>::InnerIterator it(vec); it; ++it)
-{
- it.value(); // == vec[ it.index() ]
- it.index();
-}
-\endcode
-</td></tr>
-</table>
-
-
-\section TutorialSparseFilling Filling a sparse matrix
-
-A DynamicSparseMatrix object can be set and updated just like any dense matrix using the coeffRef(row,col) method. If the coefficient is not stored yet, then it will be inserted in the matrix. Here is an example:
-\code
-DynamicSparseMatrix<float> aux(1000,1000);
-for (...)
- for each i
- for each j interacting with i
- aux.coeffRef(i,j) += foo(o1,o2);
-SparseMatrix<float> mat(aux); // convert the DynamicSparseMatrix to a SparseMatrix
-\endcode
-
-Sometimes, however, we simply want to set all the coefficients of a matrix before using it through standard matrix operations (addition, product, etc.). In that case it faster to use the low-level startFill()/fill()/fillrand()/endFill() interface. Even though this interface is availabe for both sparse matrix types, their respective restrictions slightly differ from one representation to the other. In all case, a call to startFill() set the matrix to zero, and the fill*() functions will fail if the coefficient already exist.
-
-As a first difference, for SparseMatrix, the fill*() functions can only be called inside a startFill()/endFill() pair, and no other member functions are allowed during the filling process, i.e., until endFill() has been called. On the other hand, a DynamicSparseMatrix is always in a stable state, and the startFill()/endFill() functions are only for compatibility purpose.
-
-Another difference is that the fill*() functions must be called with increasing outer indices for a SparseMatrix, while they can be random for a DynamicSparseMatrix.
-
-Finally, the fill() function assumes the coefficient are inserted in a sorted order per inner vector, while the fillrand() variante allows random insertions (the outer indices must still be sorted for SparseMatrix).
-
-Some examples:
-
-1 - If you can set the coefficients in exactly the same order that the storage order, then the matrix can be filled directly and very efficiently. Here is an example initializing a random, row-major sparse matrix:
-\code
-SparseMatrix<double,RowMajor> m(rows,cols);
-m.startFill(rows*cols*percent_of_non_zero); // estimate of the number of nonzeros (optional)
-for (int i=0; i\<rows; ++i)
- for (int j=0; j\<cols; ++j)
- if (rand()\<percent_of_non_zero)
- m.fill(i,j) = rand();
-m.endFill();
-\endcode
-
-2 - If you can set each outer vector in a consistent order, but do not have sorted data for each inner vector, then you can use fillrand() instead of fill():
-\code
-SparseMatrix<double,RowMajor> m(rows,cols);
-m.startFill(rows*cols*percent_of_non_zero); // estimate of the number of nonzeros (optional)
-for (int i=0; i\<rows; ++i)
- for (int k=0; k\<cols*percent_of_non_zero; ++k)
- m.fillrand(i,rand(0,cols)) = rand();
-m.endFill();
-\endcode
-The fillrand() function performs a sorted insertion into an array sequentially stored in memory and requires a copy of all coefficients stored after its target position. This method is therefore reserved for matrices having only a few elements per row/column (up to 50) and works better if the insertion are almost sorted.
-
-3 - Eventually, if none of the above solution is practicable for you, then you have to use a RandomSetter which temporarily wraps the matrix into a more flexible hash map allowing complete random accesses:
-\code
-SparseMatrix<double,RowMajor> m(rows,cols);
-{
- RandomSetter<SparseMatrix<double,RowMajor> > setter(m);
- for (int k=0; k\<cols*rows*percent_of_non_zero; ++k)
- setter(rand(0,rows), rand(0,cols)) = rand();
-}
-\endcode
-The matrix \c m is set at the destruction of the setter, hence the use of a nested block. This imposed syntax has the advantage to emphasize the critical section where m is not valid and cannot be used.
-
-
-\section TutorialSparseFeatureSet Supported operators and functions
-
-In the following \em sm denote a sparse matrix, \em sv a sparse vector, \em dm a dense matrix, and \em dv a dense vector.
-In Eigen's sparse module we chose to expose only the subset of the dense matrix API which can be efficiently implemented. Moreover, all combinations are not always possible. For instance, it is not possible to add two sparse matrices having two different storage order. On the other hand it is perfectly fine to evaluate a sparse matrix/expression to a matrix having a different storage order:
-\code
-SparseMatrixType sm1, sm2, sm3;
-sm3 = sm1.transpose() + sm2; // invalid
-sm3 = SparseMatrixType(sm1.transpose()) + sm2; // correct
-\endcode
-
-Here are some examples of the supported operations:
-\code
-s_1 *= 0.5;
-sm4 = sm1 + sm2 + sm3; // only if s_1, s_2 and s_3 have the same storage order
-sm3 = sm1 * sm2;
-dv3 = sm1 * dv2;
-dm3 = sm1 * dm2;
-dm3 = dm2 * sm1;
-sm3 = sm1.cwise() * sm2; // only if s_1 and s_2 have the same storage order
-dv2 = sm1.marked<UpperTriangular>().solveTriangular(dv2);
-\endcode
-
-The product of a sparse matrix A time a dense matrix/vector dv with A symmetric can be optimized by telling that to Eigen:
-\code
-res = A.marked<SeflAdjoint>() * dv; // if all coefficients of A are stored
-res = A.marked<SeflAdjoint|UpperTriangular>() * dv; // if only the upper part of A is stored
-res = A.marked<SeflAdjoint|LowerTriangular>() * dv; // if only the lower part of A is stored
-\endcode
-
-
-\section TutorialSparseDirectSolvers Using the direct solvers
-
-TODO
-
-\subsection TutorialSparseDirectSolvers_LLT LLT
-Cholmod, Taucs.
-
-\subsection TutorialSparseDirectSolvers_LDLT LDLT
-
-
-\subsection TutorialSparseDirectSolvers_LU LU
-SuperLU, UmfPack.
-
-*/
-
-}