Fast and Stable Pascal Matrix Algorithms
This work provides a practical solution for matrix operations in computer graphics and numerical analysis, where Pascal matrices arise in Bézier curve evaluation.
The authors developed fast and stable algorithms for multiplying and inverting Pascal matrices in O(n log^2 n) time, improving upon unstable O(n log n) FFT-based methods. Numerical experiments confirm the speed and stability of their approach.
In this paper, we derive a family of fast and stable algorithms for multiplying and inverting $n \times n$ Pascal matrices that run in $O(n log^2 n)$ time and are closely related to De Casteljau's algorithm for Bézier curve evaluation. These algorithms use a recursive factorization of the triangular Pascal matrices and improve upon the cripplingly unstable $O(n log n)$ fast Fourier transform-based algorithms which involve a Toeplitz matrix factorization. We conduct numerical experiments which establish the speed and stability of our algorithm, as well as the poor performance of the Toeplitz factorization algorithm. As an example, we show how our formulation relates to Bézier curve evaluation.