Speaker
Description
A matrix algorithm is said to be superfast (aka runs at sublinear cost) if it involves much fewer scalars and flops than an input matrix has entries. Such algorithms have been extensively studied and widely applied in modern computations for matrices with low displacement rank and more recently for low rank approximation of matrices, even though any superfast algorithm fails on worst case inputs for the latter problem. We extend this study to a new area by proposing three distinct superfast 1-norm estimators. In our extensive tests with synthetic and real word matrices all three have output 1-norm within relative error 1.5, while the outputs of two of them were consistently as accurate as LAPACK's. We point out some promising extensions of our surprisingly simple techniques. With further testing and refinement our algorithms should eventually win user's attention.