Computational Improvements to Matrix Operations

2006/01/18 by Gordon Chalmers, Chalmers, Gordon
Engineering · #FOS: Physical sciences #General Physics (physics.gen-ph) #Scheduling and Optimization Algorithms

paper · pdf · doi:10.48550/arxiv.physics/0601134

openalex publication_date 2006/01/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

An alternative to the matrix inverse procedure is presented. Given a bit register which is arbitrarily large, the matrix inverse to an arbitrarily large matrix can be peformed in \cal O(N²) operations, and to matrix multiplication on a vector in \cal O(N). This is in contrast to the usual \cal O(N³) and \cal O(N²). A finite size bit register can lead to speeds up of an order of magnitude in large matrices such as 500× 500. The FFT can be improved from \cal O(Nln N) to \cal O(N) steps, or even fewer steps in a modified butterfly configuration.

Related

• On Fast Matrix Inversion via Fast Matrix Multiplication
• A Tight I/O Lower Bound for Matrix Multiplication
• On matrices with displacement structure: generalized operators and faster algorithms
• Sparsifying the Operators of Fast Matrix Multiplication Algorithms
• Efficient Matrix Multiplication: The Sparse Power-of-2 Factorization