Computer Solution of Large Linear Systems

Introductory Material. Vector and matrices norms. Eigenvalues. Irreducibility and diagonal dominance. M--Matrices and generalizations. Splittings. Positive definite matrices. The graph of a matrix. Chebyshev polynomials Discretization methods for partial diffential equations. Eigenvalues and Fourier analysis. Floating point arithmetic. Vector and parallel computers. BLAS and LAPACK. Bibliographical comments. Gaussian elimination for general linear systems. Introduction to Gaussian elimination. Gaussian elimination without permutations. Gaussian elimination with permutations (partial piv- oting). Gaussian elimination with other pivoting strategies. Operation counts. Gaussian elimination for symmetric systems. The outer product algorithm. The bordering algorithm. The inner product algorithm. Coding the three factorization algorithms. Positive definite systems. Indefinite systems. Gaussian elimination for H-matrices. Block methods. Tridiagonal and block tridiagonal systems. Roundoff error analysis. Perturbation analysis. Scaling. Iterative refinement. Parallel solution of general linear systems. Bibliographical comments. Gaussian elimination for sparse linear systems. Introduction. The fill--in phenomenon. Graphs and fill--in for symmetric matrices. Characterization of the fill--in. Band and envelope numbering schemes for symmetric matrices. The Cuthill--McKee and reverse Cuthill--McKee orderings. Sloan's algorithm. Spectral schemes. The basic idea. The multilevel spectral algorithm. The Kumfert and Pothen hybrid algorithm. The Boman--Hendrickson multilevel algorithm. The minimum degree ordering. The nested dissection ordering. Generalization of dissection algorithms. General dissection algorithms. Graph bisection improvement techniques. The multisection algorithm. The multifrontal method. Non--symmetric sparse matrices. Numerical stability for sparse matrices. Parallel algorithms for sparse matrices. Bibliographical comments. Fast solvers for separable PDEs. Introduction. Fast Fourier Transform. The basics of the FFT. The complex FFT. The real transforms. FFT on vector and parallel computers. Stability of the FFT. Other algorithms. Double Fourier analysis. The Fourier/tridiagonal Method. The cyclic reduction method. The FACR(l) method. The capacitance matrix method. Bibliographical comments. Classical iterative methods. Introduction. The Jacobi method. The Gauss-Seidel method. The SOR Method. The SSOR method. Alternating direction methods. Richardson methods. Acceleration techniques. Stability of classical iterative methods. Bibliographical comments. The conjugate gradient and related methods.Meurant, G. is the author of 'Computer Solution of Large Linear Systems' with ISBN 9780444501691 and ISBN 044450169X.