High precision numerical computation, the determinant case.
Item
-
Title
-
High precision numerical computation, the determinant case.
-
Identifier
-
AAI9908368
-
identifier
-
9908368
-
Creator
-
Stewart, Colin D.
-
Contributor
-
Adviser: Victor Pan
-
Date
-
1998
-
Language
-
English
-
Publisher
-
City University of New York.
-
Subject
-
Computer Science | Mathematics
-
Abstract
-
In recent years the problem of accurately determining the sign of a matrix determinant has attracted a great deal of attention. The difficulty in this problem lies with the characteristic presence of truncation or rounding errors in floating point machine arithmetic. Various approaches have been suggested for getting around this problem, notably focusing on alternative numerical algorithms or exact arithmetic methods. We take a fresh approach, really a mix of the previously proposed ideas, featuring a new algorithmic step called "certification of the sign of the determinant" whereby an initial computation may be done in fast floating point using a standard numerical algorithm. If the certification test succeeds, then the result is said to be certified and the sign of the result is guaranteed to be correct. If the test fails then, and only then, need the computation be done using exact, albeit slower, arithmetic. Since the signs tend to be ambiguous only in small regions of the application problem space, the certification method is likely to prove competitively efficient in these applications: In effect the certification method applies the costly power of exact arithmetic selectively.;This dissertation focuses on the key problem areas of the certification method: (1) Finding a reliable method for determining the accuracy of a floating point computation. The 'correct' result is never present, errors must be deduced from the residue of the computation itself. We find that a measure of the proximity of the input to a singular matrix is available in the residue of LU decomposition with full pivoting and that this measure is a reliable source of certification. (2) Finding a parameterizable exact arithmetic alternative. The effectiveness of the certification process would be at least compromised if the exact back-up computation could not use information obtained from the primary calculation. The author's Modulus Vector formulation of classical modular arithmetic, developed in this dissertation, is just such a flexible exact arithmetic alternative. (3) Effectively combining the two major subtasks, certification and modular recomputation, into a workable algorithm.;Much of the research reported in this dissertation, and its findings, are based on numerical experiments.
-
Type
-
dissertation
-
Source
-
PQT Legacy CUNY.xlsx
-
degree
-
Ph.D.
