DSJM: A Software Toolkit for Direct Determination of Sparse Jacobian Matrices

详细信息    查看全文

• 关键词：Sparse Jacobian matrix ; Compression ; reconstruction ; Direct determination
• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9725
• 期：1
• 页码：275-283
• 全文大小：201 KB
• 参考文献：1.Coleman, T.F., Moré, J.J.: Estimation of sparse Jacobian matrices and graph coloring problems. SIAM J. Numer. Anal. 20(1), 187–209 (1983)MathSciNet CrossRef MATH
  2.Coleman, T.F., Verma, A.: The efficient computation of sparse Jacobian matrices using automatic differentiation. SIAM J. Sci. Comput. 19(4), 1210–1233 (1998)MathSciNet CrossRef MATH
  3.Curtis, A.R., Powell, M.J.D., Reid, J.K.: On the estimation of sparse Jacobian matrices. J. Inst. Math. Appl. 13, 117–119 (1974)CrossRef MATH
  4.Davis, T.A.: Direct Methods for Sparse Linear Systems (Fundamentals of Algorithms 2). Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (2006)CrossRef
  5.Duff, I.S., Grimes, R.G., Lewis, J.G.: Sparse matrix test problems. ACM Trans. Math. Softw. 15(1), 1–14 (1989)MathSciNet CrossRef MATH
  6.Gebremedhin, A.H., Manne, F., Pothen, A.: What color is your jacobian? graph coloring for computing derivatives. SIAM Rev. 47(4), 629–705 (2005)MathSciNet CrossRef MATH
  7.Gebremedhin, A.H., Nguyen, D., Patwary, M.M.A., Pothen, A.: ColPack: Software for graph coloring and related problems in scientific computing. ACM Trans. Math. Softw. 40(1), 1–31 (2013)MathSciNet CrossRef MATH
  8.Gilbert, J.R., Moler, C., Schreiber, R.: Sparse matrices in matlab: design and implementation. SIAM J. Matrix Anal. Appl. 13(1), 333–356 (1992)MathSciNet CrossRef MATH
  9.Griewank, A., Walther, A.: Evaluating Derivatives: Principles and Techniques of AlgorithmicDifferentiation, 2nd edn. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (2008)CrossRef MATH
  10.Griewank, A., Mitev, C.: Detecting Jacobian sparsity patterns by Bayesian probing. Math. Prog. 93(1), 1–25 (2002)MathSciNet CrossRef MATH
  11.Hossain, A.S., Steihaug, T.: Computing a sparse Jacobian matrix by rows and columns. Optim. Methods Softw. 10, 33–48 (1998)MathSciNet CrossRef MATH
  12.Hossain, S., Steihaug, T.: Graph coloring in the estimation of sparse derivative matrices: Instances and applications. Discrete Appl. Math. 156(2), 280–288 (2008)MathSciNet CrossRef MATH
  13.Hossain, S., Steihaug, T.: Graph models and their efficient implementation for sparse jacobian matrix determination. Discrete Appl. Math. 161(12), 1747–1754 (2013)MathSciNet CrossRef MATH
  14.Newsam, G.N., Ramsdell, J.D.: Estimation of sparse Jacobian matrices. SIAM J. Alg. Disc. Meth. 4(3), 404–417 (1983)MathSciNet CrossRef MATH
  15.Park, J.-S., Penner, M., Prasanna, V.K.: Optimizing graph algorithms for improved cache performance. IEEE Trans. Parallel Distrib. Syst. 15(9), 769–782 (2004)CrossRef
  
• 作者单位：Mahmudul Hasan (17)
  Shahadat Hossain (17)
  Ahamad Imtiaz Khan (17)
  Nasrin Hakim Mithila (17)
  Ashraful Huq Suny (17)
  
  17. University of Lethbridge, Lethbridge, AB, Canada
  
• 丛书名：Mathematical Software ¨C ICMS 2016
• ISBN：978-3-319-42432-3
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349
• 卷排序：9725

文摘

We describe the main design features of DSJM (Determine Sparse Jacobian Matrices), a software toolkit written in standard C++ that enables direct determination of sparse Jacobian matrices. Our design exploits the recently proposed unifying framework “pattern graph” and employs cache-friendly array-based sparse data structures. The DSJM implements a greedy grouping (coloring) algorithm and several ordering heuristics. In our numerical testing on a suite of large-scale test instances DSJM consistently produced better timing and partitions compared with a similar software.