Nonzero structure analysis

ABSTRACT

Because the efficiency of sparse codes is very much dependent on the size and structure of input data, peculiarities of the nonzero structures of sparse matrices must be accounted for in order to avoid unsatisfying performance. Usually, this implies retargeting a sparse application to specific instances of the same problem. However, if characteristics of the input data are collected at compile-time and used in the data structure selection and code generation by a compiler that converts dense programs into sparse programs automatically, the complexity of sparse code development can be greatly reduced, and an efficient way for this retargeting results. Such a “sparse compiler” requires an analysis engine, which is the topic of this paper.

REFERENCES

• 1: S. Kamal Abdali , David S. Wise, Experiments with Quadtree Representation of Matrices, Proceedings of the International Symposium ISSAC'88 on Symbolic and Algebraic Computation, p.96-108, July 04-08, 1988
• 2: Utpal K. Banerjee, Loop Transformations for Restructuring Compilers: The Foundations, Kluwer Academic Publishers, Norwell, MA, 1993
• 3: A. J. C. Bik , H. A. G. Wijshoff, Advanced compiler optimizations for sparse computations, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.430-439, December 1993, Portland, Oregon, United States [doi>10.1145/169627.169765]
• 4: Aart J. C. Bik , Harry A. G. Wijshoff, Compilation techniques for sparse matrix computations, Proceedings of the 7th international conference on Supercomputing, p.416-424, July 19-23, 1993, Tokyo, Japan [doi>10.1145/165939.166023]
• 5: Aart J.C. Bik and Harry A.G. W~shoff. MTI: A prototype restructuring compiler. Technical Report no. 93-32, Dept. of Computer Science, L~den UniversitE 1993.
• 6: Aart J. C. Bik , Harry A. G. Wijshoff, On Automatic Data Structure Selection and Code Generation for Sparse Computations, Proceedings of the 6th International Workshop on Languages and Compilers for Parallel Computing, p.57-75, August 12-14, 1993
• 7: Efizabeth Cuthill. Several strategies for redu~ng the bandwidth of matrices. In Donald J. Rose and Ralph A. Willoughb~ editors, Sparse Matrices and Their Applications, pages 157-166. P~num Press, New York, 1972.
• 8: I.S. Duff. A sparse future. In I.S. Duff, editor, Sparse Matrices and their Uses, pages 1-29. Academ~ Press, London, 1981.
• 9: I. S. Duff , A. M. Erisman , J. K. Reid, Direct methods for sparse matrices, Clarendon Press, New York, NY, 1987
• 10: I. S. Duff , Roger G. Grimes , John G. Lewis, Sparse matrix test problems, ACM Transactions on Mathematical Software (TOMS), v.15 n.1, p.1-14, March 1989 [doi>10.1145/62038.62043]
• 11: I. S. Duff , J. K. Reid, Some Design Features of a Sparse Matrix Code, ACM Transactions on Mathematical Software (TOMS), v.5 n.1, p.18-35, March 1979 [doi>10.1145/355815.355817]
• 12: Alan George , Joseph W. H. Liu, The Design of a User Interface for a Sparse Matrix Package, ACM Transactions on Mathematical Software (TOMS), v.5 n.2, p.139-162, June 1979 [doi>10.1145/355826.355829]
• 13: Alan George , Joseph W. Liu, Computer Solution of Large Sparse Positive Definite, Prentice Hall Professional Technical Reference, 1981
• 14: Frank Harary. Sparse matrices and graph theory. In J.K. R~d, ed~or, Large Sparse Sets of Linear Equalions, pages 139-150. Academ~ Press, 1971.
• 15: Donald Heurn and M. Paufine Baker. Computer Graphics. Prent~e-Hall International, 1986.
• 16: A. Jennings. A compact storage scheme for the solution of symmetric finear ~multaneous equations. The Computer Journa~ Volume 9:281-285, 1966.
• 17: A. Jennings and A.D. Tuff. A direct method for the solution of large sparse symmetric simultaneous equations. In J.K. Reid, editor, Large Sparse Sets of Linear Equations, pages 97-104. Academic Press, 1971.
• 18: William H. Press, Brian P. Flannery, Saul A. Teukolsky, and William T. Vetterfing. Numerical Recipes. Cambridge Univer~ty Press, Cambridge, 1986.
• 19: Youcef Sand. SPARSKIT: a bas~ tool }dt for sparse matrix computations. CSRD/RIACS, 1990.
• 20: Youcef Saad , Harry A. G. Wijshoff, SPARK: a benchmark package for sparse computations, Proceedings of the 4th international conference on Supercomputing, p.239-253, June 11-15, 1990, Amsterdam, The Netherlands
• 21: Hanan Samet, Connected Component Labeling Using Quadtrees, Journal of the ACM (JACM), v.28 n.3, p.487-501, July 1981 [doi>10.1145/322261.322267]
• 22: R. Ta~an. Depth-first search and finear graph algorithms. SIAM J. Computing, pages 146-160, 1972.
• 23: ReginM P. Tewarson. Sorting and orderi~ag sparse 5near systems, in J.K. R~d, editor, Large Sparse Sets of Linear Equations, pages 151-167. Academ~ Press, 1971.
• 24: Reginal P. Tewarson. Sparse Matrices. Acudem~ Press, New York, 1973.
• 25: M. Veldhorst. An Analysis of Sparse Matrix Storage Schemes. PhD thews, Mathemat~ch Centrum, Am~ terdam, 1982.
• 26: David S. Wise. Representating matrices as quadtrees for parallel proces~ng. Information Processing Letters, Volume 20:195-199, 1985.
• 27: David S. W~e. Parallel decompo~fion of matrix inversion using quadtrees. In Proceedings of the 1986 International Conference on Parallel Processin~ pages 92-99, 1986.
• 28: David S. W~e and John Franco. Costs of quadtree representaron of nondense matrices. Journal of Paral~l and Dist~buted Computin~ Volume 9:282-296, 1990.
• 29: Zahari Zlatev. Computational Methods for General Sparse Matrices. Kluwer Academ~ Pub~shers, 1991.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Sparse, structured, and very large systems (direct and iterative methods)

General Terms:
Theory

Keywords:
nonzero structures, restructuring compilers, sparse matrices