Skip to content
Last Dictionary
Plane
Mathematics & StatisticsHardware & ComputeDeep Learning

matrix multiplication

nounAlso: matmul, GEMM, matrix product, general matrix multiply

In plain wordsThe rule for combining two grids of numbers into a new grid by repeatedly multiplying rows by columns. It is the single calculation AI chips spend most of their time doing.

  1. The operation that combines an m × k matrixmatrix, n.: A rectangular grid of numbers arranged in rows and columns. Most of what a neural network has learned is stored in large grids like this. A and a k × n matrix B into an m × n matrix C, each entry of which is the dot productdot product, n.: A score of how well two lists of numbers line up, found by multiplying matching entries and adding the products. It is large when the lists point the same way and zero when they are at right angles. of a row of A with a column of B. It represents the composition of two linear transformationslinear transformation, n.: A rule for moving every point in a space that keeps straight lines straight and the origin in place: rotating, stretching, reflecting or squashing everything evenly. Every grid of numbers describes one. and is associative but not commutative: AB generally differs from BA. The standard algorithm costs about 2mnk floating-point operations (FLOPsFLOP, n.: A single arithmetic step, such as multiplying or adding two numbers. Counting them measures how much computing went into an AI model, and laws use such counts to decide which models face extra rules.); asymptotically faster algorithms exist, beginning with Volker Strassen's in 1969, but deep learning rarely uses them because of overheads and weaker numerical behavior. Dense layers, attention, feed-forward blocksfeed-forward network, n.: The part of each transformer layer that works on every word separately, after attention has mixed in context. It holds most of a model's adjustable numbers and is thought to store much of its knowledge. and (after rearrangement) convolutions all reduce to large matrix multiplications, so training and inference costs are usually counted in matmul FLOPs, and accelerators — GPUsGPU, abbr.: A computer chip first designed to draw video-game graphics that turned out to be ideal for AI, because it can do thousands of simple calculations at the same time. with tensor corestensor core, n.: A small, specialized part of an AI chip that does one job — multiplying small blocks of numbers together — far faster than ordinary circuits can., TPUsTPU, abbr.: Google's own family of chips built specifically for AI, used to train and run its Gemini models and rented to other companies through its cloud. with systolic arrayssystolic array, n.: A grid of tiny calculators that pass numbers to their neighbors in rhythm, like a heartbeat, so each value is reused many times. AI chips use it to multiply large tables of numbers efficiently. — are designed around them.

    Profiling showed 80 percent of step time in matmuls, so we moved them to bf16.

Cij=∑l=1kAil BljC_{ij} = \sum_{l=1}^{k} A_{il}\,B_{lj}

Origin

Set out systematically by Arthur Cayley in his 1858 memoir as the rule for composing linear substitutions, following the 1812 product theorem for determinants of Jacques Binet and Augustin-Louis Cauchy. Strassen's 1969 algorithm showed that fewer than n³ multiplications suffice, starting a long search for the true exponent; in 2022 DeepMind's AlphaTensor used reinforcement learning to discover new algorithms for small cases.

Usage note

The inner dimensions must match; shape mismatches in matmuls are among the commonest bugs in deep learning code. Element-wise (Hadamard) multiplication of same-shaped arrays is a different operation.

Related

See also
  • matrixmatrix, n.: A rectangular grid of numbers arranged in rows and columns. Most of what a neural network has learned is stored in large grids like this.
  • dot productdot product, n.: A score of how well two lists of numbers line up, found by multiplying matching entries and adding the products. It is large when the lists point the same way and zero when they are at right angles.
  • linear transformationlinear transformation, n.: A rule for moving every point in a space that keeps straight lines straight and the origin in place: rotating, stretching, reflecting or squashing everything evenly. Every grid of numbers describes one.
  • FLOPFLOP, n.: A single arithmetic step, such as multiplying or adding two numbers. Counting them measures how much computing went into an AI model, and laws use such counts to decide which models face extra rules.
  • tensor coretensor core, n.: A small, specialized part of an AI chip that does one job — multiplying small blocks of numbers together — far faster than ordinary circuits can.
  • systolic arraysystolic array, n.: A grid of tiny calculators that pass numbers to their neighbors in rhythm, like a heartbeat, so each value is reused many times. AI chips use it to multiply large tables of numbers efficiently.
  • arithmetic intensityarithmetic intensity, n.: How much calculating a task does for each piece of data it fetches from memory. Tasks with little calculation per fetch are slowed by memory, not by the chip's math speed.

Sources

  1. Strassen, V. (1969). Gaussian Elimination is not Optimal. Numerische Mathematik, 13.
  2. Fawzi, A. et al. (2022). Discovering faster matrix multiplication algorithms with reinforcement learning. Nature, 610.

Mentioned in

AI acceleratorAI accelerator, n.: Any chip built or tuned to speed up AI — graphics chips, Google's TPUs, phone 'neural engines' and many startup designs. Such chips do the heavy math of training and running models., artificial neuronartificial neuron, n.: The basic building block of a neural network: a tiny calculator that multiplies each incoming number by a weight, adds them up, and passes the total through a simple function to decide its output., GPUGPU, abbr.: A computer chip first designed to draw video-game graphics that turned out to be ideal for AI, because it can do thousands of simple calculations at the same time., big O notationbig O notation, n.: Shorthand for how the cost of a computation grows as the problem gets bigger. Saying attention costs 'O(n²)' means doubling the length of the text roughly quadruples the work., dot productdot product, n.: A score of how well two lists of numbers line up, found by multiplying matching entries and adding the products. It is large when the lists point the same way and zero when they are at right angles., linear algebralinear algebra, n.: The branch of mathematics about lists and grids of numbers and the even, straight-line transformations between them. It is the everyday language in which neural networks are written and computed., linear transformationlinear transformation, n.: A rule for moving every point in a space that keeps straight lines straight and the origin in place: rotating, stretching, reflecting or squashing everything evenly. Every grid of numbers describes one., matrixmatrix, n.: A rectangular grid of numbers arranged in rows and columns. Most of what a neural network has learned is stored in large grids like this., tensortensor, n.: A block of numbers with any number of dimensions: a single number, a list, a grid, or a stack of grids. AI software stores and processes all its data this way., tensor coretensor core, n.: A small, specialized part of an AI chip that does one job — multiplying small blocks of numbers together — far faster than ordinary circuits can., arithmetic intensityarithmetic intensity, n.: How much calculating a task does for each piece of data it fetches from memory. Tasks with little calculation per fetch are slowed by memory, not by the chip's math speed., GPGPUGPGPU, abbr.: Using a graphics chip for ordinary number-crunching instead of drawing pictures — the trick that, years later, made modern AI training practical., hardware lotteryhardware lottery, n.: The idea that research ideas succeed partly by luck — because they happen to suit the computer chips available at the time — rather than purely because they are better., photonic computingphotonic computing, n.: Using light instead of electricity to compute or move data. Light can carry huge amounts of information with little energy, but building full computers from it is still very hard., systolic arraysystolic array, n.: A grid of tiny calculators that pass numbers to their neighbors in rhythm, like a heartbeat, so each value is reused many times. AI chips use it to multiply large tables of numbers efficiently., tensor parallelismtensor parallelism, n.: Splitting the individual giant tables of numbers inside each layer of a model across several chips, so that every chip does a slice of every calculation at the same time., TritonTriton, prop. n.: A free language from OpenAI for writing the fast inner routines of AI programs in Python-style code; its compiler handles hardware details that Nvidia's own tools leave to experts.