Back to Search
Start Over
Digit Stability Inference for Iterative Methods Using Redundant Number Representation
- Source :
- Li, H, Mcinerney, I, Davis, J J & Constantinides, G A 2021, ' Digit Stability Inference for Iterative Methods Using Redundant Number Representation ', IEEE Transactions on Computers, vol. 70, no. 7, pp. 1074-1080 . https://doi.org/10.1109/TC.2020.3003529
- Publication Year :
- 2021
- Publisher :
- Institute of Electrical and Electronics Engineers (IEEE), 2021.
-
Abstract
- In our recent work on iterative computation in hardware, we showed that arbitrary-precision solvers can perform more favourably than their traditional arithmetic equivalents when the latter’s precisions are either under- or over-budgeted for the solution of the problem at hand. Significant proportions of these performance improvements stem from the ability to infer the existence of identical most-significant digits between iterations. This technique uses properties of algorithms operating on redundantly represented numbers to allow the generation of those digits to be skipped, increasing efficiency. It is unable, however, to guarantee that digits will stabilise, i.e. never change in any future iteration. In this article, we address this shortcoming, using interval and forward error analyses to prove that digits of high significance will become stable when computing the approximants of systems of linear equations using stationary iterative methods. We formalise the relationship between matrix conditioning and the rate of growth in most-significant digit stability, using this information to converge to our desired results more quickly. Versus our previous work, an exemplary hardware implementation of this new technique achieves an up-to 2.2x speedup in the solution of a set of variously conditioned systems using the Jacobi method.
- Subjects :
- math.NA
Speedup
Computer Hardware & Architecture
Iterative method
Computer science
Computation
Stability (learning theory)
Jacobi method
0805 Distributed Computing
02 engineering and technology
Interval (mathematics)
System of linear equations
Theoretical Computer Science
symbols.namesake
Redundancy (information theory)
FOS: Mathematics
0202 electrical engineering, electronic engineering, information engineering
Mathematics - Numerical Analysis
cs.NA
1006 Computer Hardware
0803 Computer Software
Numerical Analysis (math.NA)
020202 computer hardware & architecture
Computational Theory and Mathematics
Hardware and Architecture
symbols
Realization (systems)
Algorithm
Software
Subjects
Details
- ISSN :
- 23263814 and 00189340
- Volume :
- 70
- Database :
- OpenAIRE
- Journal :
- IEEE Transactions on Computers
- Accession number :
- edsair.doi.dedup.....bf007948594b9ff8556b39fbe7bd94ce