Accurate Arithmetic Methods with Matrix Applications in Real Floating-Point Arithmetic
Open Access
Author:
Murarik, Nathan
Area of Honors:
Mathematics
Degree:
Bachelor of Science
Document Type:
Thesis
Thesis Supervisors:
Thomas Robert Cameron, Thesis Supervisor Daniel Joseph Galiffa, Thesis Honors Advisor Derek William Hanely, Faculty Reader
Keywords:
Accurate Arithmetic K-Fold Accuracy Error Analysis Perturbation Theory Numerical Analysis
Abstract:
Compensated arithmetic is a summation technique designed to filter the error generated by a floating-point computation. The filtered error is then used to accurately estimate the computation's exact value. In this thesis, we use compensated arithmetic to construct accurate addition, multiplication, and division algorithms in real floating-point arithmetic. We demonstrate their accuracy by proving each algorithm's output is as accurate as if computed in k-fold precision and stored in k-parts. Moreover, we use the derived forward-error bounds to perform backward error-analysis on the dot product and on backward-substitution for upper-triangular systems. We further explore matrix applications by augmenting Gaussian Elimination with Partial Pivoting and iterative refinement with our k-parts arithmetic algorithms. We supplement our theoretical error bounds with numerical experiments on both ill-conditioned dot products and ill-conditioned linear systems.
