4 papers · 1 filter
New practical advances in polynomial root clustering
Rémi Imbach, Victor Y. Pan
We report an ongoing work on clustering algorithms for complex roots of a univariate polynomial of degree with real or complex coefficients. As in their previous best subdi…
CUR Low Rank Approximation at Deterministic Sublinear Cost
Qi Luan, Victor Y. Pan, John Svadlenka
A matrix algorithm runs at {\em sublinear cost} if it uses much fewer memory cells and arithmetic operations than the input matrix has entries. Such algorithms are indispensable fo…
Polynomial root clustering and explicit deflation
Rémi Imbach, Victor Y. Pan
We seek complex roots of a univariate polynomial with real or complex coefficients. We address this problem based on recent algorithms that use subdivision and have a nearly op…
Superfast Approximate Linear Least Squares Solution of a Highly Overdetermined Linear System of Equations
Qi Luan, Victor Y. Pan
With a high probability the Sarlos randomized algorithm of 2006 outputs a nearly optimal least squares solution of a highly overdeterminedlinear system of equations. We propose its…