Frontal solver

A frontal solver is an approach to solving sparse linear systems which is used extensively in finite element analysis.[1] Algorithms of this kind are variants of Gauss elimination that automatically avoids a large number of operations involving zero terms due to the fact that the matrix is only sparse.[2] The development of frontal solvers is usually considered as dating back to work by Bruce Irons.[3]

A frontal solver builds a LU or Cholesky decomposition of a sparse matrix. Frontal solvers start with one or a few diagonal entries of the matrix, then consider all of those diagonal entries that are coupled to the first set via off-diagonal entries, and so on. In the finite element context, these consecutive sets form "fronts" that march through the domain (and consequently through the matrix, if one were to permute rows and columns of the matrix in such a way that the diagonal entries are ordered by the wave they are part of). Processing the front involves dense matrix operations, which use the CPU efficiently.

Given that the elements of the matrix are only needed as the front marches through the matrix, it is possible (but not necessary) to provide matrix elements only as needed. For example, for matrices arising from the finite element method, one can structure 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. In this context, the whole sparse matrix is never created explicitly, though the decomposition of the matrix is stored. This approach was mainly used historically, when computers had little memory; in such implementations, 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. More modern implementations, running on computers with more memory, no longer use this approach and instead store both the original matrix and its decomposition entirely in memory.

A variation of frontal solvers is the multifrontal method that originates in work of Duff and Reid.[4] It 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[5] for a monograph exposition.

See also

References
  1. Renaud Sizaire, keyFE2 User Manual, 2005, Sec. I.4.2 Solving_linear_system online Archived October 8, 2006, at the Wayback Machine
  2. Hayrettin Kardestuncer, Ed. Finite Element Handbook.
  3. Irons, Bruce M. (1970). "A frontal solution program for finite element analysis". International Journal for Numerical Methods in Engineering. 2 (January/March): 5–32. Bibcode:1970IJNME...2....5I. doi:10.1002/nme.1620020104.
  4. I. S. Duff , J. K. Reid, The Multifrontal Solution of Indefinite Sparse Symmetric Linear, ACM Transactions on Mathematical Software (TOMS), v.9 n.3, p.302-325, Sept. 1983 DOI 10.1145/356044.356047
  5. Iain S Duff , Albert M Erisman , John K Reid, Direct methods for sparse matrices, Oxford University Press, Inc., New York, NY, 1986


This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.