A homotopy method with adaptive basis selection for computing multiple solutions of differential equations. (English) Zbl 07161476
Summary: The homotopy continuation method has been widely used to compute multiple solutions of nonlinear differential equations, but the computational cost grows exponentially based on the traditional finite difference and finite element discretizations. In this work, we presented a new method by constructing a spectral approximation space adaptively based on a greedy algorithm for nonlinear differential equations. Then multiple solutions were computed by the homotopy continuation method on this low-dimensional approximation space. Various numerical examples were given to illustrate the feasibility and the efficiency of this new approach.
MSC:
| 65Lxx | Numerical methods for ordinary differential equations |
| 65Hxx | Nonlinear algebraic or transcendental equations |
| 34Bxx | Boundary value problems for ordinary differential equations |
Keywords:
multiple solutions; nonlinear differential equations; polynomial systems; homotopy continuationReferences:
| [1] | Allgower, E.; Bates, D.; Sommese, A.; Wampler, C., Solution of polynomial systems derived from differential equations, Computing, 76, 1-2, 1-10 (2006) · Zbl 1086.65075 · doi:10.1007/s00607-005-0132-4 |
| [2] | Allgower, E.; Cruceanu, S.; Tavener, S., Application of numerical continuation to compute all solutions of semilinear elliptic equations, Adv. Geom., 9, 3, 371-400 (2009) · Zbl 1169.65105 · doi:10.1515/ADVGEOM.2009.020 |
| [3] | Bates, D.; Hauenstein, J.; Sommese, A.; Wampler, C., Adaptive multiprecision path tracking, SIAM J. Numer. Anal., 46, 2, 722-746 (2008) · Zbl 1162.65026 · doi:10.1137/060658862 |
| [4] | Bates, D.; Hauenstein, J.; Sommese, A.; Wampler, C., Stepsize control for path tracking, Contemp. Math., 496, 3, 21-31 (2009) · Zbl 1181.65071 · doi:10.1090/conm/496/09717 |
| [5] | Bates, D.; Hauenstein, J.; Sommese, A.; Wampler, C., Numerically Solving Polynomial Systems with Bertini (2013), Philadelphia: SIAM, Philadelphia · Zbl 1295.65057 |
| [6] | Bates, Dj; Hauenstein, Jd; Sommese, Aj; Wampler, Cw, Adaptive multiprecision path tracking, SIAM J. Nume. Anal., 46, 2, 722-746 (2008) · Zbl 1162.65026 · doi:10.1137/060658862 |
| [7] | Bates, Dj; Hauenstein, Jd; Sommese, Aj; Wampler, Cw, Numerically Solving Polynomial Systems with Bertini (2013), Philadelphia: SIAM, Philadelphia · Zbl 1295.65057 |
| [8] | Bauer, L.; Keller, Hb; Reiss, E., Multiple eigenvalues lead to secondary bifurcation, SIAM Rev., 17, 1, 101-122 (1975) · doi:10.1137/1017006 |
| [9] | Bernardi, C.; Maday, Y., Spectral methods, Handb. Numer. Anal., 5, 209-485 (1997) |
| [10] | Binev, P.; Cohen, A.; Dahmen, W.; Devore, R.; Petrova, G.; Wojtaszczyk, P., Convergence rates for greedy algorithms in reduced basis methods, SIAM J. Math. Anal., 43, 1457-1472 (2011) · Zbl 1229.65193 · doi:10.1137/100795772 |
| [11] | Braun, M.; Golubitsky, M., Differential Equations and Their Applications (1983), New York: Springer, New York · Zbl 0528.34001 |
| [12] | Breuer, B.; Mckenna, P.; Plum, M., Multiple solutions for a semilinear boundary value problem: a computational multiplicity proof, J. Differ. Equ., 195, 1, 243-269 (2003) · Zbl 1156.35359 · doi:10.1016/S0022-0396(03)00186-4 |
| [13] | Chen, C.; Xie, Z., Structure of multiple solutions for nonlinear differential equations, Sci. China Ser. A Math., 47, 1, 172-180 (2004) · Zbl 1090.35075 · doi:10.1360/04za0016 |
| [14] | Chen, F.; Shen, J.; Yu, H., A new spectral element method for pricing european options under the black-scholes and merton jump diffusion models, J. Sci. Comput., 52, 3, 499-518 (2012) · Zbl 1254.91745 · doi:10.1007/s10915-011-9556-5 |
| [15] | Chen, Y.; Hesthaven, J.; Maday, Y.; Rodrguez, J., Improved successive constraint method based a posteriori error estimate for reduced basis approximation of 2D Maxwell’s problem, ESAIM Math. Model. Numer. Anal., 43, 6, 1099-1116 (2009) · Zbl 1181.78019 · doi:10.1051/m2an/2009037 |
| [16] | Chen, Y.; Hesthaven, Js; Maday, Y.; Rodríguez, J., Certified reduced basis methods and output bounds for the harmonic Maxwell’s equations, SIAM J. Sci. Comput., 32, 2, 970-996 (2010) · Zbl 1213.78011 · doi:10.1137/09075250X |
| [17] | Chossat, P.; Golubitsky, M., Symmetry-increasing bifurcation of chaotic attractors, Physica D, 32, 3, 423-436 (1988) · Zbl 0668.58038 · doi:10.1016/0167-2789(88)90066-8 |
| [18] | Cristini, V.; Li, X.; Lowengrub, J.; Wise, S., Nonlinear simulations of solid tumor growth using a mixture model: invasion and branching, J. Math. Biol., 58, 4, 723-763 (2009) · Zbl 1311.92039 · doi:10.1007/s00285-008-0215-x |
| [19] | Cristini, V.; Lowengrub, J.; Nie, Q., Nonlinear simulation of tumor growth, J. Math. Biol., 46, 3, 191-224 (2003) · Zbl 1023.92013 · doi:10.1007/s00285-002-0174-6 |
| [20] | Fontelos, M.; Friedman, A., Symmetry-breaking bifurcations of free boundary problems in three dimensions, Asymptot. Anal., 35, 3, 187-206 (2003) · Zbl 1054.35145 |
| [21] | Friedman, A., Free boundary problems in biology, Philos. Trans. R. Soc. A, 373, 2050, 20140368 (2015) · Zbl 1353.35291 · doi:10.1098/rsta.2014.0368 |
| [22] | Friedman, A.; Hao, W., A mathematical model of atherosclerosis with reverse cholesterol transport and associated risk factors, Bull. Math. Biol., 77, 5, 758-781 (2015) · Zbl 1334.92198 · doi:10.1007/s11538-014-0010-3 |
| [23] | Friedman, A.; Hu, B., Bifurcation from stability to instability for a free boundary problem arising in a tumor model, Arch. Ration. Mech. Anal., 180, 2, 293-330 (2006) · Zbl 1087.92039 · doi:10.1007/s00205-005-0408-z |
| [24] | Friedman, A.; Hu, B., Bifurcation for a free boundary problem modeling tumor growth by Stokes equation, SIAM J. Math. Anal., 39, 1, 174-194 (2007) · Zbl 1136.35107 · doi:10.1137/060656292 |
| [25] | Friedman, A.; Reitich, F., Symmetry-breaking bifurcation of analytic solutions to free boundary problems: an application to a model of tumor growth, Trans. Am. Math. Soc., 353, 4, 1587-1634 (2001) · Zbl 0983.35019 · doi:10.1090/S0002-9947-00-02715-X |
| [26] | Golubitsky, M.; Stewart, I., The Symmetry Perspective: From Equilibrium to Chaos in Phase Space and Physical Space (2003), New York: Springer, New York |
| [27] | Golubitsky, M.; Stewart, I., Singularities and Groups in Bifurcation Theory (2012), New York: Springer, New York |
| [28] | Grepl, M.; Patera, A., A posteriori error bounds for reduced-basis approximations of parametrized parabolic partial differential equations, ESAIM Math. Model. Numer. Anal., 39, 1, 157-181 (2005) · Zbl 1079.65096 · doi:10.1051/m2an:2005006 |
| [29] | Haber, R.; Unbehauen, H., Structure identification of nonlinear dynamic systems survey on input/output approaches, Automatica, 26, 4, 651-677 (1990) · Zbl 0721.93023 · doi:10.1016/0005-1098(90)90044-I |
| [30] | Hao, W.; Crouser, E.; Friedman, A., Mathematical model of sarcoidosis, Proc. Nat. Acad. Sci., 111, 45, 16065-16070 (2014) · Zbl 1355.92049 · doi:10.1073/pnas.1417789111 |
| [31] | Hao, W.; Friedman, A., The ldl-hdl profile determines the risk of atherosclerosis: a mathematical model, PLoS ONE, 9, 3, e90497 (2014) · doi:10.1371/journal.pone.0090497 |
| [32] | Hao, W.; Hauenstein, J.; Hu, B.; Liu, Y.; Sommese, A.; Zhang, Y-T, Bifurcation for a free boundary problem modeling the growth of a tumor with a necrotic core, Nonlinear Anal. Real World Appl., 13, 2, 694-709 (2012) · Zbl 1238.35193 · doi:10.1016/j.nonrwa.2011.08.010 |
| [33] | Hao, W.; Hauenstein, J.; Hu, B.; Sommese, A., A bootstrapping approach for computing multiple solutions of differential equations, J. Comput. Appl. Math., 258, 181-190 (2014) · Zbl 1294.65085 · doi:10.1016/j.cam.2013.09.007 |
| [34] | Hao, W.; Hauenstein, J.; Shu, C-W; Sommese, A.; Xu, Z.; Zhang, Y-T, A homotopy method based on weno schemes for solving steady state problems of hyperbolic conservation laws, J. Comput. Phys., 250, 332-346 (2013) · Zbl 1349.65558 · doi:10.1016/j.jcp.2013.05.008 |
| [35] | Hao, W.; Nepomechie, R.; Sommese, A., Completeness of solutions of bethe’s equations, Phys. Rev. E, 88, 5, 052113 (2013) · doi:10.1103/PhysRevE.88.052113 |
| [36] | Hao, W.; Nepomechie, R.; Sommese, A., Singular solutions, repeated roots and completeness for higher-spin chains, J. Stat. Mech Theory Exp., 2014, 3, P03024 (2014) · Zbl 1456.82268 · doi:10.1088/1742-5468/2014/03/P03024 |
| [37] | Hao, W.; Sommese, A.; Zeng, Z., Algorithm 931: an algorithm and software for computing multiplicity structures at zeros of nonlinear systems, ACM Trans. Math. Softw. TOMS, 40, 1, 5-20 (2013) · Zbl 1295.65058 |
| [38] | Hou, T.; Lowengrub, J.; Shelley, M., Boundary integral methods for multicomponent fluids and multiphase materials, J. Comput. Phys., 169, 2, 302-362 (2001) · Zbl 1046.76029 · doi:10.1006/jcph.2000.6626 |
| [39] | Li, T-Y; Sauer, T.; Yorke, J., The Cheater’s homotopy: an efficient procedure for solving systems of polynomial equations, SIAM J. Numer. Anal., 26, 5, 1241-1251 (1989) · Zbl 0689.65032 · doi:10.1137/0726069 |
| [40] | Li, T-Y; Zeng, Z., Homotopy-determinant algorithm for solving nonsymmetric eigenvalue problems, Math. Comput., 59, 200, 483-502 (1992) · Zbl 0783.65034 · doi:10.1090/S0025-5718-1992-1151113-4 |
| [41] | Morgan, A.; Sommese, A., Computing all solutions to polynomial systems using homotopy continuation, Appl. Math. Comput., 24, 2, 115-138 (1987) · Zbl 0635.65058 |
| [42] | Morgan, A.; Sommese, A., A homotopy for solving general polynomial systems that respects m-homogeneous structures, Appl. Math. Comput., 24, 2, 101-113 (1987) · Zbl 0635.65057 |
| [43] | Peaceman, D.; Rachford, H., The numerical solution of parabolic and elliptic differential equations, J. Soc. Ind. Appl. Math., 3, 1, 28-41 (1955) · Zbl 0067.35801 · doi:10.1137/0103003 |
| [44] | Pearson, J., Complex patterns in a simple system, Science, 261, 3, 189-189 (1993) · doi:10.1126/science.261.5118.189 |
| [45] | Pousin, J.; Rappaz, J., Consistency, stability, a priori and a posteriori errors for petrov-galerkin methods applied to nonlinear problems, Numer. Math., 69, 2, 213-231 (1994) · Zbl 0822.65034 · doi:10.1007/s002110050088 |
| [46] | Rabier, P.; Rheinboldt, W., On a computational method for the second fundamental tensor and its application to bifurcation problems, Numer. Math., 57, 1, 681-694 (1990) · Zbl 0699.65037 · doi:10.1007/BF01386437 |
| [47] | Rheinboldt, W., Numerical methods for a class of finite dimensional bifurcation problems, SIAM J. Numer. Anal., 15, 1, 1-11 (1978) · Zbl 0389.65024 · doi:10.1137/0715001 |
| [48] | Rheinboldt, W., Numerical analysis of continuation methods for nonlinear structural problems, Comput. Struct., 13, 1, 103-113 (1981) · Zbl 0465.65030 · doi:10.1016/0045-7949(81)90114-0 |
| [49] | Rheinboldt, W.; Burkardt, J., A locally parameterized continuation process, ACM Trans. Math. Softw. TOMS, 9, 2, 215-235 (1983) · Zbl 0516.65029 · doi:10.1145/357456.357460 |
| [50] | Rozza, G.; Huynh, D.; Patera, A., Reduced basis approximation and a posteriori error estimation for affinely parametrized elliptic coercive partial differential equations, Arch. Comput. Methods Eng., 15, 3, 1 (2007) · doi:10.1007/BF03024948 |
| [51] | Rozza, G.; Huynh, D.; Patera, A., Reduced basis approximation and a posteriori error estimation for affinely parametrized elliptic coercive partial differential equations, Arch. Comput. Methods Eng., 15, 3, 229-275 (2008) · Zbl 1304.65251 · doi:10.1007/s11831-008-9019-9 |
| [52] | Shen, J.; Tang, T.; Wang, L., Spectral Methods: Algorithms, Analysis and Applications (2011), New York: Springer, New York · Zbl 1227.65117 |
| [53] | Smith, G., Numerical Solution of Partial Differential Equations: Finite Difference Methods (1985), Oxford: Oxford University Press, Oxford · Zbl 0576.65089 |
| [54] | Sommese, A.; Verschelde, J.; Wampler, C., Homotopies for intersecting solution components of polynomial systems, SIAM J. Numer. Anal., 42, 4, 1552-1571 (2004) · Zbl 1108.13308 · doi:10.1137/S0036142903430463 |
| [55] | Sommese, A.; Verschelde, J.; Wampler, C., An intrinsic homotopy for intersecting algebraic varieties, J. Complex., 21, 4, 593-608 (2005) · Zbl 1108.13309 · doi:10.1016/j.jco.2004.09.007 |
| [56] | Sommese, A.; Wampler, C., The Numerical Solution of Systems of Polynomials Arising in Engineering and Science (2005), Singapore: World Scientific, Singapore · Zbl 1091.65049 |
| [57] | Strogatz, S., Nonlinear Dynamics and Chaos: With Applications to Physics, Biology, Chemistry, and Engineering (2014), Boulder: Westview press, Boulder |
| [58] | Turton, R.; Bailie, R.; Whiting, W.; Shaeiwitz, J., Analysis, Synthesis and Design of Chemical Processes (2008), London: Pearson Education, London |
| [59] | Veroy, K., Prud’Homme, C., Rovas, D., Patera, A.: A posteriori error bounds for reduced-basis approximation of parametrized noncoercive and nonlinear elliptic partial differential equations. In: 16th AIAA Computational Fluid Dynamics Conference, p. 3847 (2003) · Zbl 1024.65104 |
| [60] | Xu, J., Two-grid discretization techniques for linear and nonlinear pdes, SIAM J. Numer. Anal., 33, 5, 1759-1777 (1996) · Zbl 0860.65119 · doi:10.1137/S0036142992232949 |
| [61] | Zhang, X.; Zhang, J.; Yu, B., Eigenfunction expansion method for multiple solutions of semilinear elliptic equations with polynomial nonlinearity, SIAM J. Numer. Anal., 51, 5, 2680-2699 (2013) · Zbl 1305.65174 · doi:10.1137/12088327X |
| [62] | Zhou, J., Solving multiple solution problems: computational methods and theory revisited, Commun. Appl. Math., 3, 1, 1-31 (2017) · Zbl 1389.35014 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
