Direct methods for sparse matrices

✍ Scribed by Duff, Iain S.; Erisman, A. M.; Reid, John Ker

• Publisher: Oxford University Press
• Year: 2017
• Tongue: English
• Leaves: 451
• Series: Numerical methods and scientific computation
• Edition: 2
• Category: Library

✦ Synopsis

The subject of sparse matrices has its root in such diverse fields as management science, power systems analysis, surveying, circuit theory, and structural analysis. Efficient use of sparsity is a key to solving large problems in many fields. This book provides both insight and answers for those attempting to solve these problems.

Abstract:

The subject of sparse matrices has its root in such diverse fields as management science, power systems analysis, surveying, circuit theory, and structural analysis. Efficient use of sparsity is a key to solving large problems in many fields. This book provides both insight and answers for those attempting to solve these problems. Read more...

✦ Table of Contents

Content: Cover
Glossary of Symbols
Preface
Contents
1 Introduction
1.1 Introduction
1.2 Graph theory
1.3 Example of a sparse matrix
1.4 Modern computer architectures
1.5 Computational performance
1.6 Problem formulation
1.7 Sparse matrix test collections
2 Sparse matrices: storage schemes and simple operations
2.1 Introduction
2.2 Sparse vector storage
2.3 Inner product of two packed vectors
2.4 Adding packed vectors
2.5 Use of full-sized arrays
2.6 Coordinate scheme for storing sparse matrices
2.7 Sparse matrix as a collection of sparse vectors 2.8 Sherman's compressed index scheme2.9 Linked lists
2.10 Sparse matrix in column-linked list
2.11 Sorting algorithms
2.11.1 The counting sort
2.11.2 Heap sort
2.12 Transforming the coordinate scheme to other forms
2.13 Access by rows and columns
2.14 Supervariables
2.15 Matrix by vector products
2.16 Matrix by matrix products
2.17 Permutation matrices
2.18 Clique (or finite-element) storage
2.19 Comparisons between sparse matrix structures
3 Gaussian elimination for dense matrices: the algebraic problem
3.1 Introduction
3.2 Solution of triangular systems 3.3 Gaussian elimination3.4 Required row interchanges
3.5 Relationship with LU factorization
3.6 Dealing with interchanges
3.7 LU factorization of a rectangular matrix
3.8 Computational sequences, including blocking
3.9 Symmetric matrices
3.10 Multiple right-hand sides and inverses
3.11 Computational cost
3.12 Partitioned factorization
3.13 Solution of block triangular systems
4 Gaussian elimination for dense matrices: numerical considerations
4.1 Introduction
4.2 Computer arithmetic error
4.3 Algorithm instability
4.4 Controlling algorithm stability through pivoting 4.4.1 Partial pivoting4.4.2 Threshold pivoting
4.4.3 Rook pivoting
4.4.4 Full pivoting
4.4.5 The choice of pivoting strategy
4.5 Orthogonal factorization
4.6 Partitioned factorization
4.7 Monitoring the stability
4.8 Special stability considerations
4.9 Solving indefinite symmetric systems
4.10 Ill-conditioning: introduction
4.11 Ill-conditioning: theoretical discussion
4.12 Ill-conditioning: automatic detection
4.12.1 The LINPACK condition estimator
4.12.2 Hager's method
4.13 Iterative refinement
4.14 Scaling
4.15 Automatic scaling 4.15.1 Scaling so that all entries are close to one4.15.2 Scaling norms
4.15.3 I-matrix scaling
5 Gaussian elimination for sparse matrices: an introduction
5.1 Introduction
5.2 Numerical stability in sparse Gaussian elimination
5.2.1 Trade-offs between numerical stability and sparsity
5.2.2 Incorporating rook pivoting
5.2.3 2 x 2 pivoting
5.2.4 Other stability considerations
5.2.5 Estimating condition numbers in sparse computation
5.3 Orderings
5.3.1 Block triangular matrix
5.3.2 Local pivot strategies
5.3.3 Band and variable band ordering
5.3.4 Dissection

✦ Subjects

Sparse matrices;Data processing;MATHEMATICS;Algebra;Intermediate