Efficient Matrix Preconditioners for Black Box Linear Algebra

Abstract : The main idea of the ``black box'' approach in exact linear algebra is to reduce matrix problems to the computation of minimum polynomials. In most cases preconditioning is necessary to obtain the desired result. Here, good preconditioners will be used to ensure geometrical / algebraic properties on matrices, rather than numerical ones, so we do not address a condition number. We offer a review of problems for which (algebraic) preconditioning is used, provide a bestiary of preconditioning problems, and discuss several preconditioner types to solve these problems. We include new conditioners, new analyses of preconditioner performance, and results on the relations among preconditioning problems and with linear algebra problems. Thus improvements are offered for the efficiency and applicability of preconditioners. The focus is on linear algebra problems over finite fields, but most results are valid for entries from arbitrary fields.
Document type :
Reports
Complete list of metadatas

https://hal-lara.archives-ouvertes.fr/hal-02101893
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:09:11 AM
Last modification on : Friday, September 20, 2019 - 5:16:01 PM

File

RR2001-05.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02101893, version 1

Collections

Citation

Lin Chen, W. Eberly, Erich Kaltofen, B.D. Saunders, W.J. Turner, et al.. Efficient Matrix Preconditioners for Black Box Linear Algebra. [Research Report] LIP RR-2001-05, Laboratoire de l'informatique du parallélisme. 2001, 2+18p. ⟨hal-02101893⟩

Share

Metrics

Record views

5

Files downloads

31