Digital Repository at the University of Maryland (University of Maryland College Park) · 2004 · 12 citations · 10 references
Open access
ComputingComputer ScienceAlgorithmsParallel AlgorithmsTheory Of ComputationAlgorithm AnalysisAlgorithmic ComplexityComputational ComplexityMatrix ComputationNumerical Linear AlgebraComplexityComputational Matrix TheoryMatrix MultiplicationSparse Matrix ComputationStructured Matrix Computation
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,
10
An algorithm for the machine calculation of complex Fourier series
J.W. Cooley, John W. Tukey · Mathematics of Computation · 1965 · 12.2K citations