Probabilistic analysis of complex Gaussian elimination without pivoting

DOI10.1016/J.LAA.2004.01.005MaRDI QIDQ1827483zbMATH OpenOpenAlexFDO

Publication date 6 August 2004

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.laa.2004.01.005

density function Gaussian elimination Gaussian matrix growth factor LU factorization numerical results numerical stability Pivot probabilistic analysis Schur complement

Mathematics Subject Classification ID

Probabilistic methods, stochastic differential equations (65C99) Direct numerical methods for linear systems and matrix inversion (65F05)

Review text

The material is intended to the probabilistic analysis of Gaussian elimination (GE) without pivoting, applied to complex Gaussian matrices \(X\in \mathbb{C}^{n\times n}\). The technique used is the following: one starts from the Schur complement and simplifies the expression by repeatedly using the property that the normal distribution does not change under an orthogonal transformation. The first section is an introduction concerning the most general method for solving an \(n\times n\) square, dense, unstructured linear system \(Ax= b\), which is the Gaussian elimination. The second section is devoted to the notations which are used throughout the paper. In the third section one explores the independence among the elements of the \(U\) factor, where \(X= LU\), \(L\) being a unit lower triangular matrix and \(U\) being an upper triangular matrix, be the \(LU\) factorization of \(X\). The first thing presented, is a result which allows us to decompose the matrix \(U\) such as: \(U= \Phi H\), \(\Phi\) being an \(n\times n\) diagonal matrix and \(H\) an \(n\times n\) upper triangular one. Then, one derives the density functions of the elements \(u_{pp}(p\leq q)\) of \(U\). In section four, similar to the derivation of the density functions of \(u_{pq}(p\leq q)\), one establish the density functions of the elements \(l_{pq}(p> q)\) of \(L\). There is a result presented concerning the decomposition of the matrix \(L\) on the form \(L= \Xi\Psi^{-1}\), \(\Psi\) being an \(n\times n\) diagonal matrix and \(\Xi\) being an \(n\times n\) lower triangular matrix. Section five contains the analysis of the probability of small pivots. One proves that the probability of the occurrence of a pivot less than \(\varepsilon\) in magnitude is \(O(\varepsilon^2)\). In the sixth section one derives bounds on the probabilities of large growth factors \(\rho_L=\| L\|_\infty\) and \(\rho_U=\| U\|_\infty/\| A\|_\infty\) for a linear system \(Ax=b\). In particular one obtains that \[ \text{Pr}\,ob(\| L\|_\infty > r)=O(n^2(\ln r)^2/r^2)\text{ and }\text{Pr}\,ob(\| U\|_\infty/\| A\|_\infty > r)=O(n^2/r^2) \] which further imply that the expected values \(E(\| L\|_\infty)=O(n\ln n)\) and \(E(\| U\|_\infty/\| A\|_\infty)=O(n)\). Within section seven there are presented numerical results, performed in MATLAB 6.1.0.450. The eight section contains some discussions made on relating the theoretical results to the crucial practical problems of numerical stability.

Recommendations

Cites work

Cited in

(9)

Describes a project that uses

Uses Software

This page was built for publication: Probabilistic analysis of complex Gaussian elimination without pivoting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1827483)