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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Arbitrary Precision Approximating Algorithms

  • Jerzy S. Respondek

摘要

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.