An algorithm to solve Hilbert systems of linear equations precisely

DOI10.1016/0096-3003(95)00061-5MaRDI QIDQ1908247zbMATH OpenOpenAlexFDO

Authors Miroslav Morháč

Publication date 5 August 1996

Published in Applied Mathematics and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0096-3003(95)00061-5

zbMATH Keywords

Hilbert matrixill-conditioningLevinson algorithmmodular arithmeticparallel computationToeplitz system

Mathematics Subject Classification ID

Direct numerical methods for linear systems and matrix inversion (65F05) Parallel numerical computation (65Y05)

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.

Recommendations

• An interval algorithm for solving systems of linear equations to prespecified accuracy
• scientific article; zbMATH DE number 238294
• A stable fast algorithm for solving linear systems of the Pascal type
• An error-free algorithm to solve a linear system of polynomial equations
• An algorithm to solve integer linear systems exactly using numerical methods

Cites work

• An error-free Levison algorithm to solve integer Toeplitz system
• scientific article; zbMATH DE number 3928865 (Why is no real title available?)
• scientific article; zbMATH DE number 3942890 (Why is no real title available?)
• scientific article; zbMATH DE number 3967873 (Why is no real title available?)
• scientific article; zbMATH DE number 3248502 (Why is no real title available?)
• Solving equations exactly

Cited in

(8)

• Hermite's method of separation of solutions of systems of algebraic equations and its applications
• Exact algorithm of multidimensional circulant deconvolution
• scientific article; zbMATH DE number 64181 (Why is no real title available?)
• scientific article; zbMATH DE number 4123147 (Why is no real title available?)
• scientific article; zbMATH DE number 1163446 (Why is no real title available?)
• An iterative error-free algorithm to solve Vandermonde systems
• On the vector \(\varepsilon\)-algorithm for solving linear systems of equations
• Error-free algorithms to solve special and general discrete systems of linear equations

This page was built for publication: An algorithm to solve Hilbert systems of linear equations precisely

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1908247)