[eigen] Pull request for dense/sparse eigenvalues solvers |

[ Thread Index | Date Index | More lists.tuxfamily.org/eigen Archives ]

*To*: eigen@xxxxxxxxxxxxxxxxxxx*Subject*: [eigen] Pull request for dense/sparse eigenvalues solvers*From*: Tristan Sahel <tristan.sahel@xxxxxxxxx>*Date*: Tue, 17 Jun 2014 17:42:50 +0200*Cc*: Bediss CHERIF <Bediss.Cherif@xxxxxxxxxxxxxxxxxxxxxxx>, Imene TENDJAOUI <Imene.Tendjaoui@xxxxxxxxx>, Matthieu Moy <matthieu.moy@xxxxxxxxxxxxxxx>*Dkim-signature*: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=message-id:date:from:user-agent:mime-version:to:cc:subject :content-type; bh=6DwMsFMuZmEVYnbDNLzqXdYbt+C0DDzvzkeeyrmeE1s=; b=BeigyM1V2Pkv9YoF9pRmxhadOFRmtKlaYFujllyCv8Qk7LCeqNygKYvhgWBzrpsudh GEa1PJk8pAGicx98TJC7kPsSyL2tp7OKXXrSQFawd2W90PrL0pK3VoVx2HMERtmfaky9 ukQ/15FCv5ligCw4LMD1O8UHlJDb3coiet1pVc8vtCgKvUGkRYmduyJCc6Smb9tge0GV kpWoVz+C/SReE3mxVRlpq8e26WHRB+pgJWP/T2ql0R7Vc94fD4x6DOQMiAaMn3Gqvby6 4aZwsXhyBgq3vBxzgsTbOrmY/YtKTmUoCytUc27bAGcg+HJxdi5IVT7P9ANumyThQqn7 BK+w==

Hello, 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. Best regards, Imène, Bediss and Tristan. |

**Messages sorted by:**[ date | thread ]- Prev by Date:
**Re: [eigen] Bugs on bugzilla** - Next by Date:
**Re: [eigen] Bugs on bugzilla** - Previous by thread:
**[eigen] Allow standard linear algebra operations for quaternions (Bug 560)** - Next by thread:
**[eigen] Slowdown on MSVC 2013**

Mail converted by MHonArc 2.6.19+ | http://listengine.tuxfamily.org/ |