Generalized Gram–Schmidt Process: Its Analysis and Use in Preconditioning

Jiří Kopal
Pondělí 8. prosince 2014, 14:20 hodin
Místnost G4-MAT, 4. patro budovy G, kampus Husova (Univerzitní nám. 1410/1)
[Pozvánka v PDF]

Anotace

Many problems arising from mathematical modelling in science and technology lead to solving large and sparse systems of linear algebraic equations. Then a natural way to solve them is to use iterative methods based on Krylov subspaces such as the method of conjugate gradients. In order to be efficient, such methods often need good preconditioners.

We focus on a particular strategy to obtain such preconditioners based on the generalized Gram–Schmidt process. We study both its theoretical properties as well as algorithms to compute it approximately and use the resulting factors as preconditioners. In this way, the thesis couples together two different areas of numerical linear algebra, i.e., numerical analysis and computational mathematics that is more focused on real-world computations.

From the theoretical point of view, the generalized Gram–Schmidt process in exact arithmetic computes a factorization of the inverse of the corresponding matrix. In other words, it can be formally considered as a direct method. Here we prefer to see the process as an incomplete scheme that produces a factorized sparse approximate inverse of the matrix. The generalized Gram–Schmidt process was introduced in a couple of important classical papers. Its use as an incomplete scheme for computing approximate inverse preconditioning was proposed by Benzi et al. The incompleteness is achieved by a dropping strategy based on discarding entries that are in some sense small.

We analyze the generalized Gram–Schmidt process in finite precision arithmetic. This analysis is a continuation of the paper by Rozložník et al. (2012). For example, we extend the generalized Gram–Schmidt process by pivoting that enables an improvement of some error bounds. In particular, differences between componentwise and norm-wise error bounds are highlighted.

Both theoretical considerations as well as experimental observations lead to a new dropping technique that behaves similarly to rounding in finite precision arithmetic.

The new dropping technique introduced by Kopal et al. (2013) is studied more in detail and de-rived in a different way.
The main goal is to present a new dropping technique that may generally help to better understand the interplay between floating-point analysis and numerical aspects of preconditioning by incomplete decompositions.