Sparsity issues in the computation of Jacobian matrices

ABSTRACT

The knowledge of sparsity information plays an important role in efficient determination of sparse Jacobian matrices. In a recent work, we have proposed sparsity-exploiting substitution techniques to determine Jacobian matrices. In this paper, we take a closer look at the underlying combinatorial problem. We propose a column ordering heuristic to augment the "usable sparsity" in the Jacobian matrix. Furthermore, we present a new elimination technique based on merging of successive columns.

REFERENCES

• 1: Thomas F Coleman , Jin Yi Cai, The cyclic coloring problem and estimation of spare hessian matrices, SIAM Journal on Algebraic and Discrete Methods, v.7 n.2, p.221-235, April 1986 [doi>10.1137/0607026]
• 2: Thomas F. Coleman , Burton S. Garbow , Jorge J. More, Software for estimating sparse Jacobian matrices, ACM Transactions on Mathematical Software (TOMS), v.10 n.3, p.329-345, Sept. 1984 [doi>10.1145/1271.1610]
• 3: T. F. Coleman and J. J. Moré. Estimation of sparse Jacobian matrices and graph coloring problems. SIAM J. Numer. Anal., 20(1):187-209, 1983.
• 4: T. F. Coleman and J. J. Moré. Estimation of sparse Hessian matrices and graph coloring problems. Math. Programming, 28:243-270, 1984.
• 5: Thomas F. Coleman , Arun Verma, The Efficient Computation of Sparse Jacobian Matrices Using Automatic Differentiation, SIAM Journal on Scientific Computing, v.19 n.4, p.1210-1233, July 1998 [doi>10.1137/S1064827595295349]
• 6: George Corliss , Christèle Faure , Andreas Griewank , Lauren Hascoët , Uwe Naumann, Automatic differentiation of algorithms: from simulation to optimization, Springer-Verlag New York, Inc., New York, NY, 2000
• 7: A. R. Curtis, M. J. D. Powell, and J. K. Reid. On the estimation of sparse Jacobian matrices. J. Inst. Math. Appl., 13:117-119, 1974.
• 8: I. S. Duff, R. G. Grimes, and J. G. Lewis. Users' guide for the Harwell-Boeing sparse matrix collection (Release I). Technical Report tr/pa/92/86, CERFACS, 1992.
• 9: W. Gautschi. How (Un)stable are Vandermonde Systems? In R. Wong, editor, Asymptotic and computational analysis, volume 124 of Lecture Notes in Pure and Appl. Math., pages 193-210. Marcel Dekker, Inc., New York, 1990.
• 10: U. Geitner, J. Utke, and A. Griewank. Automatic computation of sparse Jacobians by applying the method of Newsam and Ramsdell. In M. Berz, C. Bischof, G. Corliss, and A. Griewank, editors, Computational Differentiation: Techniques Applications, and Tools, pages 161-172. SIAM, Philadelphia, Penn., 1996.
• 11: D. Goldfarb and P. L. Toint. Optimal estimation of Jacobian and Hessian matrices that arise in finite difference calculations. Mathematics of Computation, 43(167):69-88, 1984.
• 12: G. H. Golub and C. F. V. Loan. Matrix Computations. Johns Hopkins University Press, 3rd edition, 1996.
• 13: Andreas Griewank, Evaluating derivatives: principles and techniques of algorithmic differentiation, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2000
• 14: A. Griewank and C. Mitev. Detecting Jacobian sparsity patterns by Bayesian probing. Preprint IOKOMO-04-2000, Technical University of Dresden, 2000. Submitted to Math. Progr.
• 15: Shahadat Hossain , Trond Steihaug, Reducing the number of AD passes for computing a sparse Jacobian matrix, Automatic differentiation of algorithms: from simulation to optimization, Springer-Verlag New York, Inc., New York, NY, 2000
• 16: M. Monagan and R. R. Rodoni. Automatic differentiation: An implementation of the forward and reverse mode in Maple. In M. Berz, C. H. Bischof, G. F. Corliss, and A. Griewank, editors, Computational Differentiation: Techniques, Applications, and Tools, pages 353-362. SIAM, Philadelphia, Penn., 1996.
• 17: M. R. Garey and D. S. Johnson. Computers and Intractibility. W. H. Freeman, San Francisco, 1979.
• 18: G. N. Newsam and J. D. Ramsdell. Estimation of sparse Jacobian matrices. SIAM J. Alg. Disc. Meth., 4(3):404-417, 1983.
• 19: P. E. Plassmann. Sparse Jacobian estimation and factorization on a multiprocessor. In T. F. Coleman and Y. Li, editors, Large-Scale Optimization, pages 152-179. SIAM, Philadelphia, Penn., 1990.
• 20: M. J. D. Powell and P. L. Toint. On the estimation of sparse Hessian matrices. SIAM J. Numer. Anal., 16:1060-1074, 1979.
• 21: L. B. Rall. Automatic Differentiation: Techniques and Applications, volume 120 of Lecture Notes in Computer Science. Springer-Verlag, Berlin, 1981.
• 22: L. B. Rall and T. W. Reps. Algorithmic differencing. In A. Facius and U. Kulisch, editors, Perspectives on Enclosure Methods. Springer-Verlag, Vienna, 2001.
• 23: L. Reichel and G. Opfer. Chebyshev-Vandermonde Systems. Mathematics of Computation, 57(196):703-721, 1991.
• 24: T. Steihaug and A. S. Hossain. Graph coloring and the estimation of sparse Jacobian matrices with segmented columns. Technical Report 72, Department of Informatics, University of Bergen, 1997.
• 25: The MathWorks. Matlab 5.3.1, 2000. See www.mathworks.com/products/matlab.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization

General Terms:
Algorithms

Keywords:
merging, partition, sparse jacobians, substitution methods