This chapter describes issues common to all algorithms in the book, such as sparse matrix representation and computation, both sequential and parallel. The efficiency of most iterative methods in the book is primarily determined by the performance of the matrix-vector product code and therefore on the storage format of the matrix. Each chapter section addresses a different issue.

• 10.1 Sparse Matrix Storage Formats
• 10.2 Matrix-Vector and Matrix-Matrix Multiplications
• 10.3 Direct Linear Solvers
• 10.4 Iterative Linear Solvers
• 10.5 Parallelism

Section	Package Name	Language	Comments
10.2	BLAS sparse BLAS XBLAS	Fortran	library of basic linear algebra subprograms, documentation can be found in BLAST-FORUM
10.5	Chaco	FILLIN	graph partitioning software
10.5	METIS / ParMETIS	ANSI C	graph partitioning software
10.5	Aztec	FILLIN	parallel algorithm for distributed memory machine
10.5	PETSc		parallel algorithm for distributed memory machine
10.5	ScaLAPACK		parallel algorithms for dense and band matrices
10.5	various packages	various	parallel algorithms for sparse matrices see table 10.1 in section 10.3.3