Fast algorithms using orthogonal polynomials
File(s)
Accepted version
Author(s)
Olver, Sheehan
Slevinsky, Richard Mikaël
Townsend, Alex
Type
Journal Article
Abstract
We review recent advances in algorithms for quadrature, transforms, differential equations and singular integral equations using orthogonal polynomials. Quadrature based on asymptotics has facilitated optimal complexity quadrature rules, allowing for efficient computation of quadrature rules with millions of nodes. Transforms based on rank structures in change-of-basis operators allow for quasi-optimal complexity, including in multivariate settings such as on triangles and for spherical harmonics. Ordinary and partial differential equations can be solved via sparse linear algebra when set up using orthogonal polynomials as a basis, provided that care is taken with the weights of orthogonality. A similar idea, together with low-rank approximation, gives an efficient method for solving singular integral equations. These techniques can be combined to produce high-performance codes for a wide range of problems that appear in applications.
Date Issued
2020-05-01
Date Acceptance
2020-05-01
Citation
Acta Numerica, 2020, 29, pp.573-699
ISSN
0962-4929
Publisher
Cambridge University Press (CUP)
Start Page
573
End Page
699
Journal / Book Title
Acta Numerica
Volume
29
Copyright Statement
© The Author(s), 2020. Published by Cambridge University Press. This paper has been accepted for publication and will appear in a revised form, subsequent to peer-review and/or editorial input by Cambridge University Press.
Sponsor
The Leverhulme Trust
Identifier
https://www.cambridge.org/core/journals/acta-numerica/article/fast-algorithms-using-orthogonal-polynomials/4FAD8C7C28EC20EE7583465C1A89AA3D
Grant Number
RPG-2019-144
Subjects
0102 Applied Mathematics
0103 Numerical and Computational Mathematics
Numerical & Computational Mathematics
Publication Status
Published
Date Publish Online
2020-11-30