Conjugate gradient predictor corrector method for solving large scale problems

Syam, Muhammed

doi:10.1090/S0025-5718-04-01689-8

Conjugate gradient predictor corrector method for solving large scale problems
HTML articles powered by AMS MathViewer

by Muhammed I. Syam PDF

Math. Comp. 74 (2005), 805-818 Request permission

Abstract:

In this paper, we give a new method for solving large scale problems. The basic idea of this method depends on implementing the conjugate gradient as a corrector into a continuation method. We use the Euler method as a predictor. Adaptive steplength control is used during the tracing of the solution curve. We present some of our experimental examples to demonstrate the efficiency of the method.

References

P. G. Ciarlet and J. L. Lions (eds.), Handbook of numerical analysis. Vol. V, Handbook of Numerical Analysis, V, North-Holland, Amsterdam, 1997. Techniques of scientific computing. Part 2. MR 1470224
E. L. Allgower, C.-S. Chien, K. Georg, and C.-F. Wang, Conjugate gradient methods for continuation problems, Proceedings of the International Symposium on Computational Mathematics (Matsuyama, 1990), 1991, pp. 1–16. MR 1146969, DOI 10.1016/0377-0427(91)90157-F
Randolph E. Bank and Tony F. Chan, PLTMGC: a multigrid continuation program for parameterized nonlinear elliptic systems, SIAM J. Sci. Statist. Comput. 7 (1986), no. 2, 540–559. MR 833920, DOI 10.1137/0907036
S. Bernstein, Sur la generalisation du probleme de Dirichlet., Math. Ann., 69 (1910), 82-136.
Tony F. C. Chan and H. B. Keller, Arc-length continuation and multigrid techniques for nonlinear elliptic eigenvalue problems, SIAM J. Sci. Statist. Comput. 3 (1982), no. 2, 173–194. MR 658631, DOI 10.1137/0903012
Shui Nee Chow and Jack K. Hale, Methods of bifurcation theory, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 251, Springer-Verlag, New York-Berlin, 1982. MR 660633, DOI 10.1007/978-1-4613-8159-4
T. Küpper and H. Weber (eds.), Numerical methods for bifurcation problems, Internationale Schriftenreihe zur Numerischen Mathematik [International Series of Numerical Mathematics], vol. 70, Birkhäuser Verlag, Basel, 1984. MR 821016, DOI 10.1007/978-3-0348-6256-1
Arthur I. Cohen, Rate of convergence of several conjugate gradient algorithms, SIAM J. Numer. Anal. 9 (1972), 248–259. MR 312728, DOI 10.1137/0709024
R. Fletcher, Practical methods of optimization, 2nd ed., A Wiley-Interscience Publication, John Wiley & Sons, Ltd., Chichester, 1987. MR 955799
C.B. Garci and W. I. Zangwill, Pathways to solutions, fixed points, and equilibria, Prentice-Hall, Englewood Cliffs, NJ, 1981.
R. Glowinski, H. B. Keller, and L. Reinhart, Continuation-conjugate gradient methods for the least squares solution of nonlinear boundary value problems, SIAM J. Sci. Statist. Comput. 6 (1985), no. 4, 793–832. MR 801174, DOI 10.1137/0906055
Gene H. Golub and Charles F. Van Loan, Matrix computations, 2nd ed., Johns Hopkins Series in the Mathematical Sciences, vol. 3, Johns Hopkins University Press, Baltimore, MD, 1989. MR 1002570
Floyd J. Gould and Jon W. Tolle, Complementary pivoting on a pseudomanifold structure with applications in the decision sciences, Sigma Series in Applied Mathematics, vol. 2, Heldermann Verlag, Berlin, 1983. MR 712289
Kurt Georg, Matrix-free numerical continuation and bifurcation, Numer. Funct. Anal. Optim. 22 (2001), no. 3-4, 303–320. International Workshops on Numerical Methods and Verification of Solutions, and on Numerical Function Analysis (Ehime/Shimane, 1999). MR 1849322, DOI 10.1081/NFA-100105106
Philip E. Gill, Walter Murray, and Margaret H. Wright, Practical optimization, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], London-New York, 1981. MR 634376
Sam Perlis, Maximal orders in rational cyclic algebras of composite degree, Trans. Amer. Math. Soc. 46 (1939), 82–96. MR 15, DOI 10.1090/S0002-9947-1939-0000015-X
James P. Keener and Herbert B. Keller, Perturbed bifurcation theory, Arch. Rational Mech. Anal. 50 (1973), 159–175. MR 336479, DOI 10.1007/BF00703966
H. B. Keller, Lectures on numerical methods in bifurcation problems, Tata Institute of Fundamental Research Lectures on Mathematics and Physics, vol. 79, Published for the Tata Institute of Fundamental Research, Bombay; by Springer-Verlag, Berlin, 1987. With notes by A. K. Nandakumaran and Mythily Ramaswamy. MR 910499
Herbert B. Keller, Nonlinear bifurcation, J. Differential Equations 7 (1970), 417–434. MR 264255, DOI 10.1016/0022-0396(70)90090-2
Herbert B. Keller, Numerical solution of bifurcation and nonlinear eigenvalue problems, Applications of bifurcation theory (Proc. Advanced Sem., Univ. Wisconsin, Madison, Wis., 1976) Publ. Math. Res. Center, No. 38, Academic Press, New York, 1977, pp. 359–384. MR 0455353
F. Klein, Neue beitrage zur Riemannschen Funktionentheorie, Math. Ann., 21( 1882-1883).
David S. Kershaw, The incomplete Cholesky-conjugate gradient method for the iterative solution of systems of linear equations, J. Comput. Phys. 26 (1978), no. 1, 43–65. MR 488669, DOI 10.1016/0021-9991(78)90098-0
E. Lahaye, Une methode de resolution d’une categorie d’equations transcendantes, C. R. Acad. Sci. Paris, 198 (1934), 1840-1842.
J. Leray and J. Schauder, Topologie et equations fonctioneles, Ann. Sci. Ecole Norm. Sup., 51(1934), 45-78.
W. Mackens, Numerical differentiation of implicitly defined space curves, Computing 41 (1989), no. 3, 237–260 (English, with German summary). MR 988238, DOI 10.1007/BF02259095
J. E. Marsden and A. J. Tromba, Vector calculus, Third edition, W. H. Freeman and Company, New Your, 1988, 75.
G. P. McCormick and K. Ritter, Alternate proofs of the convergence properties of the conjugate-gradient method, J. Optim. Theory Appl., 13(1974), 497-518.
Hans D. Mittelmann and Dirk Roose (eds.), Continuation techniques and bifurcation problems, International Series of Numerical Mathematics, vol. 92, Birkhäuser Verlag, Basel, 1990. Reprinted from J. Comput. Appl. Math. 26 (1989), no. 1-2. MR 1057193, DOI 10.1007/978-3-0348-5681-2
H. Poincare, Sur les courbes define par une equation differentielle, I-IV, Oeuvres I. Gauthier-Villars, Paris, 1881-1886.
E. Polak and G. Ribière, Note sur la convergence de méthodes de directions conjuguées, Rev. Française Informat. Recherche Opérationnelle 3 (1969), no. 16, 35–43 (French, with Loose English summary). MR 0255025
Werner C. Rheinboldt, Numerical analysis of continuation methods for nonlinear structural problems, Comput. & Structures 13 (1981), no. 1-3, 103–113. MR 616722, DOI 10.1016/0045-7949(81)90114-0
Rüdiger Seydel, From equilibrium to chaos, Elsevier, New York, 1988. Practical bifurcation and stability analysis. MR 927090
H.I. Siyyam and M.I. Syam, The modified trapezoidal rule for line integrals, J. Comput. Appl. Math. 84 (1997), 1-14.
Muhammed I. Syam and Hani I. Siyyam, Numerical differentiation of implicitly defined curves, J. Comput. Appl. Math. 108 (1999), no. 1-2, 131–144. MR 1705732, DOI 10.1016/S0377-0427(99)00106-5
M. I. Syam, Interpolation predictors over implicitly defined curves, Comput. Math. Appl. 44 (2002), no. 8-9, 1067–1076. MR 1937567, DOI 10.1016/S0898-1221(02)00215-8
Michael J. Todd, The computation of fixed points and applications, Lecture Notes in Economics and Mathematical Systems, Vol. 124, Springer-Verlag, Berlin-New York, 1976. MR 0410732, DOI 10.1007/978-3-642-50327-6
K. H. Winters, K. A. Cliffe, The prediction of critical points for thermal explosions in a finite volume, Combustion and Flame, 62 (1985), 13-20.