Studies in algorithms for fast rectangular matrix multiplications and their applications.
Item
-
Title
-
Studies in algorithms for fast rectangular matrix multiplications and their applications.
-
Identifier
-
AAI9807944
-
identifier
-
9807944
-
Creator
-
Huang, Xiaohan.
-
Contributor
-
Adviser: Victor Y. Pan
-
Date
-
1997
-
Language
-
English
-
Publisher
-
City University of New York.
-
Subject
-
Mathematics
-
Abstract
-
The first part of the dissertation describes the studies and results in developing the algorithms for fast rectangular matrix multiplications. In this part, we present two algorithms for the problem {dollar}\langle n,n,n\sp2\rangle{dollar} of computing the product of an n x n matrix by an n x {dollar}n\sp2{dollar} matrix, supporting the asymptotic arithmetic complexity bounds {dollar}O(n\sp{lcub}\omega{rcub}){dollar} with the exponents 3.33984{dollar}\cdots{dollar} and 3.333953{dollar}\cdots,{dollar} respectively, which are better (less) than previously known record exponent 3.375477{dollar}\cdots{dollar} by 0.036 and 0.042 respectively. Then, we present fast algorithms for rectangular matrix multiplications for matrix pairs of arbitrary dimensions and deal with the algorithms as the functions of the dimensions. Finally, we have discussed the optimization of the algorithms for rectangular matrix multiplications. Under "majority" situations, our algorithms achieve better matrix exponents than the known ones.;The second part of the dissertation describes the applications of our results of the first part on two topics. In particular, we improve the processor efficiency of fast parallel evaluation of the determinant, the characteristic polynomial and the inversion of a given square matrix, that is, we improve the processor complexity of the problem from {dollar}O(n\sp{lcub}2.851{rcub}){dollar} to {dollar}O(n\sp{lcub}2.837{rcub}).{dollar} In another application, we have yielded the acceleration of univariate polynomial factorization over a finite field.
-
Type
-
dissertation
-
Source
-
PQT Legacy CUNY.xlsx
-
degree
-
Ph.D.
