Timothy A. Davis
Yifan Hu
Skip Abstract Section
Abstract
We describe the University of Florida Sparse Matrix Collection, a large and actively growing set of sparse matrices that arise in real applications. The Collection is widely used by the numerical linear algebra community for the development and performance evaluation of sparse matrix algorithms. It allows for robust and repeatable experiments: robust because performance results with artificially generated matrices can be misleading, and repeatable because matrices are curated and made publicly available in many formats. Its matrices cover a wide spectrum of domains, include those arising from problems with underlying 2D or 3D geometry (as structural engineering, computational fluid dynamics, model reduction, electromagnetics, semiconductor devices, thermodynamics, materials, acoustics, computer graphics/vision, robotics/kinematics, and other discretizations) and those that typically do not have such geometry (optimization, circuit simulation, economic and financial modeling, theoretical and quantum chemistry, chemical process simulation, mathematics and statistics, power networks, and other networks and graphs). We provide software for accessing and managing the Collection, from MATLAB™, Mathematica™, Fortran, and C, as well as an online search capability. Graph visualization of the matrices is provided, and a new multilevel coarsening scheme is proposed to facilitate this task.
- Amestoy, P. R., Davis, T. A., and Duff, I. S. 1996. An approximate minimum degree ordering algorithm. SIAM J. Matrix Anal. Appl. 17, 4, 886--905. Google Scholar
Digital Library
- Amestoy, P. R., Davis, T. A., and Duff, I. S. 2004. Algorithm 837: AMD, an approximate minimum degree ordering algorithm. ACM Trans. Math. Softw. 30, 3, 381--388. Google ScholarDigital Library
- Amestoy, P. R., Li, X., and Ng, E. G. 2007. Diagonal Markowitz scheme with local symmetrization. SIAM J. Matrix Anal. Appl. 29, 1, 228--244.Google ScholarCross Ref
- Amestoy, P. R. and Puglisi, C. 2002. An unsymmetrized multifrontal LU factorization. SIAM J. Matrix Anal. Appl. 24, 553--569. Google ScholarDigital Library
- Bai, Z., Day, D., Demmel, J., and Dongarra, J. 1996. Test matrix collection (non-Hermitian eigenvalue problems), Release 1. Tech. rep., University of Kentucky. ftp://ftp.ms.uky.edu/pub/misc/bai/Collection.Google Scholar
- Bai, Z., Day, D., Demmel, J., and Dongarra, J. Non-Hermitian eigenvalue problems. http://www.cs.ucdavis.edu/~bai/NEP. (Accessed 2008)Google Scholar
- Barnes, J. and Hut, P. 1986. A hierarchical o(n log n) force-calculation algorithm. Lett. Nature 324, 4, 446--449.Google ScholarCross Ref
- Batagelj, V. and Mrvar, A. Pajek networks. http://vlado.fmf.uni-lj.si/pub/networks/data. (Accessed 2008)Google Scholar
- Benzi, M. and Tuma, M. 1998. A sparse approximate inverse preconditioner for nonsymmetric linear systems. SIAM J. Sci. Comput. 19, 968--994. Google ScholarDigital Library
- Berger, A. J., Mulvey, J. M., Rothberg, E., and Vanderbei, R. J. 1995. Solving multistage stochastic programs using tree dissection. Tech. rep. SOR-95-07, Department of Civil Engineering and Operations Research, Princeton University, Princeton, NJ.Google Scholar
- Boisvert, R. F., Pozo, R., Remington, K., Barrett, R., Dongarra, J., Miller, B., and Lipman, B. The Matrix Market. http://math.nist.gov/MatrixMarket. (Accessed 2008)Google Scholar
- Boisvert, R. F., Pozo, R., Remington, K., Barrett, R., and Dongarra, J. J. 1997. The Matrix Market: A web resource for test matrix collections. In Quality of Numerical Software, Assessment and Enhancement, R. F. Boisvert, Ed., Chapman & Hall, London, 125--137. http://math.nist.gov/MatrixMarket. Google ScholarDigital Library
- Bomhof, C. W. and van der Vorst, H. A. 2000. A parallel linear system solver for circuit simulation problems. Numer. Linear Algebra Appl. 7, 7-8, 649--665.Google ScholarCross Ref
- Brainman, I. and Toledo, S. 2002. Nested-dissection orderings for sparse LU with partial pivoting. SIAM J. Matrix Anal. Appl. 23, 998--1012. Google ScholarDigital Library
- Chen, Y., Davis, T. A., Hager, W. W., and Rajamanickam, S. 2008. Algorithm 887: Cholmod, supernodal sparse cholesky factorization and update/downdate. ACM Trans. Math. Softw. 35, 3, 1--14. Google ScholarDigital Library
- Davis, T. A. 2005. Algorithm 849: A concise sparse Cholesky factorization package. ACM Trans. Math. Softw. 31, 4, 587--591. Google ScholarDigital Library
- Davis, T. A. and Hager, W. W. 2009. Dynamic supernodes in sparse cholesky update/downdate and triangular solves. ACM Trans. Math. Softw. 35, 4, 1--23. Google ScholarDigital Library
- Demmel, J. W., Eisenstat, S. C., Gilbert, J. R., Li, X. S., and Liu, J. W. H. 1999a. A supernodal approach to sparse partial pivoting. SIAM J. Matrix Anal. Appl. 20, 3, 720--755. Google ScholarDigital Library
- Demmel, J. W., Gilbert, J. R., and Li, X. S. 1999b. An asynchronous parallel supernodal algorithm for sparse Gaussian elimination. SIAM J. Matrix Anal. Appl. 20, 4, 915--952. Google ScholarDigital Library
- Duff, I. S. 1974. Pivot selection and row ordering in Givens reductions on sparse matrices. Comput. 13, 239--248.Google ScholarCross Ref
- Duff, I. S. 2001. YM11 documentation in HSL 2007. http://www.hsl.rl.ac.uk/specs/ym11.pdf.Google Scholar
- Duff, I. S., Grimes, R. G., and Lewis, J. G. 1989. Sparse matrix test problems. ACM Trans. Math. Softw. 15, 1, 1--14. Google ScholarDigital Library
- Duff, I. S., Grimes, R. G., and Lewis, J. G. 1997. The Rutherford-Boeing sparse matrix collection. Tech. rep. RAL-TR-97-031, Rutherford Appleton Laboratory, UK.Google Scholar
- Duff, I. S. and Koster, J. 1999. The design and use of algorithms for permuting large entries to the diagonal of sparse matrices. SIAM J. Matrix Anal. Appl. 20, 4, 889--901. Google ScholarDigital Library
- Duff, I. S. and Pralet, S. 2005. Strategies for scaling and pivoting for sparse symmetric indefinite problems. SIAM J. Matrix Anal. Appl. 27, 2, 313--340. Google ScholarDigital Library
- Duff, I. S. and Reid, J. K. 1979. Performance evaluation of codes for sparse matrix problems. In Performance Evaluation of Numerical Software, L. D. Fosdick, Ed., North-Holland, New York, 121--135.Google Scholar
- Duff, I. S. and Reid, J. K. 1996. Exploiting zeros on the diagonal in the direct solution of indefinite sparse symmetric linear systems. ACM Trans. Math. Softw. 22, 2, 227--257. Google ScholarDigital Library
- Dumas, J.-G. Sparse integer matrices collection. http://ljk.imag.fr/membres/Jean-Guillaume.Dumas/simc.html. (Accessed 2008)Google Scholar
- Feldmann, P., Melville, R., and Long, D. 1996. Efficient frequency domain analysis of large nonlinear analog circuits. In Proceedings of the IEEE Custom Integrated Circuits Conference. IEEE.Google Scholar
- Fruchterman, T. M. J. and Reingold, E. M. 1991. Graph drawing by force-directed placement. Softw. Pract. Exper. 21, 11, 1129--1164. Google ScholarDigital Library
- Gay, D. NETLIB LP test problems. http://www.netlib.org/lp. (Accessed 2008)Google Scholar
- George, A., Heath, M. T., and Ng, E. 1983. A comparison of some methods for solving sparse linear least-squares problems. SIAM J. Sci. Statist. Comput. 4, 2, 177--187.Google ScholarDigital Library
- George, A. and Liu, J. W. H. 1981. Computer Solution of Large Sparse Positive Definite Systems. Prentice-Hall, Englewood Cliffs, NJ. Google ScholarDigital Library
- Gilbert, J. R., Moler, C., and Schreiber, R. 1992. Sparse matrices in MATLAB: design and implementation. SIAM J. Matrix Anal. Appl. 13, 1, 333--356. Google ScholarDigital Library
- Gilbert, J. R. and Peierls, T. 1988. Sparse partial pivoting in time proportional to arithmetic operations. SIAM J. Sci. Statist. Comput. 9, 862--874.Google ScholarDigital Library
- Gorter, F. and Kasky, A. 2010. The most intense moments the universe has ever known are the next 15 seconds. http://butdoesitfloat.com/496420/The-most-intense-moments-the-universe-has-ever-known-are-the-next-15.Google Scholar
- Gould, N., Hu, Y., and Scott, J. Gould/Hu/Scott collection. ftp://ftp.numerical.rl.ac.uk/pub/matrices/symmetric. (Accessed 2008)Google Scholar
- Gupta, A. 1996. Fast and effective algorithms for graph partitioning and sparse matrix ordering. Tech. rep. RC 20496 (90799), IBM Research Division, Yorktown Heights, NY.Google Scholar
- Gupta, A. 2002. Improved symbolic and numerical factorization algorithms for unsymmetric sparse matrices. SIAM J. Matrix Anal. Appl. 24, 529--552. Google ScholarDigital Library
- Hachul, S. and Jünger, M. 2004. Drawing large graphs with a potential field based multilevel algorithm. In Proceedings of the 12th International Symposium on Graph Drawing (GD'04). Lecture Notes in Computer Science, vol. 3383. Springer, 285--295. Google ScholarDigital Library
- Higham, N. J. 2002. Accuracy and Stability of Numerical Algorithms, 2nd Ed. SIAM, Philadelphia, PA. Google ScholarDigital Library
- Hu, Y. F. 2005. Efficient and high-quality force-directed graph drawing. Mathematica J. 10, 37--71.Google Scholar
- Hu, Y. and Davis, T. 2011. Sparse matrices. The Harvard Advocate, 42--43.Google Scholar
- IEEE Spectrum editorial staff. 2010. The big picture: Pretty math problem. IEEE Spectrum 47, 10, 18--19. Google ScholarDigital Library
- Kamvar, S. Stanford-Berkeley web matrices. http://www.stanford.edu/~sdkamvar. (Accessed 2008)Google Scholar
- Kamvar, S. D., Haveliwala, T. H., and Golub, G. H. 2004. Adaptive methods for the computation of page rank. Linear Algebra Appl. 386, 51--65.Google ScholarCross Ref
- Karypis, G. and Kumar, V. 1998. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Sci. Comput. 20, 359--392. Google ScholarDigital Library
- Keiter, E., Hutchinson, S. A., Hoekstra, R., Rankin, E., Russo, T., and Waters, L. 2003. Computational algorithms for device-circuit coupling. Tech. rep. SAND2003-0080, Sandia National Laboratories, Albequerque, NM.Google Scholar
- Kemelmacher, I. 2005. Indexing with unknown illumination and pose. In IEEE Conference on Computer Vision and Pattern Recognition. IEEE. Google ScholarDigital Library
- Kiss, G. R., Armstrong, C., Milroy, R., and Piper, J. 1973. An associative thesaurus of English and its computer analysis. In The Computer and Literary Studies, A. Aitken, R. Bailey, and N. Hamilton-Smith, Eds., Edinburgh University Press, Edinburgh, UK.Google Scholar
- Labarre, S. 2010. Geeky science problems double as works of art. http://www.fastcodesign.com/1662136/geeky-science-problems-double-as-works-of-art.Google Scholar
- Leskovec, J., Chakrabarti, D., Kleinberg, J., and Faloutsos, C. 2005. Realistic, mathematically tractable graph generation and evolution, using kronecker multiplication. In Knowledge Discovery in Databases (PKDD'05), A. Jorge, L. Torgo, P. Brazdil, R. Camacho, and J. Gama, Eds., Lecture Notes in Computer Science, vol. 3721. Springer, 133--145. Google ScholarDigital Library
- McConnell, R. M. and Spinrad, J. P. 1999. Modular decomposition and transitive orientation. Discr. Math. 201, 189--241. Google ScholarDigital Library
- Mészáros, C. Linear programming test set. http://www.sztaki.hu/~meszaros/public_ftp/lptestset. (Accessed 2008)Google Scholar
- Miller, J. J. H. and Wang, S. 1991. An exponentially fitted finite element method for a stationary convection-diffusion problem. In Computatioal Methods for Boundary and Interior Layers in Several Dimensions, J. J. H. Miller, Ed., Boole Press, Dublin, 120--137.Google Scholar
- Mittelmann, H. Linear programming test set. http://plato.asu.edu/ftp/lptestset. (Accessed 2008)Google Scholar
- Ng, E. G. and Peyton, B. W. 1993. Block sparse Cholesky algorithms on advanced uniprocessor computers. SIAM J. Sci. Comput. 14, 5, 1034--1056. Google ScholarDigital Library
- Page, L., Brin, S., Motwani, R., and Winograd, T. 1998. The PageRank citation ranking: Bringing order to the web. Tech. rep., Stanford Digital Library Tech. Project, Stanford, CA.Google Scholar
- Resende, M. G. C., Ramakrishnan, K. G., and Drezner, Z. 1995. Computing lower bounds for the quadratic assignment problem with an interior point algorithm for linear programming. Oper. Res. 43, 781--791.Google ScholarDigital Library
- Rudnyi, E. B. Oberwolfach model reduction benchmarks. http://www.imtek.uni-freiburg.de/simulation/benchmark. (Accessed 2008)Google Scholar
- Rudnyi, E. B., van Rietbergen, B., and Korvink, J. G. 2006. Model reduction for high dimensional micro-FE models. In Proceedings of the 3rd HPC-Europa Transnational Access Meeting.Google Scholar
- Ruesken, A. 2002. Approximation of the determinant of large sparse symmetric positive definite matrices. SIAM J. Matrix Anal. Appl. 23, 3, 799--818. Google ScholarDigital Library
- Saad, Y. 2003. Iterative Methods for Sparse Linear Systems, 2nd Ed. SIAM, Philadelphia, PA. Google ScholarDigital Library
- Saad, Y. SPARSKIT collection. http://math.nist.gov/MatrixMarket/data/SPARSKIT. (Accessed 2008)Google Scholar
- Schenk, O. University of Basel collection. http://www.computational.unibas.ch/computer_science/scicomp/matrices. (Accessed 2008)Google Scholar
- Schulze, J. 2001. Towards a tighter coupling of bottom-up and top-down sparse matrix ordering methods. BIT 41, 4, 800--841.Google ScholarCross Ref
- Taylor, A. and Higham, D. J. 2009. CONTEST: A controllable test matrix toolbox for MATLAB. ACM Trans. Math. Softw. 35, 4, 1--17. Google ScholarDigital Library
- Trefethen, L. N. 2002. A hundred-dollar, hundred-digit challenge. SIAM News 35, 1.Google Scholar
- van Heukelum, A., Barkema, G. T., and Bisseling, R. H. 2002. DNA electrophoresis studied with the cage model. J. Comput. Phys. 180, 313--326. Google ScholarDigital Library
- Walshaw, C. 2003. A multilevel algorithm for force-directed graph drawing. J. Graph Algor. Appl. 7, 253--285.Google ScholarCross Ref
- Watts, D. J. and Strogatz, S. H. 1998. Collective dynamics of small-world networks. Nature 393, 440--442.Google ScholarCross Ref
- Wilkinson, J. H. 1971. Linear algebra; part II: the algebraic eigenvalue problem. In Handbook for Automatic Computation, J. H. Wilkinson and C. Reinsch, Eds., Vol. 2. Springer.Google Scholar
- Zitney, S. E. 1992. Sparse matrix methods for chemical process separation calculations on supercomputers. In Proceedings of the Supercomputing'92 Conference. IEEE Computer Society Press. 414--423. Google ScholarDigital Library
- Zitney, S. E., Mallya, J., Davis, T. A., and Stadtherr, M. A. 1996. Multifrontal vs. frontal techniques for chemical process simulation on supercomputers. Comput. Chem. Engin. 20, 6/7, 641--646.Google Scholar
Index Terms
- The university of Florida sparse matrix collection
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 ...
Comments