In computational mathematics, a matrix-free method is an algorithm for solving a linear system of equations or an eigenvalue problem that does not store the coefficient matrix explicitly, but accesses the matrix by evaluating matrix-vector products. Such methods can be preferable when the matrix is so big that storing and manipulating it would cost a lot of memory and computing time, even with the use of methods for sparse matrices. Many iterative methods allow for a matrix-free implementation, including:
- the power method,
- the Lanczos algorithm,
- Locally Optimal Block Preconditioned Conjugate Gradient Method (LOBPCG),
- Wiedemann's coordinate recurrence algorithm, and
- the conjugate gradient method.
- Krylov subspace methods
Distributed solutions have also been explored using coarse-grain parallel software systems to achieve homogeneous solutions of linear systems.
It is generally used in solving non-linear equations like Euler's equations in computational fluid dynamics. Matrix-free conjugate gradient method has been applied in the non-linear elasto-plastic finite element solver. Solving these equations requires the calculation of the Jacobian which is costly in terms of CPU time and storage. To avoid this expense, matrix-free methods are employed. In order to remove the need to calculate the Jacobian, the Jacobian vector product is formed instead, which is in fact a vector itself. Manipulating and calculating this vector is easier than working with a large matrix or linear system.
References
- Langville, Amy N.; Meyer, Carl D. (2006), Google's PageRank and beyond: the science of search engine rankings, Princeton University Press, p. 40, ISBN 978-0-691-12202-1
- Coppersmith, Don (1993), "Solving linear equations over GF(2): Block Lanczos algorithm", Linear Algebra and Its Applications, 192: 33–60, doi:10.1016/0024-3795(93)90235-G
- Knyazev, Andrew V. (2001). "Toward the Optimal Preconditioned Eigensolver: Locally Optimal Block Preconditioned Conjugate Gradient Method". SIAM Journal on Scientific Computing. 23 (2): 517–541. Bibcode:2001SJSC...23..517K. CiteSeerX 10.1.1.34.2862. doi:10.1137/S1064827500366124.
- Wiedemann, D. (1986), "Solving sparse linear equations over finite fields" (PDF), IEEE Transactions on Information Theory, 32: 54–62, doi:10.1109/TIT.1986.1057137
- Lamacchia, B. A.; Odlyzko, A. M. (1991), "Solving Large Sparse Linear Systems Over Finite Fields", Advances in Cryptology – CRYPT0' 90, Lecture Notes in Computer Science, vol. 537, p. 109, doi:10.1007/3-540-38424-3_8, ISBN 978-3-540-54508-8
- Kaltofen, E.; Lobo, A. (1996), "Distributed Matrix-Free Solution of Large Sparse Linear Systems over Finite Fields", Algorithmica, vol. 24, no. 3–4, pp. 311–348, CiteSeerX 10.1.1.17.7470, doi:10.1007/PL00008266, S2CID 13305650
- Prabhune, Bhagyashree C.; Krishnan, Suresh (4 March 2020). "A fast matrix-free elasto-plastic solver for predicting residual stresses in additive manufacturing". Computer Aided Design. 123: 102829. doi:10.1016/j.cad.2020.102829.
| Numerical linear algebra | |
|---|---|
| Key concepts | |
| Problems | |
| Hardware | |
| Software | |
 | This applied mathematics–related article is a stub. You can help Misplaced Pages by expanding it. |