Fair and Square: Replacing One Real Multiplication with a Single Square and One Complex Multiplication with Three Squares When Performing Matrix Multiplication and Convolutions

This paper proposes a method to significantly reduce hardware resource requirements for matrix multiplications and convolutions by asymptotically replacing real and complex multiplications with fewer squaring operations, which are more efficient to implement in circuits.

The Gist

Imagine you are a master chef running a massive, high-speed kitchen. Your job is to mix thousands of ingredients together to create complex dishes (like AI models or signal processing). In this kitchen, the most expensive, energy-hungry, and space-consuming tool you have is the Heavy Mixer (a mathematical multiplication). Every time you use it, it takes up a lot of counter space and burns a lot of electricity.

The paper you shared proposes a brilliant new trick: Stop using the Heavy Mixer. Instead, use a Lightweight Blender (a squaring operation) that takes up half the space and uses half the power.

Here is how this "Fair and Square" method works, explained simply.

The Core Magic Trick: The "Sum of Squares"

In math, multiplying two numbers ($A \times B$) is usually hard. But the author points out a clever algebraic trick:

If you know how to square a number (multiply it by itself), you can figure out the product of two different numbers just by squaring their sum and their differences.

Think of it like this:

• Old Way: To find out how much 5 apples and 3 oranges cost together, you have to do a specific, heavy calculation for that exact pair.
• New Way: You calculate the cost of "5+3" (8) squared, then subtract the cost of "5" squared and "3" squared. The math works out to give you the same answer, but you only used the "squaring" tool.

Since a "squaring" circuit in computer chips is much simpler and smaller than a full "multiplication" circuit, this saves a huge amount of space and energy.

The Problem: It Seems Messy at First

If you just swap every multiplication for this squaring trick, you might think, "Wait, I'm doing more work now! I have to square the sum, square the first number, square the second number, and then subtract."

It looks like you're adding three steps to replace one. But here is the secret sauce:

In big tasks like Matrix Multiplication (which is how AI "thinks"), you are doing the same calculation over and over again with different numbers.

• The Cheat Code: The "squares of the individual numbers" (the $5^2$and$3^2$ parts) are reusable.
• You can calculate the "squares of the ingredients" once at the start, write them down, and reuse them for every single dish you make.
• So, for the massive bulk of the work, you are only doing one squaring operation per multiplication, plus a tiny bit of pre-calculation.

Real-World Applications in the Paper

1. Matrix Multiplication (The AI Brain)

AI models multiply huge grids of numbers.

• The Old Way: Use a heavy mixer for every single number pair.
• The New Way: Use the "Lightweight Blender." Because the grids are huge, the "pre-calculated" parts become negligible. You effectively get the job done with half the hardware.
• The Hardware: The paper suggests building "Systolic Arrays" (like a conveyor belt of processors) where the heavy mixers are replaced by these lightweight blenders.

2. Convolutions (The Image Filter)

When your phone recognizes a face or filters a photo, it slides a "kernel" (a small pattern) over an image.

• The Trick: Just like with matrices, the "squares of the pattern" can be pre-calculated. The "squares of the image pixels" can be calculated once and reused.
• Result: You can filter images using much less power, which is great for battery life on your phone.

3. Complex Numbers (The Double Trouble)

Sometimes math involves "Complex Numbers" (numbers with a real part and an imaginary part, like $3 + 4i$).

• The Challenge: Multiplying complex numbers usually requires 4 real multiplications.
• The 4-Square Solution: The paper shows you can replace those 4 multiplications with 4 squaring operations.
• The 3-Square Solution (The Grand Finale): The author gets even cleverer. By rearranging the math, they show you can do it with just 3 squaring operations.
  • Analogy: Imagine you need to mix 4 ingredients. Usually, you need 4 mixers. This paper says, "No, if you mix them in a specific order and reuse the leftovers, you only need 3 blenders."

Why Should You Care?

1. Cheaper Chips: Since a squaring circuit is about half the size of a multiplier, chips can be smaller or fit more features in the same space.
2. Longer Battery Life: Less hardware activity means less electricity used. Your AI phone or laptop could run longer on a single charge.
3. Faster AI: With smaller, more efficient chips, we can build bigger, smarter AI models without them overheating or costing a fortune to manufacture.

The Bottom Line

The paper is essentially saying: "Stop trying to force a square peg into a round hole (multiplication) when you can just use a square peg (squaring) and rearrange the furniture."

By realizing that we can "pre-cook" some of the ingredients (the individual squares) and reuse them, we can swap out the heavy, expensive machinery in our computers for lighter, cheaper, and more efficient tools. It's a "Fair and Square" deal for the future of computing.

Technical Summary

Here is a detailed technical summary of the paper "Fair and Square: Replacing One Real Multiplication with a Single Square and One Complex Multiplication with Three Squares When Performing Matrix Multiplications and Convolutions" by Vincenzo Liguori.

1. Problem Statement

Matrix multiplications, convolutions, and linear transforms are fundamental operations in Artificial Intelligence (AI), Digital Signal Processing (DSP), and various other computational fields. These operations rely heavily on multiplication, which is a resource-intensive operation in hardware implementations (FPGAs, ASICs, GPUs).

• Hardware Cost: An $n$-bit squaring circuit requires approximately half the gate count of an $n \times n$ multiplier.
• The Challenge: Reducing the hardware footprint (area) and power consumption of these operations without sacrificing computational accuracy or significantly increasing latency.

2. Methodology

The core methodology relies on algebraic identities to decompose multiplication into squaring operations and additions/subtractions. The paper proposes replacing standard multiplication units with "partial multipliers" based on the following identities:

A. Real Multiplication

The paper utilizes the algebraic expansion of squares:
$$(a+b)^2 = a^2 + b^2 + 2ab \implies ab = \frac{1}{2}((a+b)^2 - a^2 - b^2)$$
$$(a-b)^2 = a^2 + b^2 - 2ab \implies -ab = \frac{1}{2}((a-b)^2 - a^2 - b^2)$$

By applying these identities, a multiplication $ab$ is replaced by:

1. One squaring of the sum/difference $(a \pm b)$.
2. Two pre-calculated or reused squarings of the individual terms $a^2$ and $b^2$.
3. A final scaling by $1/2$ (implemented as a right bit-shift).

B. Complex Multiplication

The paper explores two approaches for complex numbers ($z_1 = a+ib, z_2 = c+is$):

1. 4-Square Approach: Directly applying the real/imaginary decomposition using the 4-square identity (2 squares for the real part, 2 for the imaginary).
2. 3-Square Approach: Utilizing a specific algebraic rearrangement (similar to Karatsuba's algorithm) to reduce the dependency on distinct squares. This allows the complex product to be computed using only 3 squaring operations that depend on both input variables, plus pre-computable terms.

3. Key Contributions

A. Theoretical Reduction Ratios

The paper mathematically demonstrates that for large matrices ($M \times N$ and $N \times P$), the overhead of the additional squaring terms becomes negligible:

• Real Matrix Multiplication: Requires $MNP + MN + NP$ squaring operations. As $M$ and $P$ grow, the ratio of squarings to multiplications approaches 1:1.
• Complex Matrix Multiplication (4-Square): The ratio approaches 4:1.
• Complex Matrix Multiplication (3-Square): The ratio approaches 3:1.

B. Hardware Architecture Proposals

The author proposes specific hardware modifications to leverage these mathematical insights:

• Partial Multiplier Accumulators (MACs): Replacing standard multipliers with units that compute $(a+b)^2$ and accumulate results, while handling pre-calculated terms ($a^2, b^2$) separately.
• Square-Based Systolic Arrays: Modifying Processing Elements (PEs) to accept pre-calculated row/column square sums ($S_a, S_b$) to initialize accumulators, allowing the array to compute matrix products using only squarers.
• Tensor Cores: Adapting tensor core architectures (common in AI accelerators) to use "Complex Partial Multipliers" (CPM) or "CPM3" units, initializing accumulators with pre-computed constants.
• Convolution Engines: Applying the same logic to FIR/IIR filters and 2D convolutions, where kernel weights are often constant, allowing $S_w$ (sum of squared weights) to be pre-calculated.

C. Handling Constants and Reuse

A critical optimization highlighted is the handling of constant coefficients (e.g., in DFT, fixed neural network weights, or kernel filters).

• Terms like $a^2$ or $\sum w_i^2$ can be pre-calculated and stored.
• In matrix multiplication, row/column sums of squares can be reused for every element in the resulting matrix, drastically reducing the effective cost per operation.

4. Results and Analysis

• Resource Efficiency: Since a squaring circuit is roughly 50% smaller than a multiplier, replacing multiplications with squarings yields significant area savings.
  • For real operations: ~50% reduction in multiplier logic (replaced by smaller squarers).
  • For complex operations: Replacing 4 complex multipliers (which typically use 4 real multipliers) with 3 squarers and adders offers substantial gate count reductions.
• Scalability: The efficiency gain increases with matrix size. For small matrices, the overhead of pre-calculating $a^2$ and $b^2$ is significant, but for large-scale AI inference (where $M, N, P$ are large), the overhead is asymptotically negligible.
• Accuracy: The method is exact (lossless) provided the arithmetic precision is maintained. The paper notes that approximate squaring is also a possibility for further optimization in loss-tolerant applications.

5. Significance

• Hardware Optimization: This work provides a concrete pathway to design more energy-efficient and area-efficient AI accelerators and DSP chips. By shifting the computational burden from multipliers to squarers, designers can fit more compute units into the same silicon area or reduce power consumption.
• Algorithmic Flexibility: The paper transcends specific hardware, offering a mathematical framework applicable to systolic arrays, tensor cores, and standard MAC units.
• Complex Number Efficiency: The derivation of the 3-square method for complex multiplication is particularly significant, as it improves upon the standard 4-square (or 4-multiply) approach, offering a new trade-off for high-performance computing.
• Broader Applicability: While focused on matrix multiplication and convolutions, the methodology is applicable to dot products, linear transforms (DFT, DCT), and correlations, making it a versatile tool for signal processing and machine learning hardware design.

In conclusion, the paper argues that "squaring" is a more hardware-efficient primitive than "multiplication" for these specific linear algebra operations. By restructuring the computation flow to utilize pre-calculated square terms and partial products, significant resource savings can be achieved in next-generation computing hardware.