The bit-cost of some algorithms for the solution of linear systems
type: Item
instance of: scholarly article
title: The bit-cost of some algorithms for the solution of linear systems
zbMATH Open document ID: 0654.65027
DOI: 10.1016/0898-1221(88)90036-3
author: Bruno Codenotti
publication date: 1988-01-01T00:00:00Z
review text: 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.
reviewed by: D. Kershaw
Mathematics Subject Classification ID: 65F05
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 65F10
Mathematics Subject Classification ID: 65H10
zbMATH DE Number: 4068163
zbMATH Keywords: computational cost
zbMATH Keywords: parallel processors
zbMATH Keywords: Jacobi iteration
zbMATH Keywords: Bit Sequential Cost
zbMATH Keywords: Bit Parallel Costs
zbMATH Keywords: Gaussian elimination
zbMATH Keywords: Newton iteration
zbMATH Keywords: triangular Toeplitz linear system
MaRDI profile type: Publication
full work available at URL: 0898-1221(88)90036-3
OpenAlex ID: W1969720527
cites work: Fast multiplication of large numbers
cites work: Complexity measures for matrix multiplication algorithms
cites work: The bit-complexity of arithmetic algorithms
cites work: Fast Multiple-Precision Evaluation of Elementary Functions
cites work: Q4871634
cites work: Round-off error analysis of iterations for large linear systems
cites work: Error analysis of an APA algorithm for the parallel solution of some special Toeplitz linear systems
published in: Computers & Mathematics with Applications
description: scientific article; zbMATH DE number 4068163