Fast and Stable Pascal Matrix Algorithms

MaRDI QIDQ6511830arXivFDO

Authors S. Potter, R. Duraiswami

Published in arXiv

Abstract: In this paper, we derive a family of fast and stable algorithms for multiplying and inverting $nimesn$ Pascal matrices that run in $O(nlo{g}^{2}n)$ time and are closely related to De Casteljau's algorithm for B'ezier curve evaluation. These algorithms use a recursive factorization of the triangular Pascal matrices and improve upon the cripplingly unstable $O(nlogn)$ 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'ezier curve evaluation.

This page was built for publication: Fast and Stable Pascal Matrix Algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6511830)