Error analysis of some approximating algorithms

The class of arbitrary precision approximating algorithms (APA in the following), which compute the result with an arbitrarily small error and with a number of operations smaller than the number of operations of any exact algorithm, is analysed in order to describe its numerical behaviour and to give efficient implementation strategies. the accuracy of the result can be improved either by using multiple precision arithmetic or interpolation strategies. In this paper, APA algorithms for matrix-vector product, matrix multiplication and triangular Toeplitz matrix inversion are considered.