An algorithm to solve Hilbert systems of linear equations precisely
type: Item
instance of: scholarly article
title: An algorithm to solve Hilbert systems of linear equations precisely
zbMATH Open document ID: 0842.65016
DOI: 10.1016/0096-3003(95)00061-5
published in: Applied Mathematics and Computation
publication date: 1996-08-05T00:00:00Z
review text: To solve the linear system \(Hx= y\), where \(H= [(i+ j- 1)^{- 1}]\) is a Hilbert matrix, the column order is reversed which turns it into a Toeplitz system. The Toeplitz system can be solved with the Levinson algorithm. If the right-hand side consists of rational numbers, all the computations can be done in integer arithmetic avoiding floating point rounding errors. However, because these integers grow rapidly, due to the ill-conditioning, the calculations should be done in modular arithmetic. This results in \(O(n^2)\) modular operations per modulo class which can be performed in parallel. There is a nonzero possibility that the algorithm fails if a division by a number in residue class zero occurs. Then the calculations are to be repeated with another prime modulus.
reviewed by: Adhemar Bultheel
Mathematics Subject Classification ID: 65F05
Mathematics Subject Classification ID: 65Y05
zbMATH DE Number: 847556
zbMATH Keywords: parallel computation
zbMATH Keywords: Hilbert matrix
zbMATH Keywords: Toeplitz system
zbMATH Keywords: Levinson algorithm
zbMATH Keywords: ill-conditioning
zbMATH Keywords: modular arithmetic
author: Miroslav Morháč
MaRDI profile type: Publication
full work available at URL: 0096-3003(95)00061-5
OpenAlex ID: W2008493418
cites work: Solving equations exactly
cites work: Q3713483
cites work: Q5535370
cites work: Q3703780
cites work: An error-free Levison algorithm to solve integer Toeplitz system
cites work: Q3735040
description: scientific article; zbMATH DE number 847556