I. S. Duff
Abstract
We describe the Harwell-Boeing sparse matrix collection, a set of standard test matrices for sparse matrix problems. Our test set comprises problems in linear systems, least squares, and eigenvalue calculations from a wide variety of scientific and engineering disciplines. The problems range from small matrices, used as counter-examples to hypotheses in sparse matrix research, to large test cases arising in large-scale computation. We offer the collection to other researchers as a standard benchmark for comparative studies of algorithms. The procedures for obtaining and using the test collection are discussed. We also describe the guidelines for contributing further test problems to the collection.
- 1 DUFF, I. S., GRIMES, R. G., AND LEWIS, J.G. Users' Guide for the HarweU-Boeing sparse matrix collection. To appear as Harwell Report and Boeing Report.Google Scholar
- 2 DUFF, I. S., GRIMES, R. G., LEWIS, J. G., AND POOLE, W. G. JR. Sparse matrix test problems. SIGNUM Newsl. 17, 2, (1982), p. 22. Google Scholar
- 3 DUFF, }. S., AND REID, J.g. Performance evaluation of codes for sparse matrix problems. In Performance Evaluation of Numerical Software. Fosdick, L. D., ed. Elsevier, North-Holland, New York, 1979, pp. 121-135.Google Scholar
- 4 LENARD, M. L. Standardizing the interface with nonlinear optimizers. Presented at TIMS/ ORSA Joint National Meeting (Washington, D.C., Apr. 25-27, 1989). Paper WC 36.1, TIMS/ORSA Bull. 25.Google Scholar
- 5 MORI~, J. J., GARBOW, B. S., AND HILLSTROM, K. E. Testing unconstrained optimization software. ACM Trans. Math. Softw. 7 (1981), 17-41. Google Scholar
- 6 TOINT, PH. L. Call for test problems in large scale nonlinear optimization. Report 87/9, Department of Mathematics, Facult6s Universitaires ND de la Paix, Namur, Belgium, 1987.Google Scholar
Index Terms
- Sparse matrix test problems
Recommendations
Fast sparse matrix multiplication
Let A and B two n×n matrices over a ring R (e.g., the reals or the integers) each containing at most m nonzero elements. We present a new algorithm that multiplies A and B using O(m0.7n1.2+n2+o(1)) algebraic operations (i.e., multiplications, additions ...
A sparse-sparse iteration for computing a sparse incomplete factorization of the inverse of an SPD matrix
In this paper, a method via sparse-sparse iteration for computing a sparse incomplete factorization of the inverse of a symmetric positive definite matrix is proposed. The resulting factorized sparse approximate inverse is used as a preconditioner for ...
"Wide or tall" and "sparse matrix dense matrix" multiplications
HPC '11: Proceedings of the 19th High Performance Computing SymposiaSparse matrix dense matrix (SMDM) multiplications are useful in block Krylov or block Lanczos methods. SMDM computations are AU, and VA, multiplication of a large sparse m x n matrix A by a matrix V of k rows of length m or a matrix U of k columns of ...
Reviews
Zahari Zlatev
The authors discuss the well-known Boeing-Harwell set of sparse test matrices. Matrices of this set have been used widely in the literature. This paper will help many other developers of codes that exploit the sparsity of matrices to test the efficiency of their codes on a very large and representative set of matrices that appear in many different fields of science and engineering. The Boeing-Harwell set contains 292 test matrices that occur in various fields, such as air traffic control, chemical engineering, circuit simulation, oil reservoir modeling, oceanography, and power networks. Most of the matrices in the Boeing-Harwell set are symmetric and positive definite. The class of asymmetric matrices is also well represented. It would be desirable to include some more matrices in other classes (such as matrices that appear in linear least squares problems). The matrices of the Boeing-Harwell set contain about 110 megabytes of data (and the authors intend to add more matrices). The size of the set could cause problems when it is used on small computers. The authors propose two remedies for such problems. First, users do not need to obtain the whole set; the authors develop well-organized techniques for extracting subsets of matrices. Second, two generators for sparse matrices are available (one for 5- or 9-point discretizations of the Laplacian operator, and another for three-dimensional oil-reservoir simulations). The second remedy deserves more attention. The generators are often short programs that allow users to study the performance of their codes systematically by varying the values of certain parameters. Perhaps even more important, these short programs could be applied successfully even on personal computers. Many generators for sparse matrices have been reported in the literature and used by many researchers. It may be time to try to unite these efforts by developing common tools easily available to everyone working with large and sparse matrices. The authors formulate rules for obtaining matrices from the Boeing-Harwell set and rules for submitting matrices to this set. They give a detailed description of the formats used to store the matrices and the related information. This paper will be very useful for developers of sparse matrix software as well as researchers who have to choose a sparse matrix code for computing centers, for research institutes, and for big libraries of standard subroutines.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments