Probabilistic analysis of complex Gaussian elimination without pivoting (Q1827483)

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.