FAST ALGORITHMS TO COMPUTE MATRIX-VECTOR PRODUCTS FOR PASCAL MATRICES

Loading...
Thumbnail Image

Files

CS-TR-4563.pdf (258.53 KB)
No. of downloads: 934

Publication or External Link

Date

2004-03-25

Advisor

Citation

DRUM DOI

Abstract

The Pascal matrix arises in a number of applications. We present a few ways to decompose the Pascal matrices of size $n \times n$ into products of matrices with structure. Based on these decompositions, we propose fast algorithms to compute the product of a Pascal matrix and a vector with omplexity $O(n\log n)$. We also present a strategy to stabilize the proposed algorithms. Finally, we also present some interesting properties of the Pascal matrices that help us to compute fast the product of the inverse of a Pascal matrix and a vector, and fast algorithms for generalized Pascal Matrices. UMIACS-TR-2004-08

Notes

Rights