EDP Sciences Journals List
Advanced Search
Subscriber Authentication Point
Home All issues Volume 18 Article
Free access article

Issue ESAIM: Proc.
Volume 18, 2007
Paris-sud working group on modelling and scientific computing 2006-2007
Page(s) 70 - 86
DOI http://dx.doi.org/10.1051/proc:071807
Published online 12 September 2007

ESAIM: Proc., 2007, Vol. 18, pp. 70-86
DOI: 10.1051/proc:071807

Stochastic Matrices and Lp Norms : New Algorithms for Solving Ill-conditioned Linear Systems of Equations

Riadh Zorgati1, 2, Wim van Ackooij3 and Marc Lambert1

1  Supelec, Plateau de Moulon, 3 rue Joliot-Curie, F-91192 Gif-sur-Yvette Cedex FRANCE
2  EDF R&D. 1, avenue du Général de Gaulle, F-92141 Clamart Cedex FRANCE
3  EDF R&D. 1, avenue du Général de Gaulle, F-92141 Clamart Cedex FRANCE

riadh.zorgati@lss.supelec.fr
riadh.zorgati@edf.fr
wim.van-ackooij@edf.fr
marc.lambert@lss.supelec.fr

(Published online: 12 September 2007)

Abstract
We propose new iterative algorithms for solving a system of linear equations, possibly singular and inconsistent, presenting outstanding performances regarding ill-conditioning and error propagation. The basis of our approach is constructing with the l1 norm, a preconditioning matrix C (an approximation of a generalized inverse of the matrix) such that the preconditioned matrix CA is stochastic. This property allows us to retrieve, in an original way, the Schultz-Hotelling-Bodewig's algorithm of iterative refinement of the approximate inverse of a matrix. The approach, valid for non-negative matrices, is then generalized to any complex, rectangular matrix. We are then able to compute a generalized inverse of any matrix and this inverse is fit for use in classical solving schemes such as : Richardson-Tanabe, Schultz-Hotelling-Bodewig, preconditioned conjugate gradients and also in the Kaczmarz scheme (that we have generalized using lp norms). Regarding the obtained results on pathological well-known test-cases such as Hilbert and Nakasaka matrices, some of the proposed algorithms are empirically shown to be more efficient than the known classical techniques.


Key words: Linear system, stochastic matrix, norm, conditioning, Markov chain, generalized inverse.


© EDP Sciences, ESAIM 2007


What is OpenURL?

The OpenURL standard is a protocol for transmission of metadata describing the resource that you wish to access. An OpenURL link contains article metadata and directs it to the OpenURL server of your choice. The OpenURL server can provide access to the resource and also offer complementary services (specific search engine, export of references...). The OpenURL link can be generated by different means.
  • If your librarian has set up your subscription with an OpenURL resolver, OpenURL links appear automatically on the abstract pages.
  • You can define your own OpenURL resolver with your EDPS Account. In this case your choice will be given priority over that of your library.
  • You can use an add-on for your browser (Firefox or I.E.) to display OpenURL links on a page (see http://www.openly.com/openurlref/). You should disable this module if you wish to use the OpenURL server that you or your library have defined.