Arbitrary Precision Approximating Algorithms
摘要
In this chapter we introduce the reader to the notion of arbitrary precision algorithms. In short, they allow to obtain an approximate value of a matrix product, but in return in fewer products. For the sake of clarity, we have not chosen the problems in the chronological order in which the papers were published. We show how to construct an exact algorithm from a given algorithm of arbitrary precision, and we prove what complexity it has. We then show how to transform the double disjoint matrix multiplication algorithm presented earlier into the corresponding approximate version, saving some non-scalar multiplications in return. Finally, we present in detail two classical approximate algorithms from 1981: the (relatively) simple double disjoint algorithm, and a more sophisticated one that computes three matrix products at once.