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 computer 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,
- Wiedemann's coordinate recurrence algorithm, and
- the conjugate gradient method.
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. 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.
- 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 (1991)
- ^ Wiedemann (1986)
- ^ LaMacchia; Odlyzko (1991)
- ^ Kaltofen, E.; Lobo, A. (1996), "Distributed Matrix-Free Solution of Large Sparse Linear Systems over Finite Fields", Algorithmica 24: 311–348, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.17.7470
Wikimedia Foundation. 2010.
Look at other dictionaries:
Matrix (mathematics) — Specific elements of a matrix are often denoted by a variable with two subscripts. For instance, a2,1 represents the element at the second row and first column of a matrix A. In mathematics, a matrix (plural matrices, or less commonly matrixes)… … Wikipedia
Matrix-assisted laser desorption/ionization — MALDI TOF mass spectrometer Matrix assisted laser desorption/ionization (MALDI) is a soft ionization technique used in mass spectrometry, allowing the analysis of biomolecules (biopolymers such as DNA, proteins, peptides and sugars) and large… … Wikipedia
Matrix mechanics — Quantum mechanics Uncertainty principle … Wikipedia
Multitrait-multimethod matrix — The multitrait multimethod (MTMM) matrix is an approach to examining Construct Validity developed by Campbell and Fiske(1959). There are six major considerations when examining a construct s validity through the MTMM matrix, which are as… … Wikipedia
Data Matrix — An example of a Data Matrix code, encoding the text: Wikipedia, the free encyclopedia Reading Data … Wikipedia
Ray transfer matrix analysis — (also known as ABCD matrix analysis) is a type of ray tracing technique used in the design of some optical systems, particularly lasers. It involves the construction of a ray transfer matrix which describes the optical system; tracing of a light… … Wikipedia
Data matrix (computer) — A Data Matrix code is a two dimensional matrix barcode consisting of black and white square modules arranged in either a square or rectangular pattern. The information to be encoded can be text or raw data. Usual data size is from a few bytes up… … Wikipedia
The Matrix Online — MxO redirects here. For the Japanese manga, see M×0. The Matrix Online Developer(s) Monolith Productions Publisher(s) … Wikipedia
Monte Carlo methods for electron transport — The Monte Carlo method for electron transport is a semiclassical Monte Carlo(MC) approach of modeling semiconductor transport. Assuming the carrier motion consists of free flights interrupted by scattering mechanisms, a computer is utilized to… … Wikipedia
Kernel (matrix) — In linear algebra, the kernel or null space (also nullspace) of a matrix A is the set of all vectors x for which Ax = 0. The kernel of a matrix with n columns is a linear subspace of n dimensional Euclidean space. The dimension… … Wikipedia