Optimal estimation of Jacobian and Hessian matrices that arise in finite difference calculations

Authors:
D. Goldfarb and Ph. L. Toint

Journal:
Math. Comp. **43** (1984), 69-88

MSC:
Primary 65F50; Secondary 65N20

DOI:
https://doi.org/10.1090/S0025-5718-1984-0744925-5

MathSciNet review:
744925

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper, the problem of estimating Jacobian and Hessian matrices arising in the finite difference approximation of partial differential equations is considered. Using the notion of computational molecule or stencil, schemes are developed that require the minimum number of differences to estimate these matrices. A procedure applicable to more complicated structures is also given.

**[1]**W. G. Bickley,*Finite difference formulae for the square lattice*, Quart. J. Mech. Appl. Math.**1**(1948), 35–42. MR**0025282**, https://doi.org/10.1093/qjmam/1.1.35**[2]**Thomas F. Coleman and Jorge J. Moré,*Estimation of sparse Jacobian matrices and graph coloring problems*, SIAM J. Numer. Anal.**20**(1983), no. 1, 187–209. MR**687376**, https://doi.org/10.1137/0720013**[3]**T. F. Coleman & J. J. Moré,*Software for Estimating Sparse Jacobian Matrices*, Technical Report ANL-82-37, Argonne National Laboratory, Argonne, Illinois, 1982.**[4]**T. F. Coleman & J. J. Moré,*Estimation of Sparse Hessian Matrices and Graph Colouring Problems*, Technical Report ANL-81-535, Argonne National Laboratory, Argonne, Illinois, 1982.**[5]**A. Curtis, M. J. D. Powell & J. Reíd, "On the estimation of sparse Jacobian matrices,"*J. Inst. Math. Appl.*, v. 13, 1974, pp. 117-119.**[6]**S. W. Golomb,*Polyominoes*, Chas. Schribner's Sons, New York, 1965.**[7]**S. Thomas McCormick,*Optimal approximation of sparse Hessians and its equivalence to a graph coloring problem*, Math. Programming**26**(1983), no. 2, 153–171. MR**700644**, https://doi.org/10.1007/BF02592052**[8]**David K. Melgaard and Richard F. Sincovec,*General software for two-dimensional nonlinear partial differential equations*, ACM Trans. Math. Software**7**(1981), no. 1, 106–125. MR**607354**, https://doi.org/10.1145/355934.355941**[9]**Garry N. Newsam and John D. Ramsdell,*Estimation of sparse Jacobian matrices*, SIAM J. Algebraic Discrete Methods**4**(1983), no. 3, 404–418. MR**711348**, https://doi.org/10.1137/0604041**[10]**M. J. D. Powell and Ph. L. Toint,*On the estimation of sparse Hessian matrices*, SIAM J. Numer. Anal.**16**(1979), no. 6, 1060–1074. MR**551326**, https://doi.org/10.1137/0716078**[11]**L. K. Schubert,*Modification of a quasi-Newton method for nonlinear equations with a sparse Jacobian*, Math. Comp.**24**(1970), 27–30. MR**0258276**, https://doi.org/10.1090/S0025-5718-1970-0258276-9**[12]**D. F. Shanno,*On variable-metric methods for sparse Hessians*, Math. Comp.**34**(1980), no. 150, 499–514. MR**559198**, https://doi.org/10.1090/S0025-5718-1980-0559198-2**[13]**M. N. Thapa,*Optimization of Unconstrained Problems With Sparse Hessian Matrices-Newton-Type Methods*, Technical Report SOL82-8, Stanford University, Stanford, Calif., 1982.**[14]**Ph. L. Toint,*On sparse and symmetric matrix updating subject to a linear equation*, Math. Comp.**31**(1977), no. no 140, 954–961. MR**0455338**, https://doi.org/10.1090/S0025-5718-1977-0455338-4**[15]**Ph. L. Toint,*Estimation of Sparse Hessian Matrices*:*A Block Substitution Procedure and its Application to the Multi-Diagonal Case*, Technical Report 81/10, Dept. of Math., FUN Namur, Belgium, 1981.

Retrieve articles in *Mathematics of Computation*
with MSC:
65F50,
65N20

Retrieve articles in all journals with MSC: 65F50, 65N20

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1984-0744925-5

Keywords:
Finite differences,
sparsity,
coverings

Article copyright:
© Copyright 1984
American Mathematical Society