Fast rectangular matrix multiplication and some applications |
| |
作者单位: | Department of |
| |
摘 要: | We study asymptotically fast multiplication algorithms for matrix pairs of arbitrary di- mensions, and optimize the exponents of their arithmetic complexity bounds. For a large class of input matrix pairs, we improve the known exponents. We also show some applications of our results:(i) we decrease from O(n~2 n~(1 o)(1)logq)to O(n~(1.9998) n~(1 o(1))logq)the known arithmetic complexity bound for the univariate polynomial factorization of degree n over a finite field with q elements; (ii) we decrease from 2.837 to 2.7945 the known exponent of the work and arithmetic processor bounds for fast deterministic(NC)parallel evaluation of the determinant, the characteristic polynomial, and the inverse of an n×n matrix, as well as for the solution to a nonsingular linear system of n equations; (iii)we decrease from O(m~(1.575)n)to O(m~(1.5356)n)the known bound for computing basic solutions to a linear programming problem with m constraints and n variables.
|
收稿时间: | 24 January 2006 |
修稿时间: | 19 August 2007 |
Fast rectangular matrix multiplication and some applications |
| |
Authors: | Ke ShanXue Zeng BenSheng Han WenBao Victor Y Pan |
| |
Abstract: | We study asymptotically fast multiplication algorithms for matrix pairs of arbitrary dimensions, and optimize the exponents
of their arithmetic complexity bounds. For a large class of input matrix pairs, we improve the known exponents. We also show
some applications of our results: (i) we decrease from O(n
2 + n
1+o(1)logq) to O(n
1.9998 + n
1+o(1)logq) the known arithmetic complexity bound for the univariate polynomial factorization of degree n over a finite field with q elements; (ii) we decrease from 2.837 to 2.7945 the known exponent of the work and arithmetic processor bounds for fast deterministic
(NC) parallel evaluation of the determinant, the characteristic polynomial, and the inverse of an n × n matrix, as well as for the solution to a nonsingular linear system of n equations; (iii) we decrease from O(m
1.575
n) to O(m
1.5356
n) the known bound for computing basic solutions to a linear programming problem with m constraints and n variables.
|
| |
Keywords: | rectangular matrix multiplication asymptotic arithmetic complexity bilinear algorithm polynomial factorization over finite fields |
本文献已被 CNKI SpringerLink 等数据库收录! |