FAST ALGORITHMS TO COMPUTE MATRIX-VECTOR PRODUCTS FOR PASCAL MATRICES

The Pascal matrix arises in a number of applications. We present a few waysto 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