On speed versus accuracy: Some case studies (Q2565199)

Following the author's words, usually the error bounds obtained for the fastest algorithms are much worse than the bounds known for the corresponding classical algorithms. As a counterargument, one can state that good accuracy can be obtained under a reasonable theoretical model of arithmetic. The paper explores the suitability of complexity theoretic tools to deal with accuracy issues. This is done for significant examples corresponding to three different settings: sequential complexity, parallel complexity and relative complexity of problems. For the sequential setting the (linear) problem of polynomial evaluation at many (fixed) points is studied; it is proved that the fastest known algorithms are not stable. The PLU decomposition of a real matrix is regarded in the parallel setting. The author establishes that certain constraints on the computed factors which imply good accuracy make the PLU decomposition hard to solve in parallel. Finally, an example of computation of a determinant using an oracle for the characteristic polynomial is considered. In this case, the same stability constraints discussed for the problem of polynomial evaluation are violated. The conclusion is that reductions among computational problems do not in general constitute a practical tool for solving numerical problems.