Efficient Cauchy -like computations.
Item
-
Title
-
Efficient Cauchy -like computations.
-
Identifier
-
AAI9959155
-
identifier
-
9959155
-
Creator
-
Abu Tabanjeh, Mohammad Mustafa.
-
Contributor
-
Adviser: Victor Pan
-
Date
-
2000
-
Language
-
English
-
Publisher
-
City University of New York.
-
Subject
-
Mathematics | Computer Science
-
Abstract
-
Computation with n x n dense structured matrices are highly important in sciences, communication and engineering. The space and time complexity of the computations decreases in comparison with the case of n x n general matrices, that is, from order of n2 words of storage space and order of ni arithmetic operations with 2.37 < i ≤ 3 in the best algorithms, to O(n) words of storage space and to O( n log2 n) (and sometimes to O(n log n)) arithmetic operations, with small overhead constants.;The most celebrated classes of structured matrices are Toeplitz and Hankel matrices, but some other classes of structured matrices such as Cauchy and Vandermonde are quite popular too.;We focused our study on Cauchy and Cauchy-like computations, in particular, we present a super-fast Cauchy-like linear solver for any nonsingular Cauchy-like linear system of equations. The algorithm also computes short displacement generator for the inverse and determinant of a nonsingular Cauchy and Cauchy-like matrix. The algorithm is an extension of the well known divide-and-conquer (MBA) algorithm, and its every recursive divide-and-conquer step can be reduced to Trummer's celebrated problem, for which we have some generalization of Fast Multipole Algorithm.;Finally, we extend our superfast algorithm to the solution of consistent but possibly singular Cauchy-like linear system over any field of constants.
-
Type
-
dissertation
-
Source
-
PQT Legacy CUNY.xlsx
-
degree
-
Ph.D.
