# Fwd: [GSOC2015] uBLAS Matrix Solver Project

3 messages
Open this post in threaded view
|

## Fwd: [GSOC2015] uBLAS Matrix Solver Project

 Hi, My name is Raj and I am Phd student in Computer Graphics. I am interested in tackling the problem of uBLAS Matrix Solver and in order to write my proposal, I am looking for inputs for which of the following algorithms will be most useful for prospective users in boost-numeric library. Here is a categorical list of all the prospective ones which will bring uBLAS updated to other commercial libraries like Eigen/Armadillo. Please let me know your preferences.... David Bellot : As a potential mentor, do you have any specific additions or deletions for this list? This could also be useful for other candidates pursuing this project. DENSE SOLVERS AND DECOMPOSITION : 1) QR Decomposition - (Must have) For orthogonalization of column spaces and solutions to linear systems. (Bonus : Also rank revealing..) 2) Cholesky Decomposition - (Must have) For symmetric Positive Definite systems often encountered in PDE for FEM Systems... 3) Householder Method - Conversion to tridiagonal form for eigen solvers.   SPARSE SOLVERS AND PRECONDITIONERS : 1) Conjugate Gradient - (Must have) For symmetric Positive Definite systems, this is the kryvlov space method of choice. Both general and preconditioned variants need to be implemented for convergence issues.  2) BiCGSTAB (Needs introspection) - For non symmetric systems.. 3) Incomplete Cholesky Decomposition (Good to have) - For symmetric Positive definite sparse matrices, to be used as preconditioner as extension to (1) for preconditioned CG Methods ... 4) Jacobi Preconditioner (Must have) - As prerequisite for step(1).EIGEN DECOMPOSITION MODULES (ONLY FOR DENSE MODULES)**: 1) Symmetric Eigen Values - (Must have) Like SSYEV Module in Lapack - That is first reduction to a tridiagonal form using Householder then using QR Algorithm for Eigen Value computation. 2) NonSymmetric Eigen Values - (Good to have) Like SGEEV module in Lapack - using Schur decompositions as an intermediate step in the above algorithm. 3) Generalized Eigen Values - (needs introspection) I use this in my research a lot and its a good thing to have.. ** Computing Eigen Decomposition of sparse modules needs special robust numerical treatment using implicitly restarted arnoldi iterations and may be treated as optional extensions. _______________________________________________ ublas mailing list [hidden email] http://lists.boost.org/mailman/listinfo.cgi/ublasSent to: [hidden email]
 This is a good list of potential matrix operations. I would add a sparse LU decomposition also. For performance optimization on  sparse containers I would suggest to focus on the a couple  types in uBlas and not all of them (at least compressed_matrix). FYI most applications (like FEA for example) are using sparse matrices with dense vectors and combinations like sparse matrix/sparse vector are less important. Two more items you may want to consider: 1. It would really add value to your proposal to include examples or architectural considerations of how those would integrate with uBlas. Since uBlas promotes a functional style, the same would be appropriate for the solvers interface. The simpler the interface the better. 2. Consider implementing parallel implementations using std::thread (or whatever from C++11 is appropriate). 3. Callback control for larger systems so that the solver can signal its caller about it's progress, or for other control reasons (i.e. stopping the solver). This should not interfere with performance and should probably implemented using some sort of static dispatch so that the user can choose which version to use ( with or without callback functions). Please note that those callbacks should probably be implemented using std::function. Please take a look at the last years proposals on how to draft yours because laying down your ideas is as crucial as your intention and capabilities to implement them. Regards, Nasos On 03/06/2015 10:30 AM, Rajaditya Mukherjee wrote: Hi,  My name is Raj and I am Phd student in Computer Graphics. I am interested in tackling the problem of uBLAS Matrix Solver and in order to write my proposal, I am looking for inputs for which of the following algorithms will be most useful for prospective users in boost-numeric library. Here is a categorical list of all the prospective ones which will bring uBLAS updated to other commercial libraries like Eigen/Armadillo. Please let me know your preferences....  David Bellot : As a potential mentor, do you have any specific additions or deletions for this list? This could also be useful for other candidates pursuing this project.  DENSE SOLVERS AND DECOMPOSITION :  1) QR Decomposition - (Must have) For orthogonalization of column spaces and solutions to linear systems. (Bonus : Also rank revealing..)  2) Cholesky Decomposition - (Must have) For symmetric Positive Definite systems often encountered in PDE for FEM Systems...  3) Householder Method - Conversion to tridiagonal form for eigen solvers.    SPARSE SOLVERS AND PRECONDITIONERS :  1) Conjugate Gradient - (Must have) For symmetric Positive Definite systems, this is the kryvlov space method of choice. Both general and preconditioned variants need to be implemented for convergence issues.  2) BiCGSTAB (Needs introspection) - For non symmetric systems..  3) Incomplete Cholesky Decomposition (Good to have) - For symmetric Positive definite sparse matrices, to be used as preconditioner as extension to (1) for preconditioned CG Methods ...  4) Jacobi Preconditioner (Must have) - As prerequisite for step(1). EIGEN DECOMPOSITION MODULES (ONLY FOR DENSE MODULES)**:  1) Symmetric Eigen Values - (Must have) Like SSYEV Module in Lapack - That is first reduction to a tridiagonal form using Householder then using QR Algorithm for Eigen Value computation.  2) NonSymmetric Eigen Values - (Good to have) Like SGEEV module in Lapack - using Schur decompositions as an intermediate step in the above algorithm.  3) Generalized Eigen Values - (needs introspection) I use this in my research a lot and its a good thing to have..  ** Computing Eigen Decomposition of sparse modules needs special robust numerical treatment using implicitly restarted arnoldi iterations and may be treated as optional extensions. ```_______________________________________________ ublas mailing list [hidden email] http://lists.boost.org/mailman/listinfo.cgi/ublas Sent to: [hidden email]``` _______________________________________________ ublas mailing list [hidden email] http://lists.boost.org/mailman/listinfo.cgi/ublasSent to: [hidden email]
 HI Nasos, Thanks for your inputs and your valuable suggestions regarding the style. I have a few comments : 1) As a library which chooses to emulate BLAS and LAPACK fortran style libs with a header only format, I plan to emulate the API functionality of the existing implementations of lu solver. 2) I am not so sure about the parallel implementations. I think as per a previous suggestion, it will be more useful to apply bindings to High-Performance BLAS implementations like Intel-MKL which has platform specific parallelism optimized for the architecture. They will be faster than generic C++ std::threads implementations. 3) I plan to focus for now on the dense implementations for a matured eigensolver class. Sparse EigenSolvers are almost completely monopolized by ARPACK and it can be added as a optional time-available module.(Though I agree that it will be extremely useful specially for subspace FEA) Rajaditya Mukherjee 3rd Year Graduate Student Dept. of Computer Science and Engineering The Ohio State UniversityColumbus, Ohio Tel :- +1-(614)-271-4439 email :- [hidden email],[hidden email] On Mon, Mar 9, 2015 at 11:34 AM, Nasos Iliopoulos wrote: This is a good list of potential matrix operations. I would add a sparse LU decomposition also. For performance optimization on  sparse containers I would suggest to focus on the a couple  types in uBlas and not all of them (at least compressed_matrix). FYI most applications (like FEA for example) are using sparse matrices with dense vectors and combinations like sparse matrix/sparse vector are less important. Two more items you may want to consider: 1. It would really add value to your proposal to include examples or architectural considerations of how those would integrate with uBlas. Since uBlas promotes a functional style, the same would be appropriate for the solvers interface. The simpler the interface the better. 2. Consider implementing parallel implementations using std::thread (or whatever from C++11 is appropriate). 3. Callback control for larger systems so that the solver can signal its caller about it's progress, or for other control reasons (i.e. stopping the solver). This should not interfere with performance and should probably implemented using some sort of static dispatch so that the user can choose which version to use ( with or without callback functions). Please note that those callbacks should probably be implemented using std::function. Please take a look at the last years proposals on how to draft yours because laying down your ideas is as crucial as your intention and capabilities to implement them. Regards, Nasos On 03/06/2015 10:30 AM, Rajaditya Mukherjee wrote: Hi,  My name is Raj and I am Phd student in Computer Graphics. I am interested in tackling the problem of uBLAS Matrix Solver and in order to write my proposal, I am looking for inputs for which of the following algorithms will be most useful for prospective users in boost-numeric library. Here is a categorical list of all the prospective ones which will bring uBLAS updated to other commercial libraries like Eigen/Armadillo. Please let me know your preferences....  David Bellot : As a potential mentor, do you have any specific additions or deletions for this list? This could also be useful for other candidates pursuing this project.  DENSE SOLVERS AND DECOMPOSITION :  1) QR Decomposition - (Must have) For orthogonalization of column spaces and solutions to linear systems. (Bonus : Also rank revealing..)  2) Cholesky Decomposition - (Must have) For symmetric Positive Definite systems often encountered in PDE for FEM Systems...  3) Householder Method - Conversion to tridiagonal form for eigen solvers.    SPARSE SOLVERS AND PRECONDITIONERS :  1) Conjugate Gradient - (Must have) For symmetric Positive Definite systems, this is the kryvlov space method of choice. Both general and preconditioned variants need to be implemented for convergence issues.  2) BiCGSTAB (Needs introspection) - For non symmetric systems..  3) Incomplete Cholesky Decomposition (Good to have) - For symmetric Positive definite sparse matrices, to be used as preconditioner as extension to (1) for preconditioned CG Methods ...  4) Jacobi Preconditioner (Must have) - As prerequisite for step(1). EIGEN DECOMPOSITION MODULES (ONLY FOR DENSE MODULES)**:  1) Symmetric Eigen Values - (Must have) Like SSYEV Module in Lapack - That is first reduction to a tridiagonal form using Householder then using QR Algorithm for Eigen Value computation.  2) NonSymmetric Eigen Values - (Good to have) Like SGEEV module in Lapack - using Schur decompositions as an intermediate step in the above algorithm.  3) Generalized Eigen Values - (needs introspection) I use this in my research a lot and its a good thing to have..  ** Computing Eigen Decomposition of sparse modules needs special robust numerical treatment using implicitly restarted arnoldi iterations and may be treated as optional extensions. ```_______________________________________________ ublas mailing list [hidden email] http://lists.boost.org/mailman/listinfo.cgi/ublas Sent to: [hidden email]``` _______________________________________________ ublas mailing list [hidden email] http://lists.boost.org/mailman/listinfo.cgi/ublas Sent to: [hidden email] _______________________________________________ ublas mailing list [hidden email] http://lists.boost.org/mailman/listinfo.cgi/ublasSent to: [hidden email]