Skip to Main content Skip to Navigation

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 :
Complete list of metadatas
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:09:11 AM
Last modification on : Thursday, November 21, 2019 - 2:39:35 AM


Files produced by the author(s)


  • HAL Id : hal-02101893, version 1



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⟩



Record views


Files downloads