The bit-cost of some algorithms for the solution of linear systems (Q1108740)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The bit-cost of some algorithms for the solution of linear systems |
scientific article |
Statements
The bit-cost of some algorithms for the solution of linear systems (English)
0 references
1988
0 references
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.
0 references
computational cost
0 references
parallel processors
0 references
Jacobi iteration
0 references
Bit Sequential Cost
0 references
Bit Parallel Costs
0 references
Gaussian elimination
0 references
Newton iteration
0 references
triangular Toeplitz linear system
0 references