linalg

A linear algebra engine written in C++ with a Python interface via pybind11. Built from scratch as a learning project covering the computational side of linear algebra — determinants, matrix inverse, and core matrix operations, with an emphasis on understanding both the naive mathematical definitions and optimized implementations.

---

What's inside

Feature	Algorithm	Complexity
Determinant	Cofactor expansion (naive)	O(n!)
Determinant	Gaussian elimination	O(n³)
Inverse	Gauss-Jordan elimination	O(n³)
Matrix multiply	Tiled / blocked multiplication	O(n³), cache-friendly
Add / subtract	Element-wise	O(n²)
Scalar multiply	Element-wise	O(n²)
Transpose	Index swap	O(n²)

---

Project structure

linalg/
├── matrix.h          # core engine — all algorithms and the M class
├── matrix.cpp        # C++ entrypoint with test suite
├── bindings.cpp      # pybind11 bindings
├── setup.py          # build configuration
├── test.py    # pytest test suite for the Python API
└── requirements.txt  # Python dependencies

---

Building

Prerequisites

• C++17 compiler (clang++ or g++)
• Python 3.x
• pybind11

Setup

# create and activate a virtual environment
python3 -m venv env
source env/bin/activate

# install dependencies
pip install pybind11 pytest

# build the C++ test binary
g++ -O3 -std=c++17 matrix.cpp -o matrix

# build the Python extension
python setup.py build_ext --inplace

---

Running tests

C++ tests

./matrix

Python tests

pytest test_linalg.py -v

---

Usage (Python)

import linalg

# create a matrix
m = linalg.M([[1, 2], [3, 4]])

# determinant
m.det()          # -2.0

# submatrix determinant — det(i, j, p, q)
# i,j = col bounds, p,q = row bounds (0-indexed)
m.det(0, 1, 0, 1)

# inverse
m_inv = m.inv()

# transpose
m_t = m.T()

# arithmetic
m1 = linalg.M([[1, 2], [3, 4]])
m2 = linalg.M([[5, 6], [7, 8]])

m1 + m2        # addition
m1 - m2        # subtraction
m1 * m2        # matrix multiplication (tiled)
m1 * 2.0       # scalar multiply
2.0 * m1       # scalar multiply (left)

---

Design notes

Two determinant implementations are included intentionally — the naive cofactor expansion (deter) follows the mathematical definition directly and makes the recursive structure of the determinant visible. The Gaussian elimination version (gauss_det) is what the engine actually uses, running in O(n³) with partial pivoting for numerical stability.

Tiled matrix multiplication reorders the naive O(n³) loop to keep small blocks of all three matrices hot in L1 cache simultaneously, reducing cache misses on large matrices. Block size is set to 64 by default.

Gauss-Jordan inverse augments the matrix as [A | I] and runs forward and backward elimination until the left side becomes the identity, at which point the right side holds A⁻¹. Partial pivoting is applied and singular matrices throw a runtime_error.

---

AI use disclosure

This project was built as a personal learning exercise in computational linear algebra. All core algorithmic logic and architecture decisions were made by the author. Minor bug fixing assistance (type mismatches, syntax issues) was provided by Claude Sonnet 4.6. The full test suite was written with assistance from the same model. The model was used as a debugging and review tool, not as a code generator.

---

What's next

• Systems of equations (Ax = b via back substitution)
• Eigenvalues and eigenvectors
• Element accessor (tolist() / operator[]) for cleaner Python testing
• Flat memory layout (vector<double> with manual indexing) for better cache performance