The bit-cost of some algorithms for the solution of linear systems (Q1108740)

The aim of the paper is to compare the costs of algorithms run in sequential or parallel modes. For a particular algorithm `of size n' the author defines two costs, the Bit Sequential Cost and the Bit Parallel Costs: \(BSC(n)=O[ASC(n),A(f(n,t))]\) and \(BPC(n)=O[APC(n),A'(f(n,t))]\) where ASC is the arithmetic sequential cost and APC the arithmetic parallel cost. The functions A and A' are upper bounds on the respective costs of performing arithmetic operations on K digits, and \(f(n,t)\) is the number of digits to be used when performing any arithmetic operation on K digits. Upper bounds are found for these costs for Gaussian elimination, Jacobi and Newton iteration. The paper concludes with a brief analysis of the solution of a triangular Toeplitz linear system.