# Skew-sparse matrix multiplication

Preprint · Qiao-Long Huang, Ke Ye, Xiao-Shan Gao

- Archive id: arxiv:2205.06429
- Published: 2022-05-13
- arXiv: https://arxiv.org/abs/2205.06429
- Source URL: https://arxiv.org/abs/2205.06429
- PDF: https://arxiv.org/pdf/2205.06429
- Provenance: arxiv

## Abstract

Based on the observation that $\\mathbb{Q}^{(p-1) \\times (p-1)}$ is isomorphic to a quotient skew polynomial ring, we propose a new method for $(p-1)\\times (p-1)$ matrix multiplication over $\\mathbb{Q}$, where $p$ is a prime number. The main feature of our method is the acceleration for matrix multiplication if the product is skew-sparse. Based on the new method, we design a deterministic algorithm with complexity $O(T^{ω-2} p^2)$, where $T\\le p-1$ is a parameter determined by the skew-sparsity of input matrices and $ω$ is the asymptotic exponent of matrix multiplication. Moreover, by introducing randomness, we also propose a probabilistic algorithm with complexity $O^\\thicksim(t^{ω-2}p^2+p^2\\log\\frac{1}ν)$, where $t\\le p-1$ is the skew-sparsity of the product and $ν$ is the probability parameter.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.