gauss_elim.h File Reference

Gaussian elimination over GF(2) (from a paper by D. Parkinson and M. Wunderlich). More...

#include <inttypes.h>
#include "matrix.h"
#include "x_array_list.h"

Go to the source code of this file.

Defines
#define	_TIFA_GAUSS_ELIM_H_
Functions
void	gaussian_elim (uint32_array_list_t *relations, binary_matrix_t *const matrix)
	Gaussian elimination on a binary_matrix_t.

---

Detailed Description

Gaussian elimination over GF(2) (from a paper by D. Parkinson and M. Wunderlich).

Author:

Jerome Milan

Date:

Fri Jun 10 2011

Version:

2011-06-10

Gaussian elimination over GF(2) as presented in the paper "A compact algorithm for Gaussian elimination over GF(2) implemented on highly parallel computers" written by Dennis Parkinson and Marvin Wunderlich (Parallel Computing 1, 1984).

See also:

"A compact algorithm for Gaussian elimination over GF(2) implemented on highly parallel computers", D. Parkinson and M. Wunderlich, Parallel Computing 1, 1984, pages 65-73.

Definition in file gauss_elim.h.

---

Define Documentation

#define _TIFA_GAUSS_ELIM_H_

Standard include guard.

Definition at line 43 of file gauss_elim.h.

---

Function Documentation

void gaussian_elim	(	uint32_array_list_t *	relations,
		binary_matrix_t *const	matrix
	)

Gaussian elimination on a binary_matrix_t.

Performs a gaussian elimination on a binary_matrix_t as described in the paper "A compact algorithm for Gaussian elimination over GF(2) implemented on highly parallel computers", by D. Parkinson and M. Wunderlich (Parallel Computing 1 (1984) 65-73).

Solutions (if any) of this linear system are stored in relations where each entry is a uint32_array_t containing the indexes of the rows (from the original matrix) composing a solution. In other words, for each entry, the sum of the indexed rows (from the original matrix) is a nul binary vector.

Parameters:

[in]	matrix	A pointer to the binary_matrix_t giving the linear system to solve.
[out]	relations	A pointer to a uint32_array_list_t holding the solutions of the system, if any.