The role of arithmetic in fast parallel matrix inversion

In the last two decades several NC algorithms for solving basic linear alge braic problems have appeared in the literature. This interest was clearly m otivated by the emergence of a parallel computing technology and by the wid e applicability of matrix computations. The traditionally adopted computati on model, however, ignores the arithmetic aspects of the applications, and no analysis is currently available demonstrating the concrete feasibility o f many of the known fast methods. In this paper we give strong evidence to the contrary, on the sole basis of the issue of robustness, indicating that some theoretically brilliant solutions fail the severe test of the "Engine ering of Algorithms." We perform a comparative analysis of several well-kno wn numerical matrix inversion algorithms under both fixed- and variable-pre cision models of arithmetic. We show that, for most methods investigated, a typical input leads to poor numerical performance, and that in the exact-a rithmetic setting no benefit derives from conditions usually deemed favorab le in standard scientific computing. Under these circumstances, the only al gorithm admitting sufficiently accurate NC implementations is Newton's iter ative method, and the word size required to guarantee worst-case correctnes s appears to be the critical complexity measure. Our analysis also accounts for the observed instability of the considered superfast methods when impl emented with the same floating-point arithmetic that is perfectly adequate for the fixed-precision approach.