Improved basis-change transformations for $2 \times 2$ matrix multiplication

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 [1, 2, 3, 4]. Let $R$ be an arbitrary ring, and let $A$, $B \in R^{2 \times2}$ be matrices over this ring. We use column-major vectorization, $\vec{A} = [a_{11}\ a_{21}\ a_{12}\ a_{22}]^{\mathsf{T}}$. Here and below, when counting additions, we will use the convention that a subtraction also counts as an addition, see [4, 5, 6]. Let the matrices $U$, $V$, $W \in\mathbb{Z}^{7 \times4}$ satisfy

for all matrices $A$, $B \in R^{2 \times2}$. Moreover, let $B_U$, $B_V$, $B_W \in\mathbb{Z}^{4 \times4}$ 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_Ux$, $B_Vx$, and $B_Wx$. Finally, denote by $\alpha_U$, $\alpha_V$, and $\alpha_W$ the number of additions required to compute respectively $\widetilde{U}\tilde{x}$, $\widetilde{V}\tilde{x}$, and $\widetilde{W}^{\mathsf{T}}y$ for arbitrary $x \in R^4$, and $y \in R^7$, with

Proof See Claim 2.9, Claim 2.12, and Corollary 2.15 in [1].

Now consider matrices

with basis-change matrices

It is straightforward to verify that the matrix triple $U,V,W$ satisfies equation (1.1), 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 equation (1.2).

We can compute $\widetilde{U},\widetilde{V},$ and $\widetilde{W}$ as follows

The linear transformations induced by $\widetilde{U}$ and $\widetilde{V}$ can be computed using 3 additions each as follows:

such that

for all $x\in\mathbb{R}^4$. Therefore $\alpha_U=\alpha_V=3$. The linear transformation induced by $\widetilde{W}^{\mathsf{T}}$ can be computed using 6 additions as follows:

such that

for any $M\in\mathbb{R}^7$. From which it follows that $\alpha_W=6$.

By Theorem 1.1 we can thus multiply two $n\times n$ matrices using a Karstadt–Schwartz-style basis-change in

arithmetic operations, using the basis-change induced by the matrices $B_U,B_V,$ and $B_W$ defined in equation (1.3).

Verification

The following Python program provides a simple verification of the scheme.

"""
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)=}")

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 the machine. I take full responsibility for the final manuscript.