Detailed Description

Author: hacatu

Version: 0.2.0

LICENSE

This Source Code Form is subject to the terms of the Mozilla Public License, v. 2.0. If a copy of the MPL was not distributed with this file, You can obtain one at http://mozilla.org/MPL/2.0/.

DESCRIPTION

Functions for dealing with integer matricies

Definition in file matrix.h.

Go to the source code of this file.

Data Structures
struct	nut_i64_Matrix

struct	nut_u64_ModMatrix

Functions
bool	nut_i64_Matrix_init (nut_i64_Matrix *self, int64_t rows, int64_t cols)
	Allocate internal buffers for a matrix.

void	nut_i64_Matrix_copy (nut_i64_Matrix restrict dest, const nut_i64_Matrix restrict src)
	Copy the values from one matrix to another, which must be initialized.

void	nut_i64_Matrix_destroy (nut_i64_Matrix *self)
	Deallocate internal buffers for a matrix table.

void	nut_i64_Matrix_fprint (const nut_i64_Matrix restrict self, FILE file)
	Print a matrix to a given file.

bool	nut_i64_Matrix_fill_I (nut_i64_Matrix *self)
	Fill a matrix with zeros off the diagonal and ones on the diagonal The matrix must be squared.

void	nut_i64_Matrix_mul_vec (const nut_i64_Matrix *restrict self, const int64_t vec[restrict static self->cols], int64_t out[restrict static self->rows])
	Multiply a matrix by a vector, returning a vector The vectors are stored as one dimensional arrays This is a special case of matrix-matrix multiplication, since a row/column vec is simply a matrix with 1 row/column respectively.

void	nut_i64_Matrix_fill_short_pascal (nut_i64_Matrix *self)
	Fill a matrix with part of the Pascal Triangle This is mostly internally used together with `nut_i64_Matrix_invert_ltr` to get a matrix of Faulhaber polynomial coefficients to quickly sum powers of integer (see `nut_Diri_compute_Nk`).

int64_t	nut_i64_Matrix_invert_ltr (nut_i64_Matrix restrict self, nut_i64_Matrix restrict out)
	Invert a lower triangular matrix Integer matrices in general are not invertable because the integers are not a field, so this function also returns a denominator so the result can be interpreted as a rational matrix.

void	nut_i64_Matrix_fill_vandemond_vec (uint64_t x, uint64_t k, uint64_t m, int64_t out[static k+1])
	Fill a vector with increasing powers of x.

bool	nut_u64_ModMatrix_init (nut_u64_ModMatrix *self, uint64_t rows, uint64_t cols, uint64_t modulus)
	Allocate internal buffers for a matrix.

void	nut_u64_ModMatrix_copy (nut_u64_ModMatrix restrict dest, const nut_u64_ModMatrix restrict src)
	Copy the values from one matrix to another, which must be initialized.

void	nut_u64_ModMatrix_destroy (nut_u64_ModMatrix *self)
	Deallocate internal buffers for a matrix table.

void	nut_u64_ModMatrix_fprint (const nut_u64_ModMatrix restrict self, FILE file)
	Print a matrix to a given file.

bool	nut_u64_ModMatrix_fill_I (nut_u64_ModMatrix *self)
	Fill a matrix with zeros off the diagonal and ones on the diagonal The matrix must be squared.

void	nut_u64_ModMatrix_mul_vec (const nut_u64_ModMatrix *restrict self, const uint64_t vec[restrict static self->cols], uint64_t out[restrict static self->rows])
	Multiply a matrix by a vector, returning a vector The vectors are stored as one dimensional arrays This is a special case of matrix-matrix multiplication, since a row/column vec is simply a matrix with 1 row/column respectively.

void	nut_u64_ModMatrix_fill_short_pascal (nut_u64_ModMatrix *self)
	Fill a matrix with part of the Pascal Triangle This is mostly internally used together with `nut_u64_ModMatrix_invert_ltr` to get a matrix of Faulhaber polynomial coefficients to quickly sum powers of integer (see `nut_Diri_compute_Nk`).

bool	nut_u64_ModMatrix_invert_ltr (nut_u64_ModMatrix restrict self, nut_u64_ModMatrix restrict out)
	Invert a lower triangular matrix Since we are working on matrices mod some number, any integer matrix whose denominator is divisible by the modulus, even if it is not zero, will be non-invertable.

void	nut_u64_Matrix_fill_vandemond_vec (uint64_t x, uint64_t k, uint64_t m, uint64_t out[static k+1])
	Fill a vector with increasing powers of x.

Function Documentation

◆ nut_i64_Matrix_init()

bool nut_i64_Matrix_init	(	nut_i64_Matrix *	self,
		int64_t	rows,
		int64_t	cols
	)

Allocate internal buffers for a matrix.

Parameters

[in]	rows,cols	The number of rows and columns. Must not be negative. If either is zero, most operations will become no-ops. Many operations are specific to square matrices
[out]	self	matrix to initialize

Returns: true on success, false on failure (allocation failure, size overflow, negative size)

◆ nut_i64_Matrix_fprint()

void nut_i64_Matrix_fprint	(	const nut_i64_Matrix *restrict	self,
		FILE *	file
	)

Print a matrix to a given file.

Format is '[[0, 1, 2],
[3, 4, 5],
[6, 7, 8]]'

◆ nut_i64_Matrix_mul_vec()

void nut_i64_Matrix_mul_vec	(	const nut_i64_Matrix *restrict	self,
		const int64_t	vec[restrict static self->cols],
		int64_t	out[restrict static self->rows]
	)

Multiply a matrix by a vector, returning a vector The vectors are stored as one dimensional arrays This is a special case of matrix-matrix multiplication, since a row/column vec is simply a matrix with 1 row/column respectively.

The advantage is that this can interprest more things (any buffer) as a vector.

Parameters

[in]	self	The matrix to multiply the input vector by
[in]	vec	The vector to multiply. The number of cols in the matrix must match the length of this vector. If at least self->cols elements of vec are not accessible, it is undefined behavior.
[out]	out	The vector to store the result in. The number of rows in the matrix must match the length of this vector. If at least self->rows elements of out are not accessible, it is undefined behavior

◆ nut_i64_Matrix_fill_short_pascal()

void nut_i64_Matrix_fill_short_pascal ( nut_i64_Matrix * self )

Fill a matrix with part of the Pascal Triangle This is mostly internally used together with nut_i64_Matrix_invert_ltr to get a matrix of Faulhaber polynomial coefficients to quickly sum powers of integer (see nut_Diri_compute_Nk).

In particular, the ith row of the matrix will be filled by the ith row of pascal's triangle without the final 1, trimmed/zero padded as needed. The first (0th) row is a 1 followed by all zeroes, the second (1st) row is a 1, then a 2, then all zeroes, etc.

◆ nut_i64_Matrix_invert_ltr()

int64_t nut_i64_Matrix_invert_ltr	(	nut_i64_Matrix *restrict	self,
		nut_i64_Matrix *restrict	out
	)

Invert a lower triangular matrix Integer matrices in general are not invertable because the integers are not a field, so this function also returns a denominator so the result can be interpreted as a rational matrix.

This denominator may not be reduced in general. Uses gaussian elimination specialized to lower triangular matrices.

Parameters

[in]	self	The matrix to invert, which is clobbered in place. If the original matrix will still be needed, copy it beforehand
[out]	out	The matrix to store the result in

Returns: 0 if self/tmp have different sizes or are not square or self is not invertable, otherwise the denominator (all entries should be understood as numeratos)

◆ nut_i64_Matrix_fill_vandemond_vec()

void nut_i64_Matrix_fill_vandemond_vec	(	uint64_t	x,
		uint64_t	k,
		uint64_t	m,
		int64_t	out[static k+1]
	)

Fill a vector with increasing powers of x.

Parameters

[in]	x	The number to take powers of
[in]	k	The max exponent (inclusive)
[in]	m	The modulus to reduce powers by, or 0 to skip reducing
[out]	out	Buffer to store resulting vector in. The first entry will be set to xm, then xxm then xx*xm, etc

◆ nut_u64_ModMatrix_init()

bool nut_u64_ModMatrix_init	(	nut_u64_ModMatrix *	self,
		uint64_t	rows,
		uint64_t	cols,
		uint64_t	modulus
	)

Allocate internal buffers for a matrix.

Parameters

[in]	rows,cols	The number of rows and columns. If either is zero, most operations will become no-ops. Many operations are specific to square matrices
[in]	modulus	The modulus. Some operations may fail if it is not prime.
[out]	self	matrix to initialize

Returns: true on success, false on failure (allocation failure, size overflow, negative size)

◆ nut_u64_ModMatrix_fprint()

void nut_u64_ModMatrix_fprint	(	const nut_u64_ModMatrix *restrict	self,
		FILE *	file
	)

Print a matrix to a given file.

Format is '[[0, 1, 2],
[3, 4, 5],
[6, 7, 8]] mod 1000000009'

◆ nut_u64_ModMatrix_mul_vec()

void nut_u64_ModMatrix_mul_vec	(	const nut_u64_ModMatrix *restrict	self,
		const uint64_t	vec[restrict static self->cols],
		uint64_t	out[restrict static self->rows]
	)

Multiply a matrix by a vector, returning a vector The vectors are stored as one dimensional arrays This is a special case of matrix-matrix multiplication, since a row/column vec is simply a matrix with 1 row/column respectively.

The advantage is that this can interprest more things (any buffer) as a vector.

Parameters

[in]	self	The matrix to multiply the input vector by
[in]	vec	The vector to multiply. The number of cols in the matrix must match the length of this vector. If at least self->cols elements of vec are not accessible, it is undefined behavior.
[out]	out	The vector to store the result in. The number of rows in the matrix must match the length of this vector. If at least self->rows elements of out are not accessible, it is undefined behavior

◆ nut_u64_ModMatrix_fill_short_pascal()

void nut_u64_ModMatrix_fill_short_pascal ( nut_u64_ModMatrix * self )

Fill a matrix with part of the Pascal Triangle This is mostly internally used together with nut_u64_ModMatrix_invert_ltr to get a matrix of Faulhaber polynomial coefficients to quickly sum powers of integer (see nut_Diri_compute_Nk).

In particular, the ith row of the matrix will be filled by the ith row of pascal's triangle without the final 1, trimmed/zero padded as needed. The first (0th) row is a 1 followed by all zeroes, the second (1st) row is a 1, then a 2, then all zeroes, etc.

◆ nut_u64_ModMatrix_invert_ltr()

bool nut_u64_ModMatrix_invert_ltr	(	nut_u64_ModMatrix *restrict	self,
		nut_u64_ModMatrix *restrict	out
	)

Invert a lower triangular matrix Since we are working on matrices mod some number, any integer matrix whose denominator is divisible by the modulus, even if it is not zero, will be non-invertable.

Uses gaussian elimination specialized to lower triangular matrices.

Parameters

[in]	self	The matrix to invert, which is clobbered in place. If the original matrix will still be needed, copy it beforehand
[out]	out	The matrix to store the result in

Returns: false if self/tmp have different sizes or are not square or self is not invertable, otherwise true

◆ nut_u64_Matrix_fill_vandemond_vec()

void nut_u64_Matrix_fill_vandemond_vec	(	uint64_t	x,
		uint64_t	k,
		uint64_t	m,
		uint64_t	out[static k+1]
	)

Fill a vector with increasing powers of x.

Parameters

[in]	x	The number to take powers of
[in]	k	The max exponent (inclusive)
[in]	m	The modulus to reduce powers by, may not be zero
[out]	out	Buffer to store resulting vector in. The first entry will be set to xm, then xxm then xx*xm, etc

Detailed Description

LICENSE

DESCRIPTION

Data Structures

Functions

Function Documentation

◆ nut_i64_Matrix_init()

◆ nut_i64_Matrix_fprint()

◆ nut_i64_Matrix_mul_vec()

◆ nut_i64_Matrix_fill_short_pascal()

◆ nut_i64_Matrix_invert_ltr()

◆ nut_i64_Matrix_fill_vandemond_vec()

◆ nut_u64_ModMatrix_init()

◆ nut_u64_ModMatrix_fprint()

◆ nut_u64_ModMatrix_mul_vec()

◆ nut_u64_ModMatrix_fill_short_pascal()

◆ nut_u64_ModMatrix_invert_ltr()

◆ nut_u64_Matrix_fill_vandemond_vec()