Combining algebraic and numerical methods in algorithm design.
Item
-
Title
-
Combining algebraic and numerical methods in algorithm design.
-
Identifier
-
AAI9830781
-
identifier
-
9830781
-
Creator
-
Yu, Yanqiang.
-
Contributor
-
Adviser: Victor Y. Pan
-
Date
-
1998
-
Language
-
English
-
Publisher
-
City University of New York.
-
Subject
-
Computer Science | Mathematics
-
Abstract
-
The dissertation summarizes our studies in developing fast and efficient algorithms by combining the techniques of numerical methods and algebraic methods. The effectiveness of our approach is proven by its applications to several common computational problems. In the case of multipoint polynomial evaluation and polynomial interpolation, by converting the problem into dense structured matrix computation, we have developed efficient approximation algorithm with numerical stability improved over existing algebraic algorithms. We also demonstrate the techniques of binary modular reduction and backward binary segmentation which bring the traditional algebraic method of modular arithmetic into numerical computation algorithms. The techniques are proven to improve significantly the overall efficiency of inner product computation and of the iterative improvement algorithm for matrix inversion. For the evaluation of sign of matrix determinant, we again combine numerical methods with algebraic methods to obtain the solution by using lower precision computations and fewer arithmetic operations. Some of numerical experiment results are included.
-
Type
-
dissertation
-
Source
-
PQT Legacy CUNY.xlsx
-
degree
-
Ph.D.
