Efficient Matrix Vector Multiplication with Einstein Summation in Python

by

💡 Problem Formulation: In computational mathematics, the multiplication of a matrix by a vector is a fundamental operation. This article tackles how one might perform matrix-vector multiplication efficiently in Python using the Einstein summation convention. For example, given a matrix A (2×3) and a vector v (3×1), our aim is to compute the resulting vector (2×1) that represents the product A * v.

Method 1: NumPy’s einsum Function

NumPy’s einsum function leverages the Einstein summation convention, allowing for concise and efficient matrix-vector multiplication. Specifying the subscript strings correctly dictates the operation’s semantics, in this case, matrix-vector multiplication. The function signature is numpy.einsum(subscripts, operand1, operand2), where subscripts is a string specifying the desired summation.

Here’s an example:

import numpy as np

A = np.array([[1, 2, 3],[4, 5, 6]])
v = np.array([7, 8, 9])

result = np.einsum('ij,j->i', A, v)
print(result)

Output: [ 50 122]

This snippet demonstrates the use of einsum with the subscript ‘ij,j->i’ directing the summation across the second dimension (columns) of the matrix and the dimension of the vector. The ->i signifies that a vector is the expected output, which is the dot product of the matrix rows and the input vector.

Method 2: NumPy’s dot Function

The dot function in NumPy is a straightforward way to perform matrix-vector multiplication. It computes the dot product of two arrays. For 2-D arrays, it is equivalent to matrix multiplication, and for 1-D arrays to inner product of vectors.

Here’s an example:

import numpy as np

A = np.array([[1, 2, 3],[4, 5, 6]])
v = np.array([7, 8, 9])

result = np.dot(A, v)
print(result)

Output: [ 50 122]

This code snippet multiplies the matrix A with the vector v using the dot function, leading to the matrix-vector multiplication output. It’s a more intuitive method for those already familiar with linear algebra terminology.

Method 3: NumPy’s matmul Function

The matmul function in NumPy performs matrix product of two arrays. While it is similar to the dot function for one-dimensional arrays, it is preferred in explicit matrix multiplication operations, since its readability is higher and it adheres to the conventional notation of linear algebra.

Here’s an example:

import numpy as np

A = np.array([[1, 2, 3],[4, 5, 6]])
v = np.array([7, 8, 9])

result = np.matmul(A, v)
print(result)

Output: [ 50 122]

By applying matmul, we calculate the product of the matrix A and the vector v, which yields the matrix-vector multiplication result. It is an easy-to-read option that expresses the operation in a way that’s familiar to those used to matrix operations in mathematics.

Method 4: Manual Implementation of Einstein Summation

A manual implementation of the Einstein summation convention for matrix-vector multiplication can be educational and provides insight into the operation’s mechanics. It consists of nested loops where we explicitly compute the sum of products between matrix rows and vector elements.

Here’s an example:

A = [[1, 2, 3],[4, 5, 6]]
v = [7, 8, 9]

result = [sum(row[i] * v[i] for i in range(len(v))) for row in A]
print(result)

Output: [50, 122]

This code manually implements the equivalent of the Einstein summation convention through list comprehension, iterating over each row of matrix A and multiplying by the corresponding element in vector v, followed by summation. This method is valuable for understanding the underlying process but is less efficient than NumPy-based approaches.

Bonus One-Liner: Method 5: NumPy’s multiply and sum Methods

A combination of NumPy’s multiply and sum methods can efficiently conduct matrix-vector multiplication in a straightforward one-liner. This method multiplies corresponding elements and then sums over an axis.

Here’s an example:

import numpy as np

A = np.array([[1, 2, 3],[4, 5, 6]])
v = np.array([7, 8, 9])

result = np.sum(np.multiply(A, v), axis=1)
print(result)

Output: [ 50 122]

This code uses np.multiply to element-wise multiply A and v, which results in a matrix where each row is the element-wise product of a row in A and vector v. The sum over axis 1 then yields the final matrix-vector multiplication result. This method is both compact and efficient.

Summary/Discussion

  • Method 1: NumPy’s einsum function. High efficiency. Good readability with knowledge of Einstein notation. Can be cryptic for beginners.
  • Method 2: NumPy’s dot function. Intuitive for those with linear algebra background. Not as versatile for higher dimensional arrays.
  • Method 3: NumPy’s matmul function. Offers clear matrix multiplication semantics. Limited to 1D and 2D arrays for input.
  • Method 4: Manual Implementation. Provides good insight into the summation process. Much less efficient and scalable compared to NumPy functions. Useful for learning purposes.
  • Method 5: NumPy’s multiply and sum methods. Simple and efficient. Loses the specific connotation of matrix-vector multiplication, which might affect readability.