Movatterモバイル変換

[0]ホーム
URL:

Skip to main content
Springer Nature Link
Log in

Tensor methods for large sparse systems of nonlinear equations

  • Published:
Mathematical Programming Submit manuscript

    We’re sorry, something doesn't seem to be working properly.

    Please try refreshing the page. If that doesn't work, please contact support so we can address the problem.

Abstract

This paper introduces tensor methods for solving large sparse systems of nonlinear equations. Tensor methods for nonlinear equations were developed in the context of solving small to medium-sized dense problems. They base each iteration on a quadratic model of the nonlinear equations, where the second-order term is selected so that the model requires no more derivative or function information per iteration than standard linear model-based methods, and hardly more storage or arithmetic operations per iteration. Computational experiments on small to medium-sized problems have shown tensor methods to be considerably more efficient than standard Newton-based methods, with a particularly large advantage on singular problems. This paper considers the extension of this approach to solve large sparse problems. The key issue considered is how to make efficient use of sparsity in forming and solving the tensor model problem at each iteration. Accomplishing this turns out to require an entirely new way of solving the tensor model that successfully exploits the sparsity of the Jacobian, whether the Jacobian is nonsingular or singular. We develop such an approach and, based upon it, an efficient tensor method for solving large sparse systems of nonlinear equations. Test results indicate that this tensor method is significantly more efficient and robust than an efficient sparse Newton-based method, in terms of iterations, function evaluations, and execution time. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.

This is a preview of subscription content,log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Similar content being viewed by others

References

  1. Å. Björck, I.S. Duff, A direct method for the solution of sparse linear least squares problems, Linear Algebra Appl. 34 (1980) 43–67.

    Google Scholar 

  2. B.M. Averick, R.G. Carter, J.J. Moré, G.L. Xue, The MINPACK-2 test problem collection, Preprint MCS-P153-0692, Mathematics and Computer Science Division, Argonne National Laboratory, 1992.

  3. A. Bouaricha, Solving Large Sparse Systems of Nonlinear Equations and Nonlinear Least Squares Problems Using Tensor Methods on Sequential and Parallel Computers, PhD Thesis, Computer Science Department, University of Colorado at Boulder, 1992.

  4. A. Bouaricha, R.B. Schnabel, Algorithm 768: TENSOLVE: A software package for solving systems of nonlinear equations and nonlinear least squares problems using tensor methods, ACM Trans. Math. Software 23 (1997) 174–195.

    Google Scholar 

  5. A.E. Bryson, A.E. Ho, Applied Optimal Control, Chap. 2, Wiley, New York, 1975.

    Google Scholar 

  6. T.F. Coleman, B.S. Garbow, J.J. Moré, Fortran subroutines for estimating sparse Jacobian matrices, ACM Trans. Math. Software 10 (1984) 346–347.

    Google Scholar 

  7. T.F. Coleman, B.S. Garbow, J.J. Moré, Software for estimating sparse Jacobian matrices, ACM Trans. Math. Software 10 (1984) 329–345.

    Google Scholar 

  8. T.F. Coleman, J.J. Moré, Estimation of sparse Jacobian matrices and graph coloring problems, SIAM J. Numer. Anal. 20 (1983) 187–207.

    Google Scholar 

  9. D.W. Decker, C.T. Kelly, Newton's method at singular points I, SIAM J. Numer. Anal. 17 (1980) 66–70.

    Google Scholar 

  10. D.W. Decker, C.T. Kelly, Newton's method at singular points II, SIAM J. Numer. Anal. 17 (1980) 465–471.

    Google Scholar 

  11. I.S. Duff, MA28: A set of Fortran subroutines for sparse unsymmetric linear equations, Technical Report R-8730, AERE Harwell Laboratory, 1977.

  12. D. Feng, P. Frank, R.B. Schnabel, Local convergence analysis of tensor methods for nonlinear equations, Math. Programming 62 (1993) 427–459.

    Google Scholar 

  13. P.D. Frank, W.P. Huffman, Parallel solution of large and sparse nonlinear systems, Technical Report ECA-TR-128, Boeing Computer Services, 1989.

  14. Andreas Griewank, On automatic differentiation, in: Mathematical Programming: Recent Developments and Applications, Kluwer Academic Publishers, Dordrecht, 1989, pp. 83–108.

    Google Scholar 

  15. Andreas Griewank, George F. Corliss (Eds.), Automatic Differentiation of Algorithms: Theory, Implementation, and Application, Society for Industrial and Applied Mathematics, 1991.

  16. J.J. Moré, A collection of nonlinear model problems, in: E.L. Allgower, K. Georg (Eds.), Computational Solutions of Nonlinear Systems of Equations, Lecture Notes in Applied Mathematics, vol. 26, American Mathematical Society, Providence, RI, 1990, pp. 723–762.

    Google Scholar 

  17. J.J. Moré, B.S. Garbow, K.E. Hillstrom, Testing unconstrained optimization software, ACM Trans. Math. Software 7 (1981) 17–41.

    Google Scholar 

  18. J.J. Moré, D.C. Sorensen, Computing a trust region step, SIAM J. Sci. Statist. Comput. 4 (1983) 553–572.

    Google Scholar 

  19. N. Munksgaard, NS02: A Fortran subroutine for solving sparse sets of nonlinear equations by Powell's Dog-leg algorithm, Technical Report R-11047, AERE Harwell Laboratory, 1938.

  20. G. Peters, J.H. Wilkinson, The least squares problem and pseudo-inverses, Comput. J. 13 (1970) 309–316.

    Google Scholar 

  21. R.B. Schnabel, P.D. Frank, Tensor methods for nonlinear equations, SIAM J. Numer. Anal. 21 (1984) 815–843.

    Google Scholar 

  22. A. Bouaricha, R.B. Schnabel, Tensor methods for large, sparse nonlinear least squares problems, SIAM J. Scientific Comput. (to appear).

Download references

Author information

Authors and Affiliations

  1. MCS Division, Argonne National Laboratory, 60439, Argonne, IL, USA

    Ali Bouaricha

  2. Department of Computer Science, University of Colorado, 80309-0430, Boulder, CO, USA

    Robert B. Schnabel

Authors
  1. Ali Bouaricha

    You can also search for this author inPubMed Google Scholar

  2. Robert B. Schnabel

    You can also search for this author inPubMed Google Scholar

Additional information

Work supported by the Mathematical, Information, and Computational Sciences Division subprogram of the Office of Computational and Technology Research, US Department of Energy, under Contract W-31-109-Eng-38, by the National Aerospace Agency under Purchase Order L25935D, and by the National Science Foundation, through the Center for Research on Parallel Computation, under Cooperative Agreement No. CCR-9120008.

Research supported by AFOSR Grants No. AFOSR-90-0109 and F49620-94-1-0101, ARO Grants No. DAAL03-91-G-0151 and DAAH04-94-G-0228, and NSF Grant No. CCR-9101795.

Rights and permissions

About this article

Access this article

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Advertisement

[8]ページ先頭
©2009-2025 Movatter.jp