Fast rectangular matrix multiplication and applications

DOI10.1006/jcom.1998.0476zbMath0919.65030OpenAlexW2033961328MaRDI QIDQ1271174

Xiaohan Huang, Pan, Victor Y.

Publication date: 14 February 1999

Published in: Journal of Complexity (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/ee64ab6a05667113e2f6808dceed08a187387db6

zbMATH Keywords

computational complexitylinear programmingparallel complexityarithmetic complexityfast rectangular matrix multiplicationunivariate polynomial factorization

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Linear programming (90C05) Numerical computation of solutions to single equations (65H05) Parallel numerical computation (65Y05) Complexity and performance of numerical algorithms (65Y20)

Related Items

A Combinatorial Algorithm for All-Pairs Shortest Paths in Directed Vertex-Weighted Graphs with Applications to Disc Graphs, Quantum and approximation algorithms for maximum witnesses of Boolean matrix products, Faster algorithms for finding lowest common ancestors in directed acyclic graphs, Fast operations on linearized polynomials and their applications in coding theory, Dynamic matrix rank, Fast dynamic transitive closure with lookahead, Dynamic shortest paths and transitive closure: algorithmic techniques and data structures, On design of circuits of logarithmic depth for inversion in finite fields, Nonuniform ACC Circuit Lower Bounds, The Closest Pair Problem under the Hamming Metric, On the complexity exponent of polynomial system solving, The aggregation and cancellation techniques as a practical tool for faster matrix multiplication, Modular composition modulo triangular sets and applications, Complexity of computation in finite fields, Efficiently correcting matrix products, Induced subgraph isomorphism: are some patterns substantially easier than others?, Counting Homomorphic Cycles in Degenerate Graphs, Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter, Directed evaluation, A Path Cover Technique for LCAs in Dags, Faster algorithms for all-pairs small stretch distances in weighted graphs, All-pairs bottleneck paths in vertex weighted graphs, A fast output-sensitive algorithm for Boolean matrix multiplication, Are unique subgraphs not easier to find?, Fast matrix multiplication and its algebraic neighbourhood, Computing the sign or the value of the determinant of an integer matrix, a complexity survey., All-pairs disjoint paths from a common ancestor in \(\widetilde O (n^\omega)\) time, Recognizing quasi-triangulated graphs., Fast rectangular matrix multiplication and some applications, Fast computation of special resultants, Point counting in families of hyperelliptic curves, Open problems around exact algorithms, On minimum witnesses for Boolean matrix multiplication, Drinfeld modules with complex multiplication, Hasse invariants and factoring polynomials over finite fields, Factoring polynomials over finite fields: A survey, On the complexity of fixed parameter clique and dominating set, Faster multi-witnesses for Boolean matrix multiplication, Fast algorithms for the Sylvester equation \(AX-XB^{T}=C\), On constructing circuits for transforming the polynomial and normal bases of finite fields from one to the other, Modular composition via factorization, Fast multivariate multi-point evaluation revisited, A fully dynamic algorithm for maintaining the transitive closure, An improved upper bound on maximal clique listing via rectangular fast matrix multiplication, Faster Algorithms for All-Pairs Small Stretch Distances in Weighted Graphs, Detecting directed 4-cycles still faster, Rare siblings speed-up deterministic detection and counting of small pattern graphs, Optimal fast Johnson-Lindenstrauss embeddings for large data sets, Computing Puiseux series: a fast divide and conquer algorithm, A fast algorithm for reversion of power series, Unique subgraphs are not easier to find, Accelerated tower arithmetic, Taking roots over high extensions of finite fields, Dominance Product and High-Dimensional Closest Pair under L_infty

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• How to multiply matrices faster
• Matrix multiplication via arithmetic progressions
• Parallel evaluation of the determinant and of the inverse of a matrix
• \(0(n^{2.7799})\) complexity for \(n\times n\) approximate matrix multiplication
• Using fast matrix multiplication to find basic solutions
• Rectangular matrix multiplication revisited
• Parallel computation of polynomial GCD and some related parallel computations over abstract fields
• Computing Frobenius maps and factoring polynomials
• Gaussian elimination is not optimal
• How Can We Speed Up Matrix Multiplication?
• Relative bilinear complexity and matrix multiplication.
• The asymptotic spectrum of tensors.
• Partial and Total Matrix Multiplication
• On the Asymptotic Complexity of Matrix Multiplication
• Rapid Multiplication of Rectangular Matrices
• A New Algorithm for Factoring Polynomials Over Finite Fields
• On the Number of Multiplications Required for Matrix Multiplication
• Fast Algorithms for Manipulating Formal Power Series
• Factoring Polynomials Over Large Finite Fields
• On Sets of Integers Which Contain No Three Terms in Arithmetical Progression
• On Sets of Integers Which Contain No Three Terms in Arithmetical Progression