Sparse Matrix Technology

Sergio Pissanetzky

• Publisher: Academic Press
• Year: 2014
• Print ISBN: 9780125575805
• eBook ISBN: 9781483270401
• Topic: Mathematics
• Subtopic: Algebra
• Index: Mathematics

Sparse Matrix Technology presents the methods, concepts, ideas, and applications of sparse matrix technology. The text provides the fundamental methods, procedures, techniques, and applications of sparse matrix technology in software development. The book covers topics on storage schemes and computational techniques needed for sparse matrix technology; sparse matrix methods and algorithms for the direct solution of linear equations; and algorithms for different purposes connected with sparse matrix technology. Engineers, programmers, analysts, teachers, and students in the computer sciences will find the book interesting.

CHAPTER 1

Fundamentals

Publisher Summary

This chapter discusses certain computational techniques of sufficiently general use to be considered as fundamentals of sparse matrix technology. The chapter discusses structures and internal representations used for storing lists of numbers, graphs, and various types of sparse matrices and sparse block-partitioned matrices. Symbolic and numerical processing of sparse matrices and dynamic storage allocation are examined. Also, the computational algebra of sparse vectors is discussed, as a row of a sparse matrix is a sparse vector and most of sparse matrix algebra requires that operations be performed with sparse vectors. Sparse matrix technology frequently requires the storage and manipulation of lists of items, where “item” may be an integer number, a real or complex number, or an entity having a more complicated structure such as a matrix, an array or a vertex of a graph together with the corresponding edges or branching information. The selection of a storage scheme depends on the operations to be performed, as the effectiveness of a certain operation may vary widely from one storage scheme to another.

1.1. Introduction

1.2. Storage of arrays, lists, stacks and queues

1.3. Storage of lists of integers

1.4. Representation and storage of graphs

1.5. Diagonal storage of band matrices

1.6. Envelope storage of symmetric matrices

1.7. Linked sparse storage schemes

1.8. The sparse row-wise format

1.9. Ordered and unordered representations

1.10. Sherman’s compression

1.11. Storage of block-partitioned matrices

1.12. Symbolic processing and dynamic storage schemes

1.13. Merging sparse lists of integers

1.14. The multiple switch technique

1.15. Addition of sparse vectors with the help of an expanded real accumulator

1.16. Addition of sparse vectors with the help of an expanded integer array of pointers

1.17. Scalar product of two sparse vectors with the help of an array of pointers

1.1 Introduction

In this chapter we discuss certain computational techniques of sufficiently general use to be considered as Fundamentals of Sparse Matrix Technology. The chapter begins with a description of structures and internal representations used for storing lists of numbers, graphs, and various types of sparse matrices and sparse block-partitioned matrices. The aim is to introduce precisely those ideas which are relevant to the subject and to illustrate them with simple examples. Symbolic and numerical processing of sparse matrices and dynamic storage allocation are examined. Finally, the computational algebra of sparse vectors is discussed, since a row of a sparse matrix is a sparse vector and most of sparse matrix algebra requires that operations be performed with sparse vectors.

1.2 Storage of arrays, lists, stacks and queues

Sparse matrix technology frequently requires the storage and manipulation of lists of items, where “item” may be an integer number, a real or complex number, or an entity having a more complicated structure such as a matrix, an array or a vertex of a graph together with the corresponding edges or branching information. Examples of operations commonly performed with lists are: adding an item at the end of the list, deleting an item from the end of the list, inserting or deleting an item in the middle or at the beginning of the lis...

Table of contents

• Cover image
• Title page
• Table of Contents
• Copyright
• Preface
• Dedication
• Introduction
• Chapter 1: Fundamentals
• Chapter 2: Linear Algebraic Equations
• Chapter 3: Numerical Errors in Gauss Elimination
• Chapter 4: Ordering for Gauss Elimination: Symmetric Matrices
• Chapter 5: Ordering for Gauss Elimination: General Matrices
• Chapter 6: Sparse Eigenanalysis
• Chapter 7: Sparse Matrix Algebra
• Chapter 8: Connectivity and Nodal Assembly
• Chapter 9: General Purpose Algorithms
• References
• Subject Index