{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:24:10Z","timestamp":1740108250420,"version":"3.37.3"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2021,4,30]],"date-time":"2021-04-30T00:00:00Z","timestamp":1619740800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,4,30]],"date-time":"2021-04-30T00:00:00Z","timestamp":1619740800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Comput Stat"],"published-print":{"date-parts":[[2021,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Penalized spline smoothing is a well-established, nonparametric regression method that is efficient for one and two covariates. Its extension to more than two covariates is straightforward but suffers from exponentially increasing memory demands and computational complexity, which brings the method to its numerical limit. Penalized spline smoothing with multiple covariates requires solving a large-scale, regularized least-squares problem where the occurring matrices do not fit into storage of common computer systems. To overcome this restriction, we introduce a matrix-free implementation of the conjugate gradient method. We further present a matrix-free implementation of a simple diagonal as well as more advanced geometric multigrid preconditioner to significantly speed up convergence of the conjugate gradient method. All algorithms require a negligible amount of memory and therefore allow for penalized spline smoothing with multiple covariates. Moreover, for arbitrary but fixed covariate dimension, we show grid independent convergence of the multigrid preconditioner which is fundamental to achieve algorithmic scalability.<\/jats:p>","DOI":"10.1007\/s00180-021-01104-4","type":"journal-article","created":{"date-parts":[[2021,4,30]],"date-time":"2021-04-30T03:50:46Z","timestamp":1619754646000},"page":"2379-2411","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["A multigrid preconditioner for tensor product spline smoothing"],"prefix":"10.1007","volume":"36","author":[{"given":"Martin","family":"Siebenborn","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6786-6480","authenticated-orcid":false,"given":"Julian","family":"Wagner","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,4,30]]},"reference":[{"issue":"2","key":"1104_CR1","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1145\/1944345.1944349","volume":"58","author":"H Avron","year":"2011","unstructured":"Avron H, Toledo S (2011) Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix. J ACM 58(2):8","journal-title":"J ACM"},{"key":"1104_CR2","volume-title":"Dynamic programming","author":"R Bellman","year":"1957","unstructured":"Bellman R (1957) Dynamic programming. Princeton University Press, Princeton"},{"key":"1104_CR3","unstructured":"Benoit A, Plateau B, Stewart WJ (2001) Memory efficient iterative methods for stochastic automata networks. Technical Report 4259, INRIA"},{"key":"1104_CR4","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rck A (1996) Numerical methods for least squares problems. SIAM","DOI":"10.1137\/1.9781611971484"},{"issue":"138","key":"1104_CR5","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1090\/S0025-5718-1977-0431719-X","volume":"31","author":"A Brandt","year":"1977","unstructured":"Brandt A (1977) Multi-level adaptive solutions to boundary-value problems. Math Comput 31(138):333\u2013390","journal-title":"Math Comput"},{"key":"1104_CR6","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1017\/S0962492904000182","volume":"13","author":"H-J Bungartz","year":"2004","unstructured":"Bungartz H-J, Griebel M (2004) Sparse grids. Acta Numer 13:147\u2013269","journal-title":"Acta Numer"},{"issue":"2","key":"1104_CR7","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1111\/j.1467-9868.2006.00543.x","volume":"68","author":"ID Currie","year":"2006","unstructured":"Currie ID, Durban M, Eilers PH (2006) Generalized linear array models with applications to multidimensional smoothing. J R Stat Soc Ser B (Stat Methodol) 68(2):259\u2013280","journal-title":"J R Stat Soc Ser B (Stat Methodol)"},{"key":"1104_CR8","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-6333-3","volume-title":"A practical guide to splines","author":"C de Boor","year":"1978","unstructured":"de Boor C (1978) A practical guide to splines. Springer, Berlin"},{"key":"1104_CR9","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4614-6868-4","volume-title":"Seamless R and C++ integration with Rcpp","author":"D Eddelbuettel","year":"2013","unstructured":"Eddelbuettel D (2013) Seamless R and C++ integration with Rcpp. Springer, New York"},{"issue":"8","key":"1104_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.18637\/jss.v040.i08","volume":"40","author":"D Eddelbuettel","year":"2011","unstructured":"Eddelbuettel D, Fran\u00e7ois R (2011) Rcpp: seamless R and C++ integration. J Stat Softw 40(8):1\u201318","journal-title":"J Stat Softw"},{"issue":"1","key":"1104_CR11","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/j.csda.2004.07.008","volume":"50","author":"PH Eilers","year":"2006","unstructured":"Eilers PH, Currie ID, Durb\u00e1n M (2006) Fast and compact smoothing on large multidimensional grids. Comput Stat Data Anal 50(1):61\u201376","journal-title":"Comput Stat Data Anal"},{"key":"1104_CR12","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1214\/ss\/1038425655","volume":"11","author":"PH Eilers","year":"1996","unstructured":"Eilers PH, Marx BD (1996) Flexible smoothing with B-splines and penalties. Stat Sci 11:89\u2013121","journal-title":"Stat Sci"},{"key":"1104_CR13","unstructured":"Eubank RL (1988) Spline smoothing and nonparametric regression. Marcel Dekker Inc"},{"key":"1104_CR14","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-34333-9","volume-title":"Regression: models, methods and applications","author":"L Fahrmeir","year":"2013","unstructured":"Fahrmeir L, Kneib T, Lang S, Marx B (2013) Regression: models, methods and applications. Springer, Berlin"},{"key":"1104_CR15","unstructured":"Fitzsimons J, Osborne M, Roberts S, Fitzsimons JF (2016) Improved stochastic trace estimation using mutually unbiased bases. arXiv:1608.00117"},{"key":"1104_CR16","doi-asserted-by":"crossref","unstructured":"Green PJ, Silverman BW (1993) Nonparametric regression and generalized linear models: a roughness penalty approach. Chapman & Hall","DOI":"10.1201\/b15710"},{"issue":"4","key":"1104_CR17","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1007\/BF02252378","volume":"20","author":"W Hackbusch","year":"1978","unstructured":"Hackbusch W (1978) On the multi-grid method applied to difference equations. Computing 20(4):291\u2013306","journal-title":"Computing"},{"key":"1104_CR18","doi-asserted-by":"crossref","unstructured":"Head K, Mayer T (2014) Gravity equations: workhorse, toolkit, and cookbook. In: Gravity equations: workhorse, toolkit, and cookbooks, vol\u00a04. Elsevier, pp 131\u2013195","DOI":"10.1016\/B978-0-444-54314-1.00003-3"},{"issue":"1","key":"1104_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jinteco.2010.01.002","volume":"81","author":"K Head","year":"2010","unstructured":"Head K, Mayer T, Ries J (2010) The erosion of colonial trade linkages after independence. J Int Econ 81(1):1\u201314","journal-title":"J Int Econ"},{"issue":"6","key":"1104_CR20","doi-asserted-by":"publisher","first-page":"406","DOI":"10.6028\/jres.049.044","volume":"49","author":"MR Hestenes","year":"1952","unstructured":"Hestenes MR, Stiefel E (1952) Methods of conjugate gradients for solving linear systems. J Res Natl Bur Stand 49(6):406\u2013436","journal-title":"J Res Natl Bur Stand"},{"key":"1104_CR21","doi-asserted-by":"crossref","unstructured":"H\u00f6llig K (2003) Finite element methods with B-splines. SIAM","DOI":"10.1137\/1.9780898717532"},{"issue":"4","key":"1104_CR22","first-page":"502","volume":"1","author":"F O\u2019Sullivan","year":"1986","unstructured":"O\u2019Sullivan F (1986) A statistical perspective on ill-posed inverse problems. Stat Sci 1(4):502\u2013527","journal-title":"Stat Sci"},{"key":"1104_CR23","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511755453","volume-title":"Semiparametric regression","author":"D Ruppert","year":"2003","unstructured":"Ruppert D, Wand MP, Carroll RJ (2003) Semiparametric regression. Cambridge University Press, Cambridge"},{"key":"1104_CR24","doi-asserted-by":"crossref","unstructured":"Saad Y (2003) Iterative methods for sparse linear systems, 2 ed. SIAM","DOI":"10.1137\/1.9780898718003"},{"key":"1104_CR25","doi-asserted-by":"crossref","unstructured":"Siebenborn M, Wagner J (2021) MGSS: a matrix-free multigrid preconditioner for spline smoothing. R package version 1","DOI":"10.1007\/s00180-021-01104-4"},{"key":"1104_CR26","unstructured":"Trottenberg U, Oosterlee CW, Schuller A (2000) Multigrid. Academic press"},{"key":"1104_CR27","unstructured":"Wagner J, Kauermann G, M\u00fcnnich R (2021) Matrix-free penalized spline smoothing with multiple covariates. arXiv:2101.06034"},{"key":"1104_CR28","doi-asserted-by":"crossref","unstructured":"Wahba G (1990) Spline models for observational data. SIAM","DOI":"10.1137\/1.9781611970128"},{"issue":"2","key":"1104_CR29","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1111\/j.1467-842X.2008.00507.x","volume":"50","author":"M Wand","year":"2008","unstructured":"Wand M, Ormerod J (2008) On semiparametric regression with O\u2019Sullivan penalized splines. Aust N Z J Stat 50(2):179\u2013198","journal-title":"Aust N Z J Stat"},{"issue":"4","key":"1104_CR30","doi-asserted-by":"publisher","first-page":"16","DOI":"10.17713\/ajs.v47i4.688","volume":"47","author":"A-L W\u00f6lwer","year":"2018","unstructured":"W\u00f6lwer A-L, Bre\u00dflein M, Burgard JP (2018) Gravity models in R. Austrian J Stat 47(4):16\u201335","journal-title":"Austrian J Stat"},{"key":"1104_CR31","unstructured":"Zenger C (1991) Sparse grids. Notes on numerical fluid mechanics, p 31"}],"container-title":["Computational Statistics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00180-021-01104-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00180-021-01104-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00180-021-01104-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,11,18]],"date-time":"2021-11-18T07:06:34Z","timestamp":1637219194000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00180-021-01104-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,30]]},"references-count":31,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,12]]}},"alternative-id":["1104"],"URL":"https:\/\/doi.org\/10.1007\/s00180-021-01104-4","relation":{},"ISSN":["0943-4062","1613-9658"],"issn-type":[{"type":"print","value":"0943-4062"},{"type":"electronic","value":"1613-9658"}],"subject":[],"published":{"date-parts":[[2021,4,30]]},"assertion":[{"value":"8 July 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 April 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 April 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}