\documentclass[pdflatex,sn-mathphys-num]{sn-jnl} \usepackage{graphicx} \usepackage{multirow} \usepackage{amsmath,amssymb,amsfonts} \usepackage{amsthm} \numberwithin{equation}{section} \usepackage{mathrsfs} \usepackage[title]{appendix} \usepackage{xcolor} \usepackage{subcaption} \usepackage{caption} \usepackage{textcomp} \usepackage{manyfoot} \usepackage{booktabs} \usepackage{mathtools} \usepackage{algorithm} \usepackage{algorithmicx} \usepackage{algpseudocode} \usepackage{listings} \usepackage{tikz} \usetikzlibrary{math,calc,decorations.pathreplacing,decorations.pathmorphing,decorations.shapes,arrows.meta,fit,backgrounds,shapes.geometric} \usetikzlibrary{circuits.logic.US} \usepackage{tikz-3dplot} \hypersetup{ colorlinks=true, linkcolor=black, urlcolor=black, citecolor=black, filecolor=black } \definecolor{pythonBackground}{RGB}{248,249,251} \definecolor{pythonFrame}{RGB}{205,210,218} \definecolor{pythonKeyword}{RGB}{33,85,138} \definecolor{pythonComment}{RGB}{86,116,86} \definecolor{pythonString}{RGB}{153,76,0} \lstdefinestyle{pythonstyle}{ language=Python, backgroundcolor=\color{pythonBackground}, basicstyle=\ttfamily\scriptsize, keywordstyle=\color{pythonKeyword}\bfseries, commentstyle=\color{pythonComment}\itshape, stringstyle=\color{pythonString}, numbers=left, numberstyle=\tiny\color{gray!70!black}, numbersep=8pt, frame=single, rulecolor=\color{pythonFrame}, framerule=0.4pt, framesep=5pt, breaklines=true, breakatwhitespace=false, showstringspaces=false, keepspaces=true, columns=fullflexible, tabsize=4, upquote=true, xleftmargin=2.4em, framexleftmargin=2em, captionpos=t, aboveskip=1em, belowskip=1em, } % fix sn-jnl table environment so [H] from float works on tables \renewenvironment{table}[1][]% {\tableorg[#1]% \tablebodyfont% \renewcommand\footnotetext[2][]{{\removelastskip\vskip3pt% \let\tablebodyfont\tablefootnotefont% \hskip0pt\if!##1!\else{\smash{$^{##1}$}}\fi##2\par}}% }{\endtableorg} \usepackage{float} \usepackage{lmodern} \usepackage{newtxtext} \usepackage{newtxmath} \usepackage{listings} \usepackage[noabbrev]{cleveref} \newcommand\crefrangeconjunction{\textendash} \crefname{ALG@line}{line}{lines} \Crefname{ALG@line}{Line}{Lines} \crefname{problem}{Problem}{Problems} \Crefname{problem}{Problem}{Problems} \crefname{appsubsection}{Appendix}{Appendices} \Crefname{appsubsection}{Appendix}{Appendices} \crefname{example}{Example}{Examples} \Crefname{example}{Example}{Examples} \crefname{paragraph}{Section}{Sections} \Crefname{paragraph}{Section}{Sections} \renewcommand{\crefrangeconjunction}{\textendash} \crefname{lstlisting}{Listing}{Listings} \Crefname{lstlisting}{Listing}{Listings} \usepackage{pgfplots} \pgfplotsset{compat=1.18} \usetikzlibrary{patterns} \usepackage{geometry} \geometry{a4paper, margin=2.5cm} \usepackage[T1]{fontenc} \usepackage{titlesec} \usepackage{longtable} \usepackage{array} % custom commands start \DeclareMathOperator{\relu}{ReLU} \newcommand{\del}{\partial} \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}{Corollary}[theorem] % find out styling \theoremstyle{definition} \newtheorem{problem}{Problem}[section] \newtheorem{definition}{Definition}[section] \newtheorem{example}{Example}[section] % custom commands end \begin{document} \title[Improved basis-change transformations for $2 \times 2$ matrix multiplication]{Improved basis-change transformations for $2 \times 2$ matrix multiplication} \author*[1]{\fnm{Hugo Møller} \sur{Nielsen}}\email{hugomn2002@gmail.com} \affil[1]{\orgdiv{Mathematical Institute for Machine Learning and Data Science (MIDS)}, \orgname{Catholic University of Eichstätt-Ingolstadt (KU)}, \orgaddress{\city{Ingolstadt}, \postcode{85049}, \country{Germany}}} \abstract{ To the best of our knowledge, we present a state-of-the-art change-of-basis algorithm for $2 \times 2$ matrix multiplication under the Karstadt--Schwartz-style basis change regime \cite{SchwartzVaknin2023}. We do this by introducing basis-change matrices $B_U$, $B_V$, and $B_W$ that each require only a single addition and hence give rise to a matrix-multiplication algorithm performing \begin{align*} 5n^{\log_2{7}} - 4n^2 + \frac{3}{4}n^2 \log_2{n}, \end{align*} arithmetic operations when multiplying two $n \times n$ matrices, with $n$ a power of $2$. This improves on the previous best bound, which had last term $\frac{3}{2}n^2\log_2{n}$. } \keywords{matrix multiplication, addition minimization, additive complexity, Strassen's algorithm} \maketitle \section{Introduction} The Karstadt--Schwartz-style basis change is a well-studied method, and we will not repeat the method here. For background on the Karstadt--Schwartz-style basis-change method, see \cite{SchwartzVaknin2023,KarstadtSchwartz2020,KarstadtSchwartz2017,nielsen2026matrixmultiplication}. Let $R$ be an arbitrary ring, and let $A,B \in R^{2 \times 2}$ be matrices over this ring. We use column-major vectorization, $\vec{A} = \begin{bmatrix} a_{11} & a_{21} & a_{12} & a_{22} \end{bmatrix}^\intercal$. Here and below, when counting additions, we will use the convention that a subtraction also counts as an addition, see \cite{VanZeeSmith2016,Blaeser2013,nielsen2026matrixmultiplication}. Let the matrices $U,V,W \in \mathbb{Z}^{7 \times 4}$ satisfy \begin{align} \vec{AB} = W^\intercal \left((U\vec{A}) \odot (V\vec{B})\right), \label{eq:fundamental_matmul} \end{align} for all matrices $A,B \in R^{2 \times 2}$. Moreover, let $B_U,B_V,B_W \in \mathbb{Z}^{4 \times 4}$ be invertible over $\mathbb{Z}$. For arbitrary $x \in R^4$, let $\beta_U, \beta_V, \beta_W$ denote the number of additions required to compute respectively $B_U x$, $B_V x$, and $B_W^\intercal x$. Finally, denote by $\alpha_U$, $\alpha_V$, and $\alpha_W$ the number of additions required to compute respectively $\tilde U x$, $\tilde V x$, and $\tilde W^\intercal y$ for arbitrary $x \in R^{4}$, and $y \in R^{7}$, with \begin{align*} \tilde U & = U B_U^{-1}, & \tilde V & = V B_V^{-1}, & \tilde W & = W B_W^{-1}. \end{align*} \begin{theorem} \label{thm:helper_thm} For $n \in \mathbb{N}$ an integer-power of $2$ we can multiply matrices $A,B \in R^{n \times n}$ in \begin{align} \label{eq:thm_1} \left(1 + \frac{\alpha_U + \alpha_V + \alpha_W}{3}\right)n^{\log_2{7}} - \frac{\alpha_U + \alpha_V + \alpha_W}{3} n^2 + \frac{\beta_U + \beta_V + \beta_W}{4}n^2 \log_2{n} \end{align} arithmetic operations. \end{theorem} \begin{proof} See Claim~2.9, Claim~2.12, and Corollary~2.15 in \cite{SchwartzVaknin2023}. \end{proof} Now consider matrices \begin{align*} U & =\begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & -1 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & -1 & 0 & 1 \\ -1 & -1 & 1 & 1 \end{bmatrix}, & V & =\begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ -1 & -1 & 1 & 1 \\ 0 & -1 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & -1 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix}, & W & =\begin{bmatrix} 1 & 0 & 0 & 0 \\ 1 & -1 & 1 & -1 \\ 0 & -1 & 0 & 0 \\ 0 & -1 & 1 & -1 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & -1 & 1 \\ 0 & 0 & -1 & 0 \end{bmatrix}, \end{align*} with basis-change matrices \begin{align} \label{eq:basis_changes} S = B_U = B_V & =\begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 \end{bmatrix}, & S^{-1} = B_W & =\begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & -1 & 1 \end{bmatrix}. \end{align} It is straightforward to verify that the matrix triple $U,V,W$ satisfies \cref{eq:fundamental_matmul}, and that $B_U, B_V$, and $B_W$ are invertible over $\mathbb{Z}$. Moreover, clearly $\beta_U = \beta_V = \beta_W = 1$, giving us the trailing term $\frac{3}{4}n^2 \log_2{n}$ in \cref{eq:thm_1}. We can compute $\tilde U, \tilde V$, and $\tilde W$ as follows \begin{align*} \tilde U & = U B_U^{-1} = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & -1 & 0 & 1 \\ 0 & 0 & 0 & 1 \\ 0 & -1 & -1 & 1 \\ -1 & -1 & 0 & 1 \end{bmatrix}, & \tilde V & = V B_V^{-1} = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ -1 & -1 & 0 & 1 \\ 0 & -1 & 0 & 1 \\ 0 & 0 & 0 & 1 \\ 0 & -1 & -1 & 1 \\ 0 & 0 & 1 & 0 \\ \end{bmatrix}, & \tilde W & = W B_W^{-1} = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 1 & -1 & 0 & -1 \\ 0 & -1 & 0 & 0 \\ 0 & -1 & 0 & -1 \\ 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & -1 & 0 \\ \end{bmatrix} \end{align*} The linear transformations induced by $\tilde U$ and $\tilde V$ can be computed using $3$ additions each as follows: \begin{align*} s_1 & = x_4 - x_2, & s_2 & = s_1 - x_3, & s_3 & = s_1 - x_1. \end{align*} such that \begin{align*} \tilde U x & = \begin{bmatrix} x_1 & x_3 & x_2 & s_1 & x_4 & s_2 & s_3 \end{bmatrix}^\intercal \\ \tilde V x & = \begin{bmatrix} x_1 & x_2 & s_3 & s_1 & x_4 & s_2 & x_3 \end{bmatrix}^\intercal \\ \end{align*} for all $x \in R^{4}$. Therefore $\alpha_{U} = \alpha_{V} = 3$. The linear transformation induced by $\tilde W^\intercal$ can be computed using $6$ additions as follows: \begin{align*} t_1 & = M_5-M_4, & t_2 & = t_1-M_2, \\ y_1 & = M_1+M_2, & y_2 & = t_2-M_3, \\ y_3 & = M_5-M_7, & y_4 & = t_2+M_6, \end{align*} such that \begin{align*} \tilde W^\intercal M = \begin{bmatrix} y_1 & y_2 & y_3 & y_4 \end{bmatrix}^\intercal \end{align*} for any $M \in R^7$. From which it follows that $\alpha_{W} = 6$. By \Cref{thm:helper_thm} we can thus multiply two $n \times n$ matrices using a Karstadt--Schwartz-style basis-change in \begin{align*} 5n^{\log_2{7}} - 4n^2 + \frac{3}{4}n^2\log_2{n} \end{align*} arithmetic operations, using the basis-change induced by the matrices $B_U$, $B_V$, and $B_W$ defined in \cref{eq:basis_changes}. \appendix \section{Verification} The following Python program provides a simple verification of the scheme. \begin{lstlisting}[ style=pythonstyle, caption={Small verification script (\texttt{verify.py}).}, label={lst:small-verify} ] """ Artisinally hand-crafted code """ import numpy as np import sympy as sp inv = np.linalg.inv S = np.array([[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 1, 1]]).astype(int) assert(not any(((S @ inv(S).astype(int)) - np.eye(4)).flatten())) # inv over Z sanity check U = np.array( [ [1, 0, 0, 0], [0, 0, 1, 0], [0, 1, 0, 0], [0, -1, 1, 1], [0, 0, 1, 1], [0, -1, 0, 1], [-1, -1, 1, 1] ]).astype(int) V = np.array( [ [1, 0, 0, 0], [0, 1, 0, 0], [-1, -1, 1, 1], [0, -1, 1, 1], [0, 0, 1, 1], [0, -1, 0, 1], [0, 0, 1, 0] ]).astype(int) W = np.array( [ [1, 0, 0, 0], [1, -1, 1, -1], [0, -1, 0, 0], [0, -1, 1, -1], [0, 1, 0, 1], [0, 0, -1, 1], [0, 0, -1, 0] ]).astype(int) A_vec = sp.Matrix([sp.Symbol(f"A_{j}{i}", commutative=False) for i in range(1,3) for j in range(1,3)]) B_vec = sp.Matrix([sp.Symbol(f"B_{j}{i}", commutative=False) for i in range(1,3) for j in range(1,3)]) # sanity check that U,V,W encodes matrix multiplication print("#" * 32) hadamard = sp.matrices.dense.matrix_multiply_elementwise print(f"{sp.simplify(W.T @ hadamard((U @ A_vec), (V @ B_vec)))=}") U_tilde = U @ inv(S).astype(int) V_tilde = V @ inv(S).astype(int) W_tilde = W @ S print("#" * 32) print(f"{U_tilde=}") print(f"{V_tilde=}") print(f"{W_tilde.T=}") def compute_U(x): s_1 = x[3] - x[1] # 1 add s_2 = s_1 - x[2] # 2 add s_3 = s_1 - x[0] # 3 add return sp.Matrix([x[0], x[2], x[1], s_1, x[3], s_2, s_3]) def compute_V(x): s_1 = x[3] - x[1] # 1 add s_2 = s_1 - x[2] # 2 add s_3 = s_1 - x[0] # 3 add return sp.Matrix([x[0], x[1], s_3, s_1, x[3], s_2, x[2]]) def compute_W(M): t_1 = M[4] - M[3] # 1 add t_2 = t_1 - M[1] # 2 add y_1 = M[0] + M[1] # 3 add y_2 = t_2 - M[2] # 4 add y_3 = M[4] - M[6] # 5 add y_4 = t_2 + M[5] # 6 add return sp.Matrix([y_1, y_2, y_3, y_4]) print("#" * 32) x = sp.Matrix([sp.Symbol(f"x_{i}") for i in range(1,5)]) y = sp.Matrix([sp.Symbol(f"x_{i}") for i in range(1,8)]) print(f"Should be a bunch of zeros only:") print(f"{U_tilde @ x - compute_U(x)=}") print(f"{V_tilde @ x - compute_V(x)=}") print(f"{W_tilde.T @ y - compute_W(y)=}") \end{lstlisting} \bmhead{Declaration of use of generative AI} GPT-6-Astra was used for finding this result. The manuscript is prepared by me, with minor language editing and grammar help from \textbf{the machine}. I take full responsibility for the final manuscript. %% BioMed_Central_Bib_Style_v1.01 \begin{thebibliography}{6} % BibTex style file: bmc-mathphys.bst (version 2.1), 2014-07-24 \ifx \bisbn \undefined \def \bisbn #1{ISBN #1}\fi \ifx \binits \undefined \def \binits#1{#1}\fi \ifx \bauthor \undefined \def \bauthor#1{#1}\fi \ifx \batitle \undefined \def \batitle#1{#1}\fi \ifx \bjtitle \undefined \def \bjtitle#1{#1}\fi \ifx \bvolume \undefined \def \bvolume#1{\textbf{#1}}\fi \ifx \byear \undefined \def \byear#1{#1}\fi \ifx \bissue \undefined \def \bissue#1{#1}\fi \ifx \bfpage \undefined \def \bfpage#1{#1}\fi \ifx \blpage \undefined \def \blpage #1{#1}\fi \ifx \burl \undefined \def \burl#1{\textsf{#1}}\fi \ifx \doiurl \undefined \def \doiurl#1{\url{https://doi.org/#1}}\fi \ifx \betal \undefined \def \betal{\textit{et al.}}\fi \ifx \binstitute \undefined \def \binstitute#1{#1}\fi \ifx \binstitutionaled \undefined \def \binstitutionaled#1{#1}\fi \ifx \bctitle \undefined \def \bctitle#1{#1}\fi \ifx \beditor \undefined \def \beditor#1{#1}\fi \ifx \bpublisher \undefined \def \bpublisher#1{#1}\fi \ifx \bbtitle \undefined \def \bbtitle#1{#1}\fi \ifx \bedition \undefined \def \bedition#1{#1}\fi \ifx \bseriesno \undefined \def \bseriesno#1{#1}\fi \ifx \blocation \undefined \def \blocation#1{#1}\fi \ifx \bsertitle \undefined \def \bsertitle#1{#1}\fi \ifx \bsnm \undefined \def \bsnm#1{#1}\fi \ifx \bsuffix \undefined \def \bsuffix#1{#1}\fi \ifx \bparticle \undefined \def \bparticle#1{#1}\fi \ifx \barticle \undefined \def \barticle#1{#1}\fi \bibcommenthead \ifx \bconfdate \undefined \def \bconfdate #1{#1}\fi \ifx \botherref \undefined \def \botherref #1{#1}\fi \ifx \url \undefined \def \url#1{\textsf{#1}}\fi \ifx \bchapter \undefined \def \bchapter#1{#1}\fi \ifx \bbook \undefined \def \bbook#1{#1}\fi \ifx \bcomment \undefined \def \bcomment#1{#1}\fi \ifx \oauthor \undefined \def \oauthor#1{#1}\fi \ifx \citeauthoryear \undefined \def \citeauthoryear#1{#1}\fi \ifx \endbibitem \undefined \def \endbibitem {}\fi \ifx \bconflocation \undefined \def \bconflocation#1{#1}\fi \ifx \arxivurl \undefined \def \arxivurl#1{\textsf{#1}}\fi \csname PreBibitemsHook\endcsname %%% 1 \bibitem[\protect\citeauthoryear{Schwartz and Vaknin}{2023}]{SchwartzVaknin2023} \begin{barticle} \bauthor{\bsnm{Schwartz}, \binits{O.}}, \bauthor{\bsnm{Vaknin}, \binits{N.}}: \batitle{Pebbling game and alternative basis for high performance matrix multiplication}. \bjtitle{SIAM Journal on Scientific Computing} \bvolume{45}(\bissue{6}), \bfpage{C277--C303} (\byear{2023}) \doiurl{10.1137/22M1502719} \end{barticle} \endbibitem %%% 2 \bibitem[\protect\citeauthoryear{Karstadt and Schwartz}{2020}]{KarstadtSchwartz2020} \begin{barticle} \bauthor{\bsnm{Karstadt}, \binits{E.}}, \bauthor{\bsnm{Schwartz}, \binits{O.}}: \batitle{Matrix multiplication, a little faster}. \bjtitle{Journal of the ACM} \bvolume{67}(\bissue{1}), \bfpage{1}--\blpage{31} (\byear{2020}) \doiurl{10.1145/3364504} \end{barticle} \endbibitem %%% 3 \bibitem[\protect\citeauthoryear{Karstadt and Schwartz}{2017}]{KarstadtSchwartz2017} \begin{bchapter} \bauthor{\bsnm{Karstadt}, \binits{E.}}, \bauthor{\bsnm{Schwartz}, \binits{O.}}: \bctitle{Matrix multiplication, a little faster}. In: \bbtitle{Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures}. \bsertitle{SPAA '17}, pp. \bfpage{101}--\blpage{110}. \bpublisher{Association for Computing Machinery}, \blocation{New York, NY, USA} (\byear{2017}). \doiurl{10.1145/3087556.3087579} . \burl{https://doi.org/10.1145/3087556.3087579} \end{bchapter} \endbibitem %%% 4 \bibitem[\protect\citeauthoryear{Nielsen}{2026}]{nielsen2026matrixmultiplication} \begin{botherref} \oauthor{\bsnm{Nielsen}, \binits{H.}}: A 52-Addition, Rank-23 Scheme for Exact {$3 \times 3$} Matrix Multiplication (2026). \doiurl{10.48550/arXiv.2609.06588} . \url{https://arxiv.org/abs/2609.06588} \end{botherref} \endbibitem %%% 5 \bibitem[\protect\citeauthoryear{Van~Zee and Smith}{2016}]{VanZeeSmith2016} \begin{botherref} \oauthor{\bsnm{Van~Zee}, \binits{F.G.}}, \oauthor{\bsnm{Smith}, \binits{T.M.}}: Inducing complex matrix multiplication via the {3m} and {4m} methods. FLAME Working Note~81, The University of Texas at Austin, Austin, TX, USA (October 2016). \url{https://www.cs.utexas.edu/%7Eflame/pubs/flawn81.pdf} \end{botherref} \endbibitem %%% 6 \bibitem[\protect\citeauthoryear{Bl{\"a}ser}{2013}]{Blaeser2013} \begin{barticle} \bauthor{\bsnm{Bl{\"a}ser}, \binits{M.}}: \batitle{Fast matrix multiplication}. \bjtitle{Theory of Computing Library, Graduate Surveys} \bvolume{5}, \bfpage{1}--\blpage{60} (\byear{2013}) \doiurl{10.4086/toc.gs.2013.005} \end{barticle} \endbibitem \end{thebibliography} \end{document}