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), 6988
MSC:
Primary 65F50; Secondary 65N20
MathSciNet review:
744925
Fulltext PDF Free Access
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
(9,623l)
 [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
(84f:05043), http://dx.doi.org/10.1137/0720013
 [3]
T. F. Coleman & J. J. Moré, Software for Estimating Sparse Jacobian Matrices, Technical Report ANL8237, Argonne National Laboratory, Argonne, Illinois, 1982.
 [4]
T. F. Coleman & J. J. Moré, Estimation of Sparse Hessian Matrices and Graph Colouring Problems, Technical Report ANL81535, 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. 117119.
 [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
(85c:65016), http://dx.doi.org/10.1007/BF02592052
 [8]
David
K. Melgaard and Richard
F. Sincovec, General software for twodimensional nonlinear partial
differential equations, ACM Trans. Math. Software 7
(1981), no. 1, 106–125. MR 607354
(83a:65082), http://dx.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 (84k:65058), http://dx.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
(80m:65013), http://dx.doi.org/10.1137/0716078
 [11]
L.
K. Schubert, Modification of a quasiNewton method
for nonlinear equations with a sparse Jacobian, Math. Comp. 24 (1970), 27–30. MR 0258276
(41 #2923), http://dx.doi.org/10.1090/S00255718197002582769
 [12]
D.
F. Shanno, On variablemetric methods for sparse
Hessians, Math. Comp. 34
(1980), no. 150, 499–514. MR 559198
(81j:65077), http://dx.doi.org/10.1090/S00255718198005591982
 [13]
M. N. Thapa, Optimization of Unconstrained Problems With Sparse Hessian MatricesNewtonType Methods, Technical Report SOL828, 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
(56 #13577), http://dx.doi.org/10.1090/S00255718197704553384
 [15]
Ph. L. Toint, Estimation of Sparse Hessian Matrices: A Block Substitution Procedure and its Application to the MultiDiagonal Case, Technical Report 81/10, Dept. of Math., FUN Namur, Belgium, 1981.
 [1]
 W. G. Bickley, "Finite difference formulae for the square lattice," Quart. J. Mech. Appl. Math., v. 1, 1948, pp. 3542. MR 0025282 (9:623l)
 [2]
 T. F. Coleman & J. J. Moré, "Estimation of sparse Jacobian matrices and graph coloring problems," SIAM J. Numer. Anal., v. 20, 1983, pp. 187209. MR 687376 (84f:05043)
 [3]
 T. F. Coleman & J. J. Moré, Software for Estimating Sparse Jacobian Matrices, Technical Report ANL8237, Argonne National Laboratory, Argonne, Illinois, 1982.
 [4]
 T. F. Coleman & J. J. Moré, Estimation of Sparse Hessian Matrices and Graph Colouring Problems, Technical Report ANL81535, 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. 117119.
 [6]
 S. W. Golomb, Polyominoes, Chas. Schribner's Sons, New York, 1965.
 [7]
 S. T. McCormick, "Optimal approximation of sparse Hessians and its equivalence to a graph coloring problem," Math. Programming, v. 26, 1983, pp. 153171. MR 700644 (85c:65016)
 [8]
 D. K. Melgaard & R. F. Sincovec, "General software for twodimensional nonlinear partial differential equations," ACM Trans. Math. Software, v. 7, 1981, pp. 106125. MR 607354 (83a:65082)
 [9]
 G. N. Newsam & J. D. Ramsdell, "Estimation of sparse Jacobian matrices," SIAM J. Algebraic Discrete Methods, v. 4, 1983, pp. 404418. MR 711348 (84k:65058)
 [10]
 M. J. D. Powell & Ph. L. Toint, "On the estimation of sparse Hessian matrices," SIAM J. Numer. Anal., v. 16, 1979, pp. 10601074. MR 551326 (80m:65013)
 [11]
 L. K. Schubert, "Modification of a quasiNewton method for nonlinear equations with a sparse Jacobian," Math. Comp., v. 24, 1970, pp. 2730. MR 0258276 (41:2923)
 [12]
 D. F. Shanno, "On variable metric methods for sparse Hessians," Math. Comp., v. 34, 1980, pp. 499514. MR 559198 (81j:65077)
 [13]
 M. N. Thapa, Optimization of Unconstrained Problems With Sparse Hessian MatricesNewtonType Methods, Technical Report SOL828, Stanford University, Stanford, Calif., 1982.
 [14]
 Ph. L. Toint, "On sparse and symmetric matrix updating subject to a linear equation," Math. Comp., v. 31, 1977, pp. 954961. MR 0455338 (56:13577)
 [15]
 Ph. L. Toint, Estimation of Sparse Hessian Matrices: A Block Substitution Procedure and its Application to the MultiDiagonal Case, Technical Report 81/10, Dept. of Math., FUN Namur, Belgium, 1981.
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
65F50,
65N20
Retrieve articles in all journals
with MSC:
65F50,
65N20
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718198407449255
PII:
S 00255718(1984)07449255
Keywords:
Finite differences,
sparsity,
coverings
Article copyright:
© Copyright 1984 American Mathematical Society
