*Rob H. Bisseling*

- Published in print:
- 2004
- Published Online:
- September 2007
- ISBN:
- 9780198529392
- eISBN:
- 9780191712869
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198529392.003.0004
- Subject:
- Mathematics, Applied Mathematics

This chapter introduces irregular algorithms and presents the example of multiplying a sparse matrix with a vector, which is the central operation in iterative solvers for linear systems and ...
More

This chapter introduces irregular algorithms and presents the example of multiplying a sparse matrix with a vector, which is the central operation in iterative solvers for linear systems and eigensystems. The irregular sparsity pattern of the matrix does not change during the multiplication, and the multiplication may be repeated many times with the same matrix. This justifies putting a lot of effort in finding good data distribution for a parallel multiplication. A useful non-Cartesian matrix distribution called the Mondriaan distribution is introduced, and an algorithm for finding such a distribution for a general sparse matrix is studied. Several special types of matrices are analyzed, such as random sparse matrices and Laplacian matrices. The program of this chapter demonstrates the use of the bulk synchronous message passing primitives from BSPlib, which were designed to facilitate irregular computations.Less

This chapter introduces irregular algorithms and presents the example of multiplying a sparse matrix with a vector, which is the central operation in iterative solvers for linear systems and eigensystems. The irregular sparsity pattern of the matrix does not change during the multiplication, and the multiplication may be repeated many times with the same matrix. This justifies putting a lot of effort in finding good data distribution for a parallel multiplication. A useful non-Cartesian matrix distribution called the Mondriaan distribution is introduced, and an algorithm for finding such a distribution for a general sparse matrix is studied. Several special types of matrices are analyzed, such as random sparse matrices and Laplacian matrices. The program of this chapter demonstrates the use of the bulk synchronous message passing primitives from BSPlib, which were designed to facilitate irregular computations.

*Rob H. Bisseling*

- Published in print:
- 2004
- Published Online:
- September 2007
- ISBN:
- 9780198529392
- eISBN:
- 9780191712869
- Item type:
- book

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198529392.001.0001
- Subject:
- Mathematics, Applied Mathematics

This book explains the use of the bulk synchronous parallel (BSP) model and the BSPlib communication library in parallel algorithm design and parallel programming. The main topics treated in the book ...
More

This book explains the use of the bulk synchronous parallel (BSP) model and the BSPlib communication library in parallel algorithm design and parallel programming. The main topics treated in the book are central to the area of scientific computation: solving dense linear systems by Gaussian elimination, computing fast Fourier transforms, and solving sparse linear systems by iterative methods based on sparse matrix-vector multiplication. Each topic is treated in depth, starting from the problem formulation and a sequential algorithm, through a parallel algorithm and its cost analysis, to a complete parallel program written in C and BSPlib, and experimental results obtained using this program on a parallel computer. Throughout the book, emphasis is placed on analyzing the cost of the parallel algorithms developed, expressed in three terms: computation cost, communication cost, and synchronization cost. The book contains five example programs written in BSPlib, which illustrate the methods taught. These programs are freely available as the package BSPedupack. An appendix on the message-passing interface (MPI) discusses how to program in a structured, bulk synchronous parallel style using the MPI communication library, and presents MPI equivalents of all the programs in the book.Less

This book explains the use of the bulk synchronous parallel (BSP) model and the BSPlib communication library in parallel algorithm design and parallel programming. The main topics treated in the book are central to the area of scientific computation: solving dense linear systems by Gaussian elimination, computing fast Fourier transforms, and solving sparse linear systems by iterative methods based on sparse matrix-vector multiplication. Each topic is treated in depth, starting from the problem formulation and a sequential algorithm, through a parallel algorithm and its cost analysis, to a complete parallel program written in C and BSPlib, and experimental results obtained using this program on a parallel computer. Throughout the book, emphasis is placed on analyzing the cost of the parallel algorithms developed, expressed in three terms: computation cost, communication cost, and synchronization cost. The book contains five example programs written in BSPlib, which illustrate the methods taught. These programs are freely available as the package BSPedupack. An appendix on the message-passing interface (MPI) discusses how to program in a structured, bulk synchronous parallel style using the MPI communication library, and presents MPI equivalents of all the programs in the book.

*Harri Kiiveri*

- Published in print:
- 2014
- Published Online:
- December 2014
- ISBN:
- 9780198709022
- eISBN:
- 9780191779619
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198709022.003.0003
- Subject:
- Mathematics, Probability / Statistics, Biostatistics

The usual analysis of gene expression data ignores the correlation between gene expression values. Biologically, this assumption is unreasonable. The approach presented in this chapter allows for ...
More

The usual analysis of gene expression data ignores the correlation between gene expression values. Biologically, this assumption is unreasonable. The approach presented in this chapter allows for correlation between genes through a sparse Gaussian graphical model: sparse inverse covariance matrices and their associated graphical representations are used to capture the notion of gene networks. Existing methods find their limitations in the issue posed by the identification of the pattern of zeroes in such inverse covariance matrices. A workable solution for determining the zero pattern is provided in this chapter. Two other important contributions of this chapter are a method for very high-dimensional model fitting and a distribution-free approach to hypothesis testing. Such tests address assessment of differential expression and of differential connection, a novel notion introduced in this chapter. An example dealing with real data is presented.Less

The usual analysis of gene expression data ignores the correlation between gene expression values. Biologically, this assumption is unreasonable. The approach presented in this chapter allows for correlation between genes through a sparse Gaussian graphical model: sparse inverse covariance matrices and their associated graphical representations are used to capture the notion of gene networks. Existing methods find their limitations in the issue posed by the identification of the pattern of zeroes in such inverse covariance matrices. A workable solution for determining the zero pattern is provided in this chapter. Two other important contributions of this chapter are a method for very high-dimensional model fitting and a distribution-free approach to hypothesis testing. Such tests address assessment of differential expression and of differential connection, a novel notion introduced in this chapter. An example dealing with real data is presented.

*I. S. Duff, A. M. Erisman, and J. K. Reid*

- Published in print:
- 2017
- Published Online:
- April 2017
- ISBN:
- 9780198508380
- eISBN:
- 9780191746420
- Item type:
- book

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198508380.001.0001
- Subject:
- Mathematics, Numerical Analysis

Direct Methods for Sparse Matrices, second edition, is a complete rewrite of the first edition published 30 years ago. Much has changed since that time. Problems have grown greatly in size and ...
More

Direct Methods for Sparse Matrices, second edition, is a complete rewrite of the first edition published 30 years ago. Much has changed since that time. Problems have grown greatly in size and complexity; nearly all our examples were of order less than 5,000 in the first edition, and are often more than a million in the second edition. Computer architectures are now much more complex, requiring new ways of adapting algorithms to parallel environments with memory hierarchies. Because the area is such an important one to all of computational science and engineering, a huge amount of research has been done since the first edition, some of it by the authors. This new research is integrated into the text with a clear explanation of the underlying mathematics and algorithms. New research that is described includes new techniques for scaling and error control, new orderings, new combinatorial techniques for partitioning both symmetric and unsymmetric problems, and a detailed description of the multifrontal approach to solving systems that was pioneered by the research of the authors and colleagues. This includes a discussion of techniques for exploiting parallel architectures and new work for indefinite and unsymmetric systems.Less

Direct Methods for Sparse Matrices, second edition, is a complete rewrite of the first edition published 30 years ago. Much has changed since that time. Problems have grown greatly in size and complexity; nearly all our examples were of order less than 5,000 in the first edition, and are often more than a million in the second edition. Computer architectures are now much more complex, requiring new ways of adapting algorithms to parallel environments with memory hierarchies. Because the area is such an important one to all of computational science and engineering, a huge amount of research has been done since the first edition, some of it by the authors. This new research is integrated into the text with a clear explanation of the underlying mathematics and algorithms. New research that is described includes new techniques for scaling and error control, new orderings, new combinatorial techniques for partitioning both symmetric and unsymmetric problems, and a detailed description of the multifrontal approach to solving systems that was pioneered by the research of the authors and colleagues. This includes a discussion of techniques for exploiting parallel architectures and new work for indefinite and unsymmetric systems.