Linear Algebra API

Linear Algebra API#

The panther.linalg module provides randomized linear algebra operations for efficient matrix decompositions.

Core Functions#

Linear algebra operations for randomized matrix decompositions and sketching.

panther.linalg.cqrrpt(M, gamma=1.25)[source]#

Performs CholeskyQR with randomization and pivoting (CQRRPT) for tall matrices.

This function implements a numerically stable QR decomposition for tall matrices using Cholesky factorization, randomization, and column pivoting. It is particularly useful for large-scale problems where standard QR decomposition may be computationally expensive or numerically unstable.

Parameters:

  • M (torch.Tensor) – The input tall matrix of shape (m, n) with m >= n.

  • gamma (float, optional) – Oversampling parameter to improve numerical stability. Default is 1.25.

Returns:

  • Q (torch.Tensor): Orthonormal matrix of shape (m, n).

  • R (torch.Tensor): Upper triangular matrix of shape (n, n).

  • P (torch.Tensor): Permutation matrix or indices representing column pivoting.

Return type:

Tuple[torch.Tensor, torch.Tensor, torch.Tensor]

Example

>>> import torch
>>> from panther.linalg import cqrrpt
>>> # Create a random tall matrix
>>> m, n = 100, 20
>>> M = torch.randn(m, n)
>>> # Perform CQRRPT
>>> Q, R, P = cqrrpt(M, gamma=1.25)
>>> # Q is (m, n), R is (n, n), P is (n,)
>>> # Verify the decomposition: Q @ R should approximate M[:, P]
>>> M_permuted = M[:, P]
>>> reconstruction = Q @ R
>>> print("Reconstruction error:", torch.norm(reconstruction - M_permuted))
>>> # Q should be orthonormal: Q.T @ Q ≈ I
>>> print("Q orthogonality error:", torch.norm(Q.T @ Q - torch.eye(n)))
>>> # R should be upper triangular
>>> print("R upper triangular:", torch.allclose(R, torch.triu(R)))
>>> # Optionally, check relative error
>>> rel_error = torch.norm(reconstruction - M_permuted) / torch.norm(M_permuted)
>>> print("Relative error:", rel_error.item())

Notes

  • This method is especially effective for matrices where m >> n.

  • The randomization step improves the conditioning of the matrix before Cholesky factorization.

  • Pivoting ensures numerical stability and accurate rank-revealing properties.

panther.linalg.randomized_svd(A, k, tol)[source]#

Computes a truncated randomized Singular Value Decomposition (SVD) of a matrix.

This function efficiently approximates the singular value decomposition of a given matrix A using randomized algorithms, which are particularly useful for large-scale matrices where traditional SVD is computationally expensive.

Parameters:

  • A (torch.Tensor) – The input matrix of shape (m, n) to decompose.

  • k (int) – The number of singular values and vectors to compute (rank of the approximation).

  • tol (float) – Tolerance for convergence. Smaller values yield more accurate results but may require more computation.

Returns:

  • U (torch.Tensor) – Left singular vectors of shape (m, k).

  • S (torch.Tensor) – Singular values of shape (k,).

  • V (torch.Tensor) – Right singular vectors of shape (n, k).

Examples

>>> import torch
>>> from panther.linalg import randomized_svd
>>> A = torch.randn(100, 50)
>>> U, S, V = randomized_svd(A, k=10, tol=1e-5)
>>> # Reconstruct the approximation
>>> A_approx = U @ torch.diag(S) @ V.T
>>> print(A_approx.shape)
torch.Size([100, 50])

Notes

Randomized SVD is especially useful for dimensionality reduction, principal component analysis (PCA), and latent semantic analysis (LSA) on large datasets.

Examples#

Randomized QR Decomposition with Column Pivoting

import torch
import panther as pr

# Create a matrix
A = torch.randn(1000, 500)

# Perform CQRRPT decomposition
Q, R, P = pr.linalg.cqrrpt(A, gamma=1.5)

# Q is orthogonal, R is upper triangular
print(f"Q shape: {Q.shape}")  # (1000, 500)
print(f"R shape: {R.shape}")  # (500, 500)
print(f"P shape: {P.shape}")  # (500,)

# Verify decomposition: A[:, P] ≈ Q @ R
reconstruction_error = torch.norm(A[:, P] - Q @ R)
print(f"Reconstruction error: {reconstruction_error.item()}")

Randomized SVD

import torch
import panther as pr

# Create a large matrix
A = torch.randn(2000, 1500)

# Compute top 100 singular values/vectors
U, S, V = pr.linalg.randomized_svd(A, k=100, tol=1e-6)

print(f"U shape: {U.shape}")  # (2000, 100)
print(f"S shape: {S.shape}")  # (100,)
print(f"V shape: {V.shape}")  # (1500, 100)

# Reconstruct approximation
A_approx = U @ torch.diag(S) @ V.T
approximation_error = torch.norm(A - A_approx)
print(f"Approximation error: {approximation_error.item()}")

GPU Support#

All linear algebra operations support GPU acceleration:

import torch
import panther as pr

device = torch.device('cuda')
A = torch.randn(5000, 3000, device=device)

# GPU computation
Q, R, P = pr.linalg.cqrrpt(A)

# Results are on the same device
print(f"Q device: {Q.device}")  # cuda:0

Performance Notes#

  • Matrix Size: Randomized algorithms are most beneficial for large matrices (> 1000x1000)

  • Rank: For randomized SVD, choose k based on the desired accuracy vs. speed tradeoff

  • Tolerance: Lower tolerance values in randomized SVD provide higher accuracy but require more computation

  • GPU Memory: Large matrices may require significant GPU memory. Monitor usage with torch.cuda.memory_allocated()

Theoretical Background#

The randomized algorithms implemented in Panther are based on:

  • CQRRPT: Randomized QR decomposition with column pivoting for numerical stability

  • Randomized SVD: Fast approximate SVD using random projections

  • Sketching: Dimensionality reduction techniques for large-scale linear algebra

These methods provide:

  • Speed: Much faster than deterministic algorithms for large matrices

  • Memory Efficiency: Lower memory footprint through sketching

  • Accuracy: Theoretical guarantees on approximation quality

  • Scalability: Handle matrices that don’t fit in memory