In engineering structural analysis, I need the solution for some linear systems involving the inverse of a large-scale sparse matrix. Therefore, we need speed up the solution of the inverse problem. Anyone who would like to suggest some literatures and opinion are encouraged to discuss them to me.
You don't...
Matrix inversion is very expensive and is less precise compared to other methods.
In standard structural analysis, your stiffness matrix should be symmetric positive definite: Do a Cholesky factorization and 2 substitutions.
If you are doing strange things, a LU decomposition and 2 substitutions is the way.
In 3D fem, your system size may easily become huge. In that case a PCG with an incomplete Cholesky preconditioner is usually the best.
You don't...
Matrix inversion is very expensive and is less precise compared to other methods.
In standard structural analysis, your stiffness matrix should be symmetric positive definite: Do a Cholesky factorization and 2 substitutions.
If you are doing strange things, a LU decomposition and 2 substitutions is the way.
In 3D fem, your system size may easily become huge. In that case a PCG with an incomplete Cholesky preconditioner is usually the best.
As stated by Zegard, one should not compute inverse of a sparse matrix because then it loses its sparsity benefit (because inverse may not be sparse). However, they can be solved efficiently by ILU decomposition or Krylov's method depending on the structure of the matrix. You may see some of our work (R C Mittal and Ahmad al Kurdi) on the topic.
Tomas is correct. PCG (preconditioned conjugate gradients) is the simplest method that works reasonably well. I don't use incomplete Cholesky preconditioner (but it is a fine place to start).
All you ever wanted to know and more is here:
http://caminos.udc.es/info/asignaturas/617/Bibliografia/TextosPDF/IterativeMethodsSparseLinearSystems.pdf
Youseff Saad is one of the gods of iterative methods.
For large sparse matrix inversion problems, some kind of regularization techniques are also in use. These are mostly used in determining the inverse covariance matrix in statistical modeling of graphical models. You can refer this paper. http://www.cs.utexas.edu/~pradeepr/paperz/invcov.pdf
Please avoid editing the question to a completely different topic. Now the answers and the question are unrelated and therefore less beneficial to others.
Dear Tomas,
Am I really editing the original question? Then really sorry. I thought the problem stated is very similar to what I have written...Both are inverting a matrix which is sparse...
Sorry for the inconvenience...
No no no no... I meant the original question. Now the question is asking about flops on substitutions and such.
Dear Zegard,
Sorry for this modification. I have now modifed it back.
Often the solution requires a matrix decomposition and uses the forward and back-substitution technique to implement the inverse problem. But there is very little literature discussing the operation counts (flops or computational cost) of a sparse matrix?
@Li Li: For sparse and large linear system of equations Ax=b, it is often adequate to use some Krylov subspace method (possibly with appropriate preconditioning); for instance, if the coefficient matrix A is SPD, then PCG will be your choice; if A is non-symmetric, then GMRES, BiCGSTAB etc. should be favored. All these algorithms have been incorporated in the newest MATLAB and a single line of command will meet your demand. If u are interested in detail of these algorithms, i refer to Y. Saad's monograph, as suggested by J. Perot.
For symmetric positive definite matrices, the MINRES method is also a very good candidate. Recently, M. Saunders published a paper with some results showing that MINRES can in some cases even be better than PCG.
Anyway, there are no exact flop counts available for such iterative solvers since it is unknown how much iterations they will require.
I agree with Tomas that you don't really want to invert the matrix. From what I understand pre-conditioning with Cholesky factorization and then using perhaps the conjugate gradient method (CGM) would be among the more efficient procedures to use. Wikipedia has a good description of CGM at https://en.wikipedia.org/wiki/Conjugate_gradient_method
After some discussions above, I believe the conjugate gradient method (CGM) is an efficient method to solve the linear structural or mechanical system in large-scaled problems. However, some questions confuse me.
What are the disadvantages to implement the CGM?
Why some famous softwares (e.g., MSC/Nastran) do not use the CGM to solve the structural problems of large-scaled engineering problems. Often matrix factorization are used in these famous softwares.
Can someone who would like to discuss these questions to me.
@Li Li: To my knowledge, direct methods (say, LU factorization) are generally suitable for small and dense linear system of equations (in the context of numerical linear algebra). However, the coefficient matrix arising from engineering/PDE etc. are often large and sparse. To save the computational cost/memory, therefore, iterative methods are often preferred (and often present to be the only approach). Algorithms incorporated in different softwares differ greatly which leads to varing efficiency; for instance, the newest MATLAB inclludes many state-of-the-art linear solvers including PCG, GMRES etc..
Dear Zhang
To my best knowledge, iterative linear solvers [e.g., preconditioned generalized minimum residual (GMRES), conjugate gradient method (CGM) or generalized conjugate residual (GCR) algorithm] are only suggest for the large-scaled problems since their are less robust than the matrix factorization approaches.
Iterative solvers need less demand than direct solvers on both computer memory and CPU times, and they are also more amenable to parallel processing. The robust problem may be the answer why some famous softwares choose the matrix factorization approaches instead of iterative methods.
Dear Dr. Ke Zhang
Thanks for this useful information on the packages. Of course, Krylov-based model reduced method is known as the modern reduced space method, and many researchers have paid attention to it. I wish it can be more robust so that it can be more often used in real engineering problems.
Most of the matrix factorization approaches are aimed at SPD matrix. What if it's an asymmetric problem?
@Xiaobai Li: In numerical linear albebra, the term 'matrix inverse' is used more for its analogy with the reciprocal in the scalar case; that is, we seldom have to compute explicitly the matrix inverse (say, by factorization). Instead, as I said elsewhere, the idea of solving linear system of equations is often adopted for 'computing' implicitly the inverse. For instance, suppose you need to compute A^{-1}b. A common practice is to sovle it from Az=b, where z is an approximation of A^{-1}b.
- Badges
- Science topic