{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,23]],"date-time":"2026-10-23T05:47:30Z","timestamp":1792734450564,"version":"4.5.0"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2020,8,24]],"date-time":"2020-08-24T00:00:00Z","timestamp":1598227200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,8,24]],"date-time":"2020-08-24T00:00:00Z","timestamp":1598227200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100009767","name":"Heriot-Watt University","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100009767","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Numer. Math."],"published-print":{"date-parts":[[2020,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The <jats:italic>p<\/jats:italic>-Laplacian is a nonlinear partial differential equation, parametrized by <jats:inline-formula><jats:alternatives><jats:tex-math>$$p \\in [1,\\infty ]$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n<mml:mrow>\n<mml:mi>p<\/mml:mi>\n<mml:mo>\u2208<\/mml:mo>\n<mml:mo>[<\/mml:mo>\n<mml:mn>1<\/mml:mn>\n<mml:mo>,<\/mml:mo>\n<mml:mi>\u221e<\/mml:mi>\n<mml:mo>]<\/mml:mo>\n<\/mml:mrow>\n<\/mml:math><\/jats:alternatives><\/jats:inline-formula>. We provide new numerical algorithms, based on the barrier method, for solving the <jats:italic>p<\/jats:italic>-Laplacian numerically in <jats:inline-formula><jats:alternatives><jats:tex-math>$$O(\\sqrt{n}\\log n)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n<mml:mrow>\n<mml:mi>O<\/mml:mi>\n<mml:mo>(<\/mml:mo>\n<mml:msqrt>\n<mml:mi>n<\/mml:mi>\n<\/mml:msqrt>\n<mml:mo>log<\/mml:mo>\n<mml:mi>n<\/mml:mi>\n<mml:mo>)<\/mml:mo>\n<\/mml:mrow>\n<\/mml:math><\/jats:alternatives><\/jats:inline-formula> Newton iterations for all <jats:inline-formula><jats:alternatives><jats:tex-math>$$p \\in [1,\\infty ]$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n<mml:mrow>\n<mml:mi>p<\/mml:mi>\n<mml:mo>\u2208<\/mml:mo>\n<mml:mo>[<\/mml:mo>\n<mml:mn>1<\/mml:mn>\n<mml:mo>,<\/mml:mo>\n<mml:mi>\u221e<\/mml:mi>\n<mml:mo>]<\/mml:mo>\n<\/mml:mrow>\n<\/mml:math><\/jats:alternatives><\/jats:inline-formula>, where <jats:italic>n<\/jats:italic> is the number of grid points. We confirm our estimates with numerical experiments.<\/jats:p>","DOI":"10.1007\/s00211-020-01141-z","type":"journal-article","created":{"date-parts":[[2020,8,24]],"date-time":"2020-08-24T20:02:37Z","timestamp":1598299357000},"page":"369-400","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":18,"title":["Efficient algorithms for solving the p-Laplacian in polynomial time"],"prefix":"10.1007","volume":"146","author":[{"given":"S\u00e9bastien","family":"Loisel","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2020,8,24]]},"reference":[{"key":"1141_CR1","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1137\/S1064827598343954","volume":"22","author":"KD Andersen","year":"1999","unstructured":"Andersen, K.D., Christiansen, E., Conn, A.R., Overton, M.L.: An efficient primal-dual interior-point method for minimizing a sum of Euclidean norms. SIAM J. Sci. Comput. 22, 243\u2013262 (1999)","journal-title":"SIAM J. Sci. Comput."},{"issue":"5","key":"1141_CR2","doi-asserted-by":"publisher","first-page":"1815","DOI":"10.1137\/080720991","volume":"40","author":"F Andreu","year":"2009","unstructured":"Andreu, F., Maz\u00f3n, J.M., Rossi, J.D., Toledo, J.: A nonlocal p-Laplacian evolution equation with nonhomogeneous Dirichlet boundary conditions. SIAM J. Math. Anal. 40(5), 1815\u20131851 (2009)","journal-title":"SIAM J. Math. Anal."},{"issue":"204","key":"1141_CR3","first-page":"523","volume":"61","author":"JW Barrett","year":"1993","unstructured":"Barrett, J.W., Liu, W.B.: Finite element approximation of the p-Laplacian. Math. Comput. 61(204), 523\u2013537 (1993)","journal-title":"Math. Comput."},{"issue":"5","key":"1141_CR4","doi-asserted-by":"publisher","first-page":"A2166","DOI":"10.1137\/120901064","volume":"36","author":"H Berninger","year":"2014","unstructured":"Berninger, H., Loisel, S., Sander, O.: The 2-Lagrange multiplier method applied to nonlinear transmission problems for the Richards equation in heterogeneous soil with cross points. SIAM J. Sci. Comput. 36(5), A2166\u2013A2198 (2014)","journal-title":"SIAM J. Sci. Comput."},{"key":"1141_CR5","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804441","volume-title":"Convex Optimization","author":"S Boyd","year":"2004","unstructured":"Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, New York (2004)"},{"issue":"1","key":"1141_CR6","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/BF02591853","volume":"38","author":"PH Calamai","year":"1987","unstructured":"Calamai, P.H., Conn, A.R.: A projected Newton method for $$l^p$$ norm location problems. Math. Program. 38(1), 75\u2013109 (1987). https:\/\/doi.org\/10.1007\/BF02591853","journal-title":"Math. Program."},{"issue":"2","key":"1141_CR7","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1109\/TIT.2005.862083","volume":"52","author":"EJ Cand\u00e8s","year":"2006","unstructured":"Cand\u00e8s, E.J., Romberg, J., Tao, T.: Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Trans. Inf. Theory 52(2), 489\u2013509 (2006)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"1","key":"1141_CR8","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1137\/0729012","volume":"29","author":"F Catt\u00e9","year":"1992","unstructured":"Catt\u00e9, F., Lions, P.-L., Morel, J.-M., Coll, T.: Image selective smoothing and edge detection by nonlinear diffusion. SIAM J. Numer. Anal. 29(1), 182\u2013193 (1992)","journal-title":"SIAM J. Numer. Anal."},{"issue":"4","key":"1141_CR9","doi-asserted-by":"publisher","first-page":"745","DOI":"10.1007\/s10255-012-0185-z","volume":"28","author":"R-L Chen","year":"2012","unstructured":"Chen, R.-L., Zeng, J.-P.: A new subspace correction method for nonlinear unconstrained convex optimization problems. Acta Mathematicae Applicatae Sinica 28(4), 745\u2013756 (2012). https:\/\/doi.org\/10.1007\/s10255-012-0185-z. (English Series)","journal-title":"Acta Mathematicae Applicatae Sinica"},{"key":"1141_CR10","doi-asserted-by":"crossref","unstructured":"C\u00f4t\u00e9, J., Gander, M.J., Laayouni, L., Loisel, S.: Comparison of the Dirichlet-Neumann and optimal Schwarz method on the sphere. In: Domain Decomposition Methods in Science and Engineering, pp. 235\u2013242. Springer, New York (2005)","DOI":"10.1007\/3-540-26825-1_21"},{"issue":"1","key":"1141_CR11","first-page":"85","volume":"76","author":"P Dr\u00e1bek","year":"2007","unstructured":"Dr\u00e1bek, P.: The $$p$$-Laplacian-mascot of nonlinear analysis. Acta Mathematica Universitatis Comenianae 76(1), 85\u201398 (2007)","journal-title":"Acta Mathematica Universitatis Comenianae"},{"key":"1141_CR12","doi-asserted-by":"crossref","unstructured":"Drury, S.W., Loisel, S.: Sharp condition number estimates for the symmetric 2-Lagrange multiplier method. In: Domain Decomposition Methods in Science and Engineering, pp. 255\u2013261. Springer, New York(2013)","DOI":"10.1007\/978-3-642-35275-1_29"},{"key":"1141_CR13","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611971088","volume-title":"Convex Analysis and Variational Problems","author":"I Ekeland","year":"1999","unstructured":"Ekeland, I., T\u00e9mam, R.: Convex Analysis and Variational Problems. SIAM, Philadelphia (1999)"},{"issue":"2","key":"1141_CR14","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1137\/100796194","volume":"33","author":"MJ Gander","year":"2012","unstructured":"Gander, M.J., Loisel, S., Szyld, D.B.: An optimal block iterative method and preconditioner for banded matrices with applications to pdes on irregular domains. SIAM J. Matrix Anal. Appl. 33(2), 653\u2013680 (2012)","journal-title":"SIAM J. Matrix Anal. Appl."},{"issue":"4","key":"1141_CR15","doi-asserted-by":"publisher","first-page":"737","DOI":"10.1007\/s11075-014-9923-z","volume":"69","author":"N Greer","year":"2015","unstructured":"Greer, N., Loisel, S.: The optimised Schwarz method and the two-Lagrange multiplier method for heterogeneous problems in general domains with two general subdomains. Numer. Algorithms 69(4), 737\u2013762 (2015)","journal-title":"Numer. Algorithms"},{"key":"1141_CR16","volume-title":"Nonlinear Potential Theory of Degenerate Elliptic Equations","author":"J Heinonen","year":"2006","unstructured":"Heinonen, J., Kilperl\u00e4inen, T., Martio, O.: Nonlinear Potential Theory of Degenerate Elliptic Equations. Dover Publications, Mineola (2006)"},{"issue":"1\u20133","key":"1141_CR17","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/BF01585553","volume":"69","author":"D Hertog","year":"1995","unstructured":"Hertog, D., Jarre, F., Roos, C., Terlaky, T.: A sufficient condition for self-concordance, with application to some classes of structured convex programming problems. Math. Program. 69(1\u20133), 75\u201388 (1995). https:\/\/doi.org\/10.1007\/BF01585553","journal-title":"Math. Program."},{"issue":"2","key":"1141_CR18","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1007\/s10915-007-9134-z","volume":"32","author":"YQ Huang","year":"2007","unstructured":"Huang, Y.Q., Li, R., Liu, W.: Preconditioned descent algorithms for p-Laplacian. J. Sci. Comput. 32(2), 343\u2013371 (2007). https:\/\/doi.org\/10.1007\/s10915-007-9134-z","journal-title":"J. Sci. Comput."},{"issue":"3","key":"1141_CR19","doi-asserted-by":"publisher","first-page":"344","DOI":"10.1002\/cpa.20101","volume":"59","author":"R Kohn","year":"2006","unstructured":"Kohn, R., Serfaty, S.: A deterministic-control-based approach motion by curvature. Commun. Pure Appl. Math. 59(3), 344\u2013407 (2006). https:\/\/doi.org\/10.1002\/cpa.20101","journal-title":"Commun. Pure Appl. Math."},{"key":"1141_CR20","doi-asserted-by":"crossref","unstructured":"Le\u00a0Gall, F.: Powers of tensors and fast matrix multiplication. In: Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, pp. 296\u2013303. ACM, New York (2014)","DOI":"10.1145\/2608628.2608664"},{"key":"1141_CR21","volume-title":"Notes on the p-Laplace Equation","author":"P Lindqvist","year":"2017","unstructured":"Lindqvist, P.: Notes on the p-Laplace Equation. University of Jyv\u00e4skyl\u00e4, Finland (2017)"},{"key":"1141_CR22","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1016\/j.cam.2017.02.018","volume":"321","author":"S Loisel","year":"2017","unstructured":"Loisel, S., Nguyen, H.: An optimal Schwarz preconditioner for a class of parallel adaptive finite elements. J. Comput. Appl. Math. 321, 90\u2013107 (2017)","journal-title":"J. Comput. Appl. Math."},{"key":"1141_CR23","doi-asserted-by":"crossref","unstructured":"Loisel, S., Szyld, D.B.: On the convergence of optimized Schwarz methods by way of matrix analysis. In: Domain Decomposition Methods in Science and Engineering, vol. XVIII, pp. 363\u2013370. Springer, New York (2009a)","DOI":"10.1007\/978-3-642-02677-5_41"},{"key":"1141_CR24","doi-asserted-by":"crossref","unstructured":"Loisel, S., Szyld, D.B.: A maximum principle for $$l^2$$-trace norms with an application to optimized Schwarz methods. In: Domain Decomposition Methods in Science and Engineering, vol. XVIII, pp. 193\u2013200. Springer, New York (2009b)","DOI":"10.1007\/978-3-642-02677-5_20"},{"issue":"2","key":"1141_CR25","doi-asserted-by":"publisher","first-page":"524","DOI":"10.1137\/080727014","volume":"48","author":"S Loisel","year":"2010","unstructured":"Loisel, S., C\u00f4t\u00e9, J., Gander, M.J., Laayouni, L., Qaddouri, A.: Optimized domain decomposition methods for the spherical Laplacian. SIAM J. Numer. Anal. 48(2), 524\u2013551 (2010)","journal-title":"SIAM J. Numer. Anal."},{"issue":"6","key":"1141_CR26","doi-asserted-by":"publisher","first-page":"A2896","DOI":"10.1137\/15M1009676","volume":"37","author":"S Loisel","year":"2015","unstructured":"Loisel, S., Nguyen, H., Scheichl, R.: Optimized Schwarz and 2-Lagrange multiplier methods for multiscale elliptic PDEs. SIAM J. Sci. Comput. 37(6), A2896\u2013A2923 (2015)","journal-title":"SIAM J. Sci. Comput."},{"key":"1141_CR27","volume-title":"Introductory Lectures on Convex Optimization: A Basic Course","author":"Y Nesterov","year":"2013","unstructured":"Nesterov, Y.: Introductory Lectures on Convex Optimization: A Basic Course, vol. 87. Springer, New York (2013)"},{"key":"1141_CR28","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970791","author":"Y Nesterov","year":"1994","unstructured":"Nesterov, Y., Nemirovskii, A.: Interior-point polynomial algorithms in convex programming. Soc. Ind. Appl. Math. (1994). https:\/\/doi.org\/10.1137\/1.9781611970791","journal-title":"Soc. Ind. Appl. Math."},{"issue":"4","key":"1141_CR29","doi-asserted-by":"publisher","first-page":"1674","DOI":"10.1137\/060649513","volume":"19","author":"J Nocedal","year":"2009","unstructured":"Nocedal, J., W\u00e4chter, A., Waltz, R.A.: Adaptive barrier update strategies for nonlinear interior methods. SIAM J. Optim. 19(4), 1674\u20131693 (2009)","journal-title":"SIAM J. Optim."},{"key":"1141_CR30","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/j.cam.2012.11.023","volume":"254","author":"AM Oberman","year":"2013","unstructured":"Oberman, A.M.: Finite difference methods for the infinity Laplace and p-Laplace equations. J. Comput. Appl. Math. 254, 65\u201380 (2013)","journal-title":"J. Comput. Appl. Math."},{"issue":"1","key":"1141_CR31","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1080\/10586458.1993.10504266","volume":"2","author":"U Pinkall","year":"1993","unstructured":"Pinkall, U., Polthier, K.: Computing discrete minimal surfaces and their conjugates. Exp. Math. 2(1), 15\u201336 (1993). https:\/\/doi.org\/10.1080\/10586458.1993.10504266","journal-title":"Exp. Math."},{"key":"1141_CR32","volume-title":"Numerical Approximation of Partial Differential Equations","author":"A Quarteroni","year":"2008","unstructured":"Quarteroni, A., Valli, A.: Numerical Approximation of Partial Differential Equations, vol. 23. Springer, New York (2008)"},{"key":"1141_CR33","volume-title":"Variational Methods in Mathematics, Science and Engineering","author":"K Rektorys","year":"2012","unstructured":"Rektorys, K.: Variational Methods in Mathematics, Science and Engineering. Springer, New York (2012)"},{"issue":"190","key":"1141_CR34","doi-asserted-by":"publisher","first-page":"483","DOI":"10.1090\/S0025-5718-1990-1011446-7","volume":"54","author":"L Ridgway Scott","year":"1990","unstructured":"Ridgway Scott, L., Zhang, S.: Finite element interpolation of nonsmooth functions satisfying boundary conditions. Math. Comput. 54(190), 483\u2013493 (1990)","journal-title":"Math. Comput."},{"key":"1141_CR35","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1016\/j.cma.2013.12.016","volume":"272","author":"W Subber","year":"2014","unstructured":"Subber, W., Loisel, S.: Schwarz preconditioners for stochastic elliptic PDES. Comput. Methods Appl. Mech. Eng. 272, 34\u201357 (2014)","journal-title":"Comput. Methods Appl. Mech. Eng."},{"key":"1141_CR36","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1090\/S0025-5718-01-01311-4","volume":"71","author":"X-C Tai","year":"2001","unstructured":"Tai, X.-C., Jinchao, X.: Global and uniform convergence of subspace correction methods for some convex optimization problems. Math. Comput. 71, 105\u2013124 (2001)","journal-title":"Math. Comput."},{"key":"1141_CR37","volume-title":"Domain Decomposition Methods-Algorithms and Theory","author":"A Toselli","year":"2006","unstructured":"Toselli, A., Widlund, O.: Domain Decomposition Methods-Algorithms and Theory, vol. 34. Springer, New York (2006)"},{"key":"1141_CR38","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1137\/S1052623497327088","volume":"10","author":"G Xue","year":"1997","unstructured":"Xue, G., Ye, Y.: An efficient algorithm for minimizing a sum of p-norms. SIAM J. Optim. 10, 551\u2013579 (1997)","journal-title":"SIAM J. Optim."}],"container-title":["Numerische Mathematik"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00211-020-01141-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00211-020-01141-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00211-020-01141-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,23]],"date-time":"2021-08-23T23:29:48Z","timestamp":1629761388000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00211-020-01141-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,24]]},"references-count":38,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,10]]}},"alternative-id":["1141"],"URL":"https:\/\/doi.org\/10.1007\/s00211-020-01141-z","relation":{},"ISSN":["0029-599X","0945-3245"],"issn-type":[{"value":"0029-599X","type":"print"},{"value":"0945-3245","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,8,24]]},"assertion":[{"value":"15 August 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 March 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 August 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}