Aleph::Modular_Matrix< MatrixT > Class Template Reference

Matrix operations modulo a prime. More...

#include <modular_linalg.H>

Collaboration diagram for Aleph::Modular_Matrix< MatrixT >:

Classes
struct	skip_validation_t

Public Member Functions
	Modular_Matrix (const MatrixT &m, const uint64_t p)
	Construct a modular matrix from an existing matrix and a prime modulus.
const MatrixT &	get () const noexcept
	Get a constant reference to the underlying matrix.
uint64_t	determinant () const
	Computes the determinant of the matrix modulo p.
std::optional< Modular_Matrix< MatrixT > >	inverse () const
	Computes the inverse of the matrix modulo p.

Private Member Functions
	Modular_Matrix (MatrixT &&m, uint64_t p, skip_validation_t)

Static Private Member Functions
static uint64_t	get_val (const MatrixT &m, size_t r, size_t c)
static void	set_val (MatrixT &m, size_t r, size_t c, uint64_t v)
static void	swap_rows (MatrixT &m, size_t r1, size_t r2)

Private Attributes
MatrixT	mat
	The underlying matrix data.
uint64_t	mod
	The prime modulus defining the finite field.

Detailed Description

template<ModularMatrixBackend MatrixT>
class Aleph::Modular_Matrix< MatrixT >

Matrix operations modulo a prime.

Provides linear algebra algorithms over a finite field defined by a prime modulus. Supports various matrix backends like Array of Arrays for dense matrices or DynMatrix for sparse ones.

Thread-safety

Methods are safe for concurrent reads from multiple threads. External synchronization is required if the underlying matrix backend is being modified.

Template Parameters

MatrixT

The matrix container type. Must satisfy ModularMatrixBackend concept.

Definition at line 122 of file modular_linalg.H.

Constructor & Destructor Documentation

Modular_Matrix() [1/2]

template<ModularMatrixBackend MatrixT>

Aleph::Modular_Matrix< MatrixT >::Modular_Matrix ( const MatrixT &  m, const uint64_t  p  )

inline

Construct a modular matrix from an existing matrix and a prime modulus.

Initializes the internal matrix and ensures all elements are normalized within the range [0, p-1].

Parameters

[in]	m	Source matrix data.
[in]	p	Prime modulus.

Exceptions

std::invalid_argument

if p is not prime or if m is a ragged Array<Array>.

Definition at line 181 of file modular_linalg.H.

References ah_invalid_argument_if, Aleph::divide_and_conquer_partition_dp(), Aleph::Modular_Matrix< MatrixT >::mat, Aleph::matrix_dims(), Aleph::miller_rabin(), Aleph::Modular_Matrix< MatrixT >::mod, and Aleph::size().

Modular_Matrix() [2/2]

template<ModularMatrixBackend MatrixT>

Aleph::Modular_Matrix< MatrixT >::Modular_Matrix ( MatrixT &&  m, uint64_t  p, skip_validation_t    )

inlineprivate

Definition at line 216 of file modular_linalg.H.

Member Function Documentation

determinant()

template<ModularMatrixBackend MatrixT>

uint64_t Aleph::Modular_Matrix< MatrixT >::determinant ( ) const

inline

Computes the determinant of the matrix modulo p.

Uses Gaussian elimination to compute the determinant in O(n^3) time.

Precondition

Matrix must be non-empty and square.

Returns

The determinant of the matrix modulo p.

Postcondition

Returns determinant modulo p.

Exceptions

std::domain_error

if the matrix is not square or is empty.

Definition at line 237 of file modular_linalg.H.

References ah_domain_error_if, Aleph::divide_and_conquer_partition_dp(), Aleph::Modular_Matrix< MatrixT >::get_val(), k, Aleph::Modular_Matrix< MatrixT >::mat, Aleph::matrix_dims(), Aleph::Modular_Matrix< MatrixT >::mod, Aleph::mod_inv(), Aleph::mod_mul(), Aleph::Modular_Matrix< MatrixT >::set_val(), and Aleph::Modular_Matrix< MatrixT >::swap_rows().

Referenced by demo_modular_linalg(), TEST(), TEST(), TEST(), and TEST().

get()

template<ModularMatrixBackend MatrixT>

const MatrixT & Aleph::Modular_Matrix< MatrixT >::get ( ) const

inlinenoexcept

Get a constant reference to the underlying matrix.

Returns

Constant reference to the matrix data.

Exceptions

none

Note

Complexity: O(1).

Thread-safety: Safe for concurrent reads.

Definition at line 226 of file modular_linalg.H.

References Aleph::Modular_Matrix< MatrixT >::mat.

Referenced by demo_modular_linalg().

get_val()

template<ModularMatrixBackend MatrixT>

static uint64_t Aleph::Modular_Matrix< MatrixT >::get_val ( const MatrixT &  m, size_t  r, size_t  c  )

inlinestaticprivate

Definition at line 128 of file modular_linalg.H.

References m, and r.

Referenced by Aleph::Modular_Matrix< MatrixT >::determinant(), and Aleph::Modular_Matrix< MatrixT >::inverse().

inverse()

template<ModularMatrixBackend MatrixT>

std::optional< Modular_Matrix< MatrixT > > Aleph::Modular_Matrix< MatrixT >::inverse ( ) const

inline

Computes the inverse of the matrix modulo p.

Uses Gauss-Jordan elimination to find the inverse in O(n^3) time.

Precondition

Matrix must be non-empty and square.

Returns

A new Modular_Matrix containing the inverse, or std::nullopt if the matrix is singular (not invertible).

Postcondition

Returns inverse matrix modulo p or std::nullopt if matrix is singular (not invertible).

Exceptions

std::domain_error

if the matrix is not square or is empty.

Definition at line 301 of file modular_linalg.H.

References ah_domain_error_if, Aleph::Array< T >::append(), Aleph::divide_and_conquer_partition_dp(), Aleph::Modular_Matrix< MatrixT >::get_val(), k, Aleph::Modular_Matrix< MatrixT >::mat, Aleph::matrix_dims(), Aleph::Modular_Matrix< MatrixT >::mod, Aleph::mod_inv(), Aleph::mod_mul(), Aleph::Array< T >::reserve(), Aleph::Modular_Matrix< MatrixT >::set_val(), and Aleph::Modular_Matrix< MatrixT >::swap_rows().

Referenced by demo_modular_linalg(), TEST(), TEST(), TEST(), and TEST().

set_val()

template<ModularMatrixBackend MatrixT>

static void Aleph::Modular_Matrix< MatrixT >::set_val ( MatrixT &  m, size_t  r, size_t  c, uint64_t  v  )

inlinestaticprivate

Definition at line 136 of file modular_linalg.H.

References Aleph::divide_and_conquer_partition_dp(), m, and r.

Referenced by Aleph::Modular_Matrix< MatrixT >::determinant(), Aleph::Modular_Matrix< MatrixT >::inverse(), and Aleph::Modular_Matrix< MatrixT >::swap_rows().

swap_rows()

template<ModularMatrixBackend MatrixT>

static void Aleph::Modular_Matrix< MatrixT >::swap_rows ( MatrixT &  m, size_t  r1, size_t  r2  )

inlinestaticprivate

Definition at line 149 of file modular_linalg.H.

References Aleph::divide_and_conquer_partition_dp(), m, and Aleph::Modular_Matrix< MatrixT >::set_val().

Referenced by Aleph::Modular_Matrix< MatrixT >::determinant(), and Aleph::Modular_Matrix< MatrixT >::inverse().

Member Data Documentation

mat

template<ModularMatrixBackend MatrixT>

MatrixT Aleph::Modular_Matrix< MatrixT >::mat

private

The underlying matrix data.

Definition at line 124 of file modular_linalg.H.

Referenced by Aleph::Modular_Matrix< MatrixT >::Modular_Matrix(), Aleph::Modular_Matrix< MatrixT >::determinant(), Aleph::Modular_Matrix< MatrixT >::get(), and Aleph::Modular_Matrix< MatrixT >::inverse().

mod

template<ModularMatrixBackend MatrixT>

uint64_t Aleph::Modular_Matrix< MatrixT >::mod

private

The prime modulus defining the finite field.

Definition at line 125 of file modular_linalg.H.

Referenced by Aleph::Modular_Matrix< MatrixT >::Modular_Matrix(), Aleph::Modular_Matrix< MatrixT >::determinant(), and Aleph::Modular_Matrix< MatrixT >::inverse().

---

The documentation for this class was generated from the following file:

• modular_linalg.H