ABSTRACT
Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307 10.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308
10.1.1 Predictive Models and Factors Affecting the Performance of Related Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308
10.1.2 Basic Concepts of Parallel Computing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311 10.1.3 Concepts from Numerical Linear Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315
10.2 Additive Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319 10.2.1 The Backfitting Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319 10.2.2 A Parallel Backfitting Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 321 10.2.3 Implementation — The Block and Merge Method. . . . . . . . . . . . . . . . . . . . . . . . 324
10.3 Thin Plate Splines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325 10.3.1 Fitting Radial Basis Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325 10.3.2 Parallel and Scalable Finite Element Approximation
of Thin Plate Splines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 326 10.3.3 A Parallel Nonconforming Finite Element Method . . . . . . . . . . . . . . . . . . . . . . . 327
10.4 Multivariate Adaptive Regression Splines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 330 10.4.1 The MARS Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 330 10.4.2 MARS with B-Splines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334
10.5 Sparse Grids . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 336 10.5.1 Sparse Grid Spaces and Penalized Least Squares . . . . . . . . . . . . . . . . . . . . . . . . . 336 10.5.2 The Combination Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 338 10.5.3 Implementation of the Combination Technique . . . . . . . . . . . . . . . . . . . . . . . . . . 340
10.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 341 Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342
Parallel computing enables the analysis of very large data sets using large collections of flexible models with many variables. The computational methods are based on ideas from computational linear algebra and can draw on extensive research in parallel algorithms. Many algorithms for the direct and iterative solution of penalized least squares problems and for updating can be applied. Both methods for dense and sparse problems are applicable. An important property of the algorithms is their scalability, i.e., their ability to solve larger problems in the same time using hardware which grows linearly with the problem size. Whereas in most cases large granularity parallelism is to be preferred, it turns out that smaller granularity parallelism can also be exploited effectively in the problems considered.
