FAST ALGORITHMS TO COMPUTE MATRIX-VECTOR PRODUCTS FOR PASCAL MATRICES
Zhihui Tang, Ramani Duraiswami, Nail A. Gumerov · 2004
Abstract. The Pascal matrix arises in a number of applications. We present a few ways to decompose the Pascal matrices of size n×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 complexity 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. Key words. Matrix-vector product, Pascal matrices, matrix decomposition, structured matrices,