Frontal solver
Encyclopedia
A frontal solver, due to Irons
is an approach to solving sparse linear systems
which is used extensively in finite element analysis. It is a variant of Gauss elimination that automatically avoids a large number of operations involving zero terms.
A frontal solver builds a LU
or Cholesky decomposition
of a sparse matrix given as the assembly of element matrices by assembling the matrix and eliminating equations only on a subset of elements at a time. This subset is called the front and it is essentially the transition region between the part of the system already finished and the part not touched yet. The whole sparse matrix is never created explicitly. Only parts of the matrix are assembled as they enter the front. Processing the front involves dense matrix operations, which use the CPU efficiently. In a typical implementation, only the front is in memory
, while the factors in the decomposition are written into files
. The element matrices are read from files or created as needed and discarded.
A multifrontal solver of Duff
and Reid is an improvement of the frontal solver that uses several independent fronts at the same time. The fronts can be worked on by different processors, which enables parallel computing
.
See for a monograph exposition.
Bruce Irons (engineer)
Bruce Irons was an engineer and mathematician, known for his fundamental contribution to the finite element method, including the patch test and the frontal solver....
is an approach to solving sparse linear systems
Sparse matrix
In the subfield of numerical analysis, a sparse matrix is a matrix populated primarily with zeros . The term itself was coined by Harry M. Markowitz....
which is used extensively in finite element analysis. It is a variant of Gauss elimination that automatically avoids a large number of operations involving zero terms.
A frontal solver builds a LU
LU decomposition
In linear algebra, LU decomposition is a matrix decomposition which writes a matrix as the product of a lower triangular matrix and an upper triangular matrix. The product sometimes includes a permutation matrix as well. This decomposition is used in numerical analysis to solve systems of linear...
or Cholesky decomposition
Cholesky decomposition
In linear algebra, the Cholesky decomposition or Cholesky triangle is a decomposition of a Hermitian, positive-definite matrix into the product of a lower triangular matrix and its conjugate transpose. It was discovered by André-Louis Cholesky for real matrices...
of a sparse matrix given as the assembly of element matrices by assembling the matrix and eliminating equations only on a subset of elements at a time. This subset is called the front and it is essentially the transition region between the part of the system already finished and the part not touched yet. The whole sparse matrix is never created explicitly. Only parts of the matrix are assembled as they enter the front. Processing the front involves dense matrix operations, which use the CPU efficiently. In a typical implementation, only the front is in memory
Computer memory
In computing, memory refers to the physical devices used to store programs or data on a temporary or permanent basis for use in a computer or other digital electronic device. The term primary memory is used for the information in physical systems which are fast In computing, memory refers to the...
, while the factors in the decomposition are written into files
Computer file
A computer file is a block of arbitrary information, or resource for storing information, which is available to a computer program and is usually based on some kind of durable storage. A file is durable in the sense that it remains available for programs to use after the current program has finished...
. The element matrices are read from files or created as needed and discarded.
A multifrontal solver of Duff
Iain S. Duff
Iain S. Duff is a British mathematician and computer scientist, known for his work in numerical methods and software for solving problem with sparse matrices, in particular the Harwell Subroutine Library. From 1986–2009 he was the Group Leader of Numerical Analysis at Harwell Laboratory, which...
and Reid is an improvement of the frontal solver that uses several independent fronts at the same time. The fronts can be worked on by different processors, which enables parallel computing
Parallel computing
Parallel computing is a form of computation in which many calculations are carried out simultaneously, operating on the principle that large problems can often be divided into smaller ones, which are then solved concurrently . There are several different forms of parallel computing: bit-level,...
.
See for a monograph exposition.