|[eigen] Pull request for dense/sparse eigenvalues solvers|
[ Thread Index | Date Index | More lists.tuxfamily.org/eigen Archives ]
Today is the last day of our project, so we would like to submit our work to the community: https://bitbucket.org/ensigll/eigen/commits/b00952c146854c133ab3e7e7089fbb995832c612.
To recap the work we have done, we have implemented 4 modules:
- The power iteration solver module, which is functional on dense real matrices, and faster than the eigensolver when the number of requested eigenvalues is not too high. Convergence is also dependent on the magnitude ratio of the eigenvalues. As said in the documentation, precision cannot be pushed too far (6 significant digits at most). It only computes real eigenvalues.
- The Lanczos algorithm, which works on dense symmetric real matrices with any requested precision, but is quite slow compared to the eigensolver. It transforms the initial matrix into a tridiagonal similar matrix that allows the computation of the eigenvalues more easily. QR is then used to complete this computation.
- The Modified Gram-Schmidt module: it orthogonalizes the given rectangular sparse matrix with linearly independent columns, by reducing it into a Q * R decomposition, where Q is orthogonal and R is upper triangular. This module is efficient and reliable, it uses several primitives from the sparse module that were already implemented and optimized.
- The Sparse Block Lanczos process, which was our initial goal. It consists of two steps, just like the Lanczos algorithm:
1) It reduces the given real symmetric matrix to a block-tridiagonal matrix; the algorithm in itself works and manages to produce the wanted tridiagonal matrix. However, we are faced with a problem that we will not have time to solve: the random initialization of the sparse vector that gets the algorithm started is an issue. Indeed, we want to generate a random sparse matrix with a chosen rank (the highest divider of the number of columns of the matrix) to initialize the Block Lanczos algorithm. Our idea was to create a sparse matrix and use the reserve function to reserve room for a chosen number of non-zeros per column, and then fill the non-zeros randomly. But we have not managed to implement it using the existing functions. Do you have any suggestions to remedy this problem?
We have implemented a temporary solution to generate random matrices, but it is not efficient at all and quickly fixable.
When the initialization is successful though, the algorithm efficiently computes the block-tridiagonal matrix. We checked, thanks to the second step, that the tridiagonal was indeed similar to the initial matrix.
2) It computes the eigenvalues of the block-tridiagonal matrix. We implemented a solution with SparseQR, but it turns out this solution might not be the most efficient: SparseQR does not seem to benefit much from the tridiagonal structure of the matrix and the algorithm takes a very long time to compute the eigenvalues. We will not have time to implement another solution, but we researched the subject and it seems that a divide & conquer algorithm for eigenvalues might be more optimal.
It has been a pleasure and a challenge to work on this library, we feel that we have learned a great deal about template libraries, as well as linear algebra, and we certainly hope that our work will benefit you and the users of Eigen.
Imène, Bediss and Tristan.
|Mail converted by MHonArc 2.6.19+||http://listengine.tuxfamily.org/|