G. A. Gravvanis
ABSTRACT
During the last decades, research efforts have been focused on the derivation of effective preconditioned iterative methods. The preconditioned iterative methods are mainly categorized into implicit preconditioned methods and explicit preconditioned methods. In this manuscript we review implicit preconditioned methods, based on incomplete and approximate factorization, and explicit preconditioned methods, based on sparse approximate inverses and explicit approximate inverses. Modified Moore-Penrose conditions are presented and theoretical estimates for the sensitivity of the explicit approximate inverse matrix of the explicit preconditioned method are derived. Finally, the performance of the preconditioned iterative methods is illustrated by solving characteristic 2D elliptic problem and numerical results are given indicating a qualitative agreement with the theoretical estimates.
- Axelsson, O. 1996. Iterative solution methods. Cambridge University Press. Google Scholar
Digital Library
- Benzi, M., Meyer, C. D., and Tuma, M. 1996. A sparse approximate inverse preconditioner for the conjugate gradient method. SIAM J. Sci. Comput. 17, 5, 1135--1149. Google ScholarDigital Library
- Benzi, M., Cullum, J., and Tuma, M. 2000. Robust approximate inverse preconditioning for the conjugate gradient method. SIAM J. Sci. Comput. 22, 4, 1318--1332. Google ScholarDigital Library
- Chan, T. F., and van der Vorst, H. A. 1997. Approximate and Incomplete Factorizations. In Parallel Numerical Algorithms. ICASE/LaRC Interdisciplinary Series in Science and Engineering, 4, Kluwer, 167--202.Google Scholar
- Evans, D. J. 1967. The use of preconditioning in iterative methods for solving linear equations with symmetric positive definite matrices. J. I. M. A. 4, 295--314.Google Scholar
- Evans, D. J., and Lipitakis, E. A. 1983. Implicit semi-direct methods based on root-free sparse factorization procedures. BIT 23, 194--208.Google ScholarCross Ref
- Evans, D. J., and Lipitakis, E. A. 1979. A sparse LU factorization procedure for the solution of parabolic differential equations. In Proc. of Inter. Conf. on Num. Math in Thermal Problems, Pineridge Press, 954--966.Google Scholar
- Filelis-Papadopoulos, C. K., and Gravvanis, G. A. 2013. On the multigrid method based on finite difference approximate inverses. Computer Modeling in Engineering & Sciences 90, 3, 233--253.Google Scholar
- Golub, G. H., and van Loan, C. 1996. Matrix Computations. The Johns Hopkins University Press.Google Scholar
- Greenbaum, A. 1997. Iterative methods for solving linear systems. SIAM. Google ScholarDigital Library
- Gravvanis, G. A. 2009. High Performance Inverse Preconditioning. Arch. of Comput. Meth. in Engin. 16, 1, 77--108.Google ScholarCross Ref
- Gravvanis, G. A. 2002. Explicit Approximate Inverse Preconditioning Techniques. Arch. of Comput. Meth. in Engin. 9, 4, 371--402.Google ScholarCross Ref
- Gravvanis, G. A. 2000. Generalized approximate inverse preconditioning for solving non-linear elliptic boundary-value problems. I. J. Appl. Math. 2, 11, 1363--1378.Google Scholar
- Gravvanis, G. A. 1996. The rate of convergence of explicit approximate inverse preconditioning. I. J. Comp. Math. 60, 77--89.Google ScholarCross Ref
- Gravvanis, G. A., Filelis-Papadopoulos, C. K., and Matskanidis, P. I. Algebraic multigrid methods based on Generic Approximate Inverse Matrix Techniques, TR/ECE/ASC-AMA/2012/13, submitted.Google Scholar
- Gravvanis, G. A., Filelis-Papadopoulos, C. K., Giannoutakis, K. M., and Lipitakis, E. A. 2013. A note on parallel finite difference approximate inverse preconditioning on multicore systems using POSIX threads. I. J. Comput. Meth. 10, 5.Google Scholar
- Gravvanis, G. A.; Filelis-Papadopoulos, C. K. and Lipitakis, E. A. 2012. A Note on the Comparison of a Class of Preconditioned Iterative Methods. In 16th Panhellenic Conference on Informatics (PCI) 2012, 204--210. Google ScholarDigital Library
- Grote, M. J., and Huckle, T. 1997. Parallel preconditioning with sparse approximate inverses. SIAM J. Sci. Comput. 18, 3, 838--853. Google ScholarDigital Library
- Grote, M. J., and Huckle, T. 1995. Effective Parallel Preconditioning with Sparse Approximate Inverses. In Proc. SIAM Conf. on Parallel Processing for Scientific Computing, SIAM, 466--471.Google Scholar
- Huckle, T. 1999. Approximate sparsity patterns for the inverse of a matrix and preconditioning. Appl. Numer. Math. 30, 291--303. Google ScholarDigital Library
- Lipitakis, E. A. 1986. Approximate root-free factorization for solving elliptic difference equations in three space variables. Linear Alg. Appl. 76, 247--269.Google ScholarCross Ref
- Lipitakis, E. A., and Evans, D. J. 1981. The rate of convergence of an approximate matrix factorization semi-direct method. Numer. Math. 36, 237--251.Google ScholarDigital Library
- Lipitakis, E. A., and Evans, D. J. 1987. Explicit semi-direct methods based on approximate inverse matrix techniques for solving boundary-value problems on parallel processors. Math. and Comput. in Simul. 29, 1--17. Google ScholarDigital Library
- Penrose, R. 1955. A Generalized Inverse for Matrices. Proc. Cambridge Phil. Soc. 51, 406--413.Google ScholarCross Ref
- Saad, Y. 1996. Iterative methods for sparse linear systems. PWS Publishing. Google ScholarDigital Library
- Saad, Y., and van der Vorst, H. A. 2000. Iterative solution of linear systems in the 20th century. J. Comp. Appl. Math. 123, 1--33. Google ScholarDigital Library
- Turing, A. M. 1948. Rounding-off errors in matrix processes. Q. J. Mech. Appl. Mat. 1, 287--308.Google ScholarCross Ref
- van der Vorst, H. A. 1992. Bi-CGSTAB: A fast and smoothly converging variant of Bi-CG for the solution of nonsymmetric linear systems. SIAM J. on Sci. and Stat. Comput. 13, 2, 631--644. Google ScholarDigital Library
- www.computational.unibas.ch/software/spai/spaidoc.html, Grote M, Hagemann M, SPAI - SParse Approximate Inverse Preconditioner.Google Scholar
Index Terms
- On numerical modeling performance of generalized preconditioned methods
Recommendations
A Note on the Comparison of a Class of Preconditioned Iterative Methods
PCI '12: Proceedings of the 2012 16th Panhellenic Conference on InformaticsThe preconditioned iterative methods are mainly categorized into implicit preconditioned methods and explicit preconditioned methods. In this manuscript we review implicit preconditioned methods, based on incomplete and approximate factorization, and ...
Preconditioning Highly Indefinite and Nonsymmetric Matrices
Standard preconditioners, like incomplete factorizations, perform well when the coefficient matrix is diagonally dominant, but often fail on general sparse matrices. We experiment with nonsymmetric permutations and scalings aimed at placing large entries ...
Computational experience with sequential and parallel, preconditioned Jacobi--Davidson for large, sparse symmetric matrices
The Jacobi-Davidson (JD) algorithm was recently proposed for evaluating a number of the eigenvalues of a matrix. JD goes beyond pure Krylov-space techniques; it cleverly expands its search space, by solving the so-called correction equation, thus in ...
Reviews
Maurice W. Benson
The efficient solution of large sparse linear systems is critical for many applications, such as the one focused on in this paper. The problem arises from the discretization of elliptic boundary value problems and has a matrix with a striped sparsity pattern. The authors examine preconditioners viewed as approximate inverses, in explicit (not factored) matrix form, that consequently provide highly parallel implementations. There are two difficulties with a direct lower and upper triangular (LU) factoring: factor fill in, and the sequential aspect of forward and back substitution. The former has been addressed for these implicit approximate inverses by dropping factor elements to maintain sparsity, while the latter remains unsolved. The major algorithm studied in this paper builds on approximate LU factors to create an explicit approximation for the inverse that is still sparse and just requires inherently parallel matrix vector products in its application. The authors compare this with another explicit approach using a highly parallel Frobenius norm minimization with an adaptation of sparsity to obtain an acceptable sparse approximate inverse. Experimentally, this Frobenius approach, which lacks information available in the approximate LU factors, is less effective. The report contains a sensitivity analysis that builds on earlier work and includes experiments demonstrating quality measures and timings using the preconditioned biconjugate gradient stabilized method. As the timings are for sequential processing, a more complete study awaits experiments using parallel configurations. This highly specialized material will be mainly of interest to readers working with parallel approaches for large sparse linear systems. Online Computing Reviews Service
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments