xref: /dports/math/lidia/lidia-2.3.0+latte-patches-2014-10-04/doc/bigint_matrix.tex

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%%  bigint_matrix.tex       LiDIA documentation
%%
%%  This file contains the documentation of the class bigint_matrix
%%
%%  Copyright   (c)   1995   by  LiDIA-Group
%%
%%  Authors: Patrick Theobald
%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\NAME

\CLASS{bigint_matrix} \dotfill Linear algebra over $\bbfZ$


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\ABSTRACT

\code{bigint_matrix} is a class for doing linear algebra over the ring of rational integers.
This class may either be used for representing a modul, which is generated by the columns of the
matrix
\begin{displaymath}
  A = (a_{i,j}) \in \bbfZ^{m\times n} \enspace,\quad 0 \leq i < m,\, 0 \leq j < n
\end{displaymath}
or for representing a homomorphism by its matrix.  In the first case, the class supports for
example computing bases, hermite normal form, smith normal form etc., in the second case it may
be used for computing the determinant, the characteristic polynomial, the image, the kernel
etc.~of the homomorphism.

According to the template introduction (see page \pageref{template_introduction2}) the class
\code{bigint_matrix} is derived from \code{math_matrix< bigint >}.  So you can apply all the
functions and operators of class \code{base_matrix< bigint >} and \code{math_matrix< bigint >}
to instances of type \code{bigint_matrix}.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\DESCRIPTION

A variable of type \code{bigint_matrix} contains the same components as a \code{math_matrix<
  bigint >}.

As usually in the following descriptions we use \code{$A$.rows} to label the number of rows and
\code{$A$.columns} to label the number of columns of matrix $A$.

For some computations modular arithmetic is used, for which we use an external table of prime
numbers.  By default, this table is taken out of the file
\path{LIDIA_INSTALL_DIR/lib/LiDIA/LIDIA_PRIMES}, where \path{LIDIA_INSTALL_DIR} denotes the
directory, where \LiDIA was installed by the installation procedure.  For efficiency reasons, we
assume at first, that 300 prime numbers are sufficient.  If this is not the case, the number of
used prime numbers is successively doubled.

If you want to use some other file location for the file containing the prime numbers, you have
to set the environment variable \code{LIDIA_PRIMES_NAME} to point to this location.  Depending
on your architecture quite some gain in running time may be achieved by using lists of larger
prime numbers, e.g.~if you have a 64 bit CPU using our list of 26 bit primes (optimized for
SPARC V7/V8 architectures) is just a convenient though slow way to get our library to work.  If
you do computations with very large numbers, you might consider to start with a larger buffer
for the prime numbers by setting the environment variable \code{LIDIA_PRIMES_SIZE} to some
larger number, e.g.~to 6000.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\CONS

If $a \leq 0$ or $b \leq 0$ or $v = \code{NULL}$ in one of the following constructors the \LEH
will be invoked.

\begin{fcode}{ct}{bigint_matrix}{}
  constructs a $1 \times 1$ matrix initialized with zero.
\end{fcode}

\begin{fcode}{ct}{bigint_matrix}{lidia_size_t $a$, lidia_size_t $b$}
  constructs an $a \times b$ matrix initialized with zero.
\end{fcode}

\begin{fcode}{ct}{bigint_matrix}{lidia_size_t $a$, lidia_size_t $b$, const bigint ** $v$}
  constructs an $a \times b$ matrix initialized with the values of the 2-dimensional array $v$.
  The behaviour of this constructor is undefined if the array $v$ has less than $a$ rows or less
  than $b$ columns.
\end{fcode}

\begin{fcode}{ct}{bigint_matrix}{const base_matrix< bigint > & $A$}
  constructs a copy of matrix $A$.
\end{fcode}

\begin{fcode}{dt}{~bigint_matrix}{}
\end{fcode}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\ARTH

In addition to the arithmetical functions and operators of class \code{math_matrix< T >} you can
use the following operators and function:

The operators \code{bigint_matrix % bigint} and \code{bigint_matrix %= bigint} reduce
componentwise each entry of the given matrix modulo the given \code{bigint}.

To avoid copying this operator also exist as function:

\begin{fcode}{void}{remainder}{bigint_matrix & $A$, const bigint_matrix & $B$, const bigint & $e$}
  Let $r = \code{$B$.rows}$ and $c = \code{$B$.columns}$.
  \begin{displaymath}
    \begin{pmatrix}
      a_{0,0} & \dots & a_{0,c-1}\\
      \vdots & \ddots & \vdots \\
      a_{r-1,0} & \dots & a_{r-1,c-1}
    \end{pmatrix} \assign
    \begin{pmatrix}
      b_{0,0} \bmod e & \dots & b_{0,c'-1} \bmod e\\
      \vdots & \ddots & \vdots \\
      b_{r-1,0} \bmod e & \dots & b_{r'-1,c'-1} \bmod e
    \end{pmatrix}\enspace.
  \end{displaymath}
  As modulo operation on $\bbfZ$ we use the best remainder function for integers.
\end{fcode}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\COMP

Let $A$ be an variable of type \code{bigint_matrix}.

\begin{cfcode}{bool}{$A$.is_column_zero}{lidia_size_t $i$}
\end{cfcode}

\begin{fcode}{bool}{is_column_zero}{const bigint_matrix & $A$, lidia_size_t $i$}
  returns \TRUE if all entries of column $i$ of matrix $A$ are zero, \FALSE otherwise.
\end{fcode}

\begin{cfcode}{bool}{$A$.is_row_zero}{lidia_size_t $i$}
\end{cfcode}

\begin{fcode}{bool}{is_row_zero}{const bigint_matrix & $A$, lidia_size_t $i$}
  returns \TRUE if all entries of row $i$ of matrix $A$ are zero, \FALSE otherwise.
\end{fcode}

\begin{cfcode}{bool}{$A$.is_matrix_zero}{}
\end{cfcode}

\begin{fcode}{bool}{is_matrix_zero}{const bigint_matrix & $A$}
  returns \TRUE if all entries of matrix $A$ are zero, and \FALSE otherwise.
\end{fcode}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\STITLE{Norms and Bounds}

\begin{cfcode}{bigint}{$A$.max}{}
\end{cfcode}

\begin{fcode}{bigint}{max}{const bigint_matrix & $A$}
  returns the maximum of all components of matrix $A$.
\end{fcode}

\begin{cfcode}{void}{$A$.max}{bigint & $x$}
  $x \assign \code{max($A$)}$.
\end{cfcode}

\begin{cfcode}{bigint}{$A$.max_abs}{}
\end{cfcode}

\begin{fcode}{bigint}{max_abs}{const bigint_matrix & $A$}
  returns the maximum of the absolute values of all components of matrix $A$.
\end{fcode}

\begin{cfcode}{void}{$A$.max_abs}{bigint & $x$}
  $x \assign \code{max_abs($A$)}$
\end{cfcode}

\begin{cfcode}{bigint}{$A$.max_pos}{lidia_size_t & $x$, lidia_size_t & $y$}
\end{cfcode}

\begin{fcode}{bigint}{max_pos}{const bigint_matrix & $A$, lidia_size_t & $x$, lidia_size_t & $y$}
  returns the element $a_{x,y}$ which is the maximum of all components of matrix $A$.
\end{fcode}

\begin{cfcode}{void}{$A$.max_pos}{bigint & $m$, lidia_size_t & $x$, lidia_size_t & $y$}
  $m \assign \code{max_pos($A$, $x$, $y$)}$.
\end{cfcode}

\begin{cfcode}{bigint}{$A$.max_abs_pos}{lidia_size_t & $x$, lidia_size_t & $y$}
\end{cfcode}

\begin{fcode}{bigint}{max_abs_pos}{const bigint_matrix & $A$, lidia_size_t & $x$, lidia_size_t & $y$}
  returns the element $a_{x,y}$ which is the maximum of the absolute values of all components of
  matrix $A$.
\end{fcode}

\begin{cfcode}{void}{$A$.max_abs_pos}{bigint & $m$, lidia_size_t & $x$, lidia_size_t & $y$}
  $m \assign \code{max_abs_pos($A$, $x$, $y$)}$
\end{cfcode}

\begin{cfcode}{bigint}{$A$.min}{}
\end{cfcode}

\begin{fcode}{bigint}{min}{const bigint_matrix & $A$}
  returns the minimum of all components of $A$.
\end{fcode}

\begin{cfcode}{void}{$A$.min}{bigint & $x$}
  $x \assign \code{min($A$)}$
\end{cfcode}

\begin{cfcode}{bigint}{$A$.min_abs}{}
\end{cfcode}

\begin{fcode}{bigint}{min_abs}{const bigint_matrix & $A$}
  returns the minimum of the absolute values of all components of matrix $A$.
\end{fcode}

\begin{cfcode}{void}{$A$.min_abs}{bigint & $x$}
  $x \assign \code{min_abs($A$)}$
\end{cfcode}

\begin{cfcode}{bigint}{$A$.min_pos}{lidia_size_t & $x$, lidia_size_t & $y$}
\end{cfcode}

\begin{fcode}{bigint}{min_pos}{const bigint_matrix & $A$, lidia_size_t & $x$, lidia_size_t & $y$}
  returns the element $a_{x,y}$ which is the minimum of all components of $A$.
\end{fcode}

\begin{cfcode}{void}{$A$.min_pos}{bigint & $m$, lidia_size_t & $x$, lidia_size_t & $y$}
  $m \assign \code{min_pos($A$, $x$, $y$)}$
\end{cfcode}

\begin{cfcode}{bigint}{$A$.min_abs_pos}{lidia_size_t & $x$, lidia_size_t & $y$}
\end{cfcode}

\begin{fcode}{bigint}{min_abs_pos}{const bigint_matrix & $A$, lidia_size_t & $x$, lidia_size_t & $y$}
  returns the element $a_{x,y}$ which is the minimum of the absolute values of all components of
  matrix $A$.
\end{fcode}

\begin{cfcode}{void}{$A$.min_abs_pos}{bigint & $x$, lidia_size_t & $x$, lidia_size_t & $y$}
  $x \assign \code{min_abs_pos($A$, $x$, $y$)}$
\end{cfcode}

\begin{cfcode}{bigint}{$A$.hadamard}{}
\end{cfcode}

\begin{fcode}{bigint}{hadamard}{const bigint_matrix & $A$}
  returns the Hadamard bound of $A$.
\end{fcode}

\begin{cfcode}{void}{$A$.hadamard}{bigint & $x$}
  $x \assign \code{hadamard($A$)}$
\end{cfcode}

\begin{fcode}{void}{$A$.row_norm}{bigint & $x$, lidia_size_t $i$, long $j$ = 2}
  sets $x \assign \sum_{l=0}^{\code{$A$.columns}-1} |a_{i,l}^j|$.  If $0 \leq i < \code{$A$.rows}$
  doesn't hold, the \LEH will be invoked.
\end{fcode}

\begin{fcode}{bigint}{$A$.row_norm}{lidia_size_t $i$, long j = 2}
\end{fcode}

\begin{fcode}{bigint}{row_norm}{const bigint_matrix & $A$, lidia_size_t $i$, long $j$ = 2}
  returns $\sum_{l=0}^{\code{$A$.columns}-1} |a_{i,l}^j|$.  If not $0 \leq i < \code{$A$.rows}$
  the \LEH will be invoked.
\end{fcode}

\begin{fcode}{void}{$A$.column_norm}{bigint & $x$, lidia_size_t $i$, long $j$ = 2}
  sets $x \assign \sum_{l=0}^{\code{$A$.rows}-1} |a_{l,i}^j|$.  If not $0 \leq i <
  \code{$A$.columns}$ the \LEH will be invoked.
\end{fcode}

\begin{fcode}{bigint}{$A$.column_norm}{lidia_size_t $i$, long $j$ = 2}
\end{fcode}

\begin{fcode}{bigint}{column_norm}{const bigint_matrix & $A$, lidia_size_t $i$, long $j$ = 2}
  returns $\sum_{l=0}^{\code{$A$.rows}-1} |a_l,i^j|$.  If not $0 \leq i < \code{$A$.columns}$
  the \LEH will be invoked.
\end{fcode}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\STITLE{Randomize}

\begin{fcode}{void}{$A$.randomize}{const bigint & $b$}
  fills matrix $A$ with random values between $0$ and $b$.  The dimensions of matrix $A$ remain
  unchanged.
\end{fcode}

\begin{fcode}{void}{$A$.randomize_with_det}{const bigint & $b$, const bigint & $\mathit{DET}$}
  generates a random matrix $A$ with determinant $\mathit{DET}$.  Internally this function
  creates two triangular matrices with values between $0$ and $b$.  One of these matrices has
  the determinant $1$ and the other determinant $\mathit{DET}$.  So the product of these
  matrices is the wanted matrix $A$.  If matrix $A$ is not quadratic, the \LEH will be invoked.
\end{fcode}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\STITLE{Linear Algebra}

If the dimensions of the arguments in the following functions don't satisfy the usual
restrictions known from linear algebra, the \LEH will be invoked.  Some of these are marked by
(I).  These functions are interface functions to select the algorithm, which is the fastest one
on big, dense matrices.  Depending on your application, you might want to choose some other
algorithm from the list of algorithms described in the next section.

\begin{fcode}{void}{$A$.adj}{const bigint_matrix & $B$}
\end{fcode}

\begin{fcode}{bigint_matrix}{adj}{const bigint_matrix & $B$}
  stores the adjoint matrix of $B$ to $A$.
\end{fcode}

\begin{cfcode}{void}{$A$.charpoly}{base_vector< bigint > & $v$}
\end{cfcode}

\begin{fcode}{void}{charpoly}{base_vector< bigint > & $v$, const bigint_matrix & $A$}
  stores the coefficients of the characteristic polynomial of $A$ to $v$, where $v[i]$ contains
  the coefficient of $x^i$ (see \cite{Mueller_Thesis:1994}).  Note that the size of vector $v$
  will be adapted if necessary.
\end{fcode}

\begin{cfcode}{bigint *}{$A$.charpoly}{}
\end{cfcode}

\begin{fcode}{bigint *}{charpoly}{const bigint_matrix & $A$}
  returns an array $v$ of coefficients of the characteristic polynomial of $A$, where $v[i]$
  contains the coefficient of $x^i$ (see \cite{Mueller_Thesis:1994}).
\end{fcode}

\begin{cfcode}{bigint}{$A$.det}{}
\end{cfcode}

\begin{fcode}{bigint}{det}{const bigint_matrix & $A$}
  returns the determinant of matrix $A$.
\end{fcode}

\begin{cfcode}{void}{$A$.det}{x}
  $x \assign \code{det($A$)}$.
\end{cfcode}

\begin{fcode}{void}{$A$.hnf}{}
  transforms $A$ into hermite normal form. (I)
\end{fcode}

\begin{fcode}{bigint_matrix}{hnf}{const bigint_matrix & $A$}
  returns the hermite normal form of $A$. (I)
\end{fcode}

\begin{fcode}{void}{$A$.hnf}{bigint_matrix & $T$}
  transforms $A$ in hermite normal form and sets $T$ to the corresponding transformation matrix.
  That means: $A \cdot T = \HNF(A)$ (I).
\end{fcode}

\begin{fcode}{bigint_matrix}{hnf}{const bigint_matrix & $A$, bigint_matrix & $T$}
  returns the hermite normal form of $A$ and sets $T$ to the corresponding transformation
  matrix.  That means: $A \cdot T = \HNF(A)$ (I).
\end{fcode}

\begin{fcode}{void}{$A$.image}{const bigint_matrix & $B$}
  stores a base of the image of the homomorphism defined by $B$ to $A$.  That means, the columns
  of matrix $A$ form a generating system of this image.
\end{fcode}

\begin{fcode}{bigint_matrix}{image}{const bigint_matrix & $B$}
  returns a base of the image of the homomorphism defined by $B$.
\end{fcode}

\begin{fcode}{void}{$A$.invimage}{const bigint_matrix & $B$, const bigint * $v$}
  stores the solutions of the linear equation system $B \cdot x = v$ to matrix $A$.  The last
  column of matrix $A$ is a solution $x$ of the system and the other columns form a generating
  system of the kernel of the homomorphism corresponding to matrix $B$.  If there is no
  solution, matrix $A$ has only one column of zeros.  If no memory is allocated for array $v$,
  the \LEH will be invoked.  The behaviour of this function is undefined if $v$ has less than
  \code{$B$.rows} elements.
\end{fcode}

\begin{fcode}{bigint_matrix}{invimage}{const bigint_matrix & $B$, const bigint * $v$}
  returns a \code{bigint_matrix} $A$ with the following properties: The last column of matrix
  $A$ is a solution $x$ of the system $B \cdot x = v$ and the other columns form a generating
  system of the kernel of the homomorphism corresponding to matrix $B$.  If there is no
  solution, matrix $A$ has only one column of zeros.  If no memory is allocated for array $v$,
  the \LEH will be invoked.  The behaviour of this function is undefined if $v$ has less than
  \code{$B$.rows} elements.
\end{fcode}

\begin{fcode}{void}{$A$.invimage}{const bigint_matrix & $B$, const math_vector< bigint > & $v$}
  stores the solutions of the linear equation $B \cdot x = v$ to matrix $A$.  The last column of
  matrix $A$ is a solution $x$ of the system and the other columns form a generating system of
  the kernel of the homomorphism corresponding to matrix $B$.  If there is no solution, matrix
  $A$ has only one column of zeros.  If $\code{$v$.size} \neq \code{$B$.rows}$, the \LEH will be
  invoked.
\end{fcode}

\begin{fcode}{bigint_matrix}{invimage}{const bigint_matrix & $B$, const math_vector< bigint > & $v$}
  returns a \code{bigint_matrix} $A$ with the following properties: The last column of matrix
  $A$ is a solution $x$ of the system $B \cdot x = v$ and the other columns form a generating
  system of the kernel of the homomorphism corresponding to matrix $B$.  If there is no
  solution, matrix $A$ has only one column of zeros.  If $\code{$v$.size} \neq \code{$B$.rows}$,
  the \LEH will be invoked.
\end{fcode}

\begin{fcode}{void}{$A$.kernel}{const bigint_matrix & $B$}
  stores a basis of the kernel of the homomorphism defined by matrix $B$ to $A$ (see
  \cite{Mueller_Thesis:1994}), i.e. the columns of the matrix A form a generating system of the
  kernel (I).
\end{fcode}

\begin{fcode}{bigint_matrix}{kernel}{const bigint_matrix & $B$}
  stores a basis of the kernel of the homomorphism defined by matrix $B$ to $A$ (see
  \cite{Mueller_Thesis:1994}), i.e. the columns of the matrix A form a generating system of the
  kernel (I).
\end{fcode}

\begin{cfcode}{bigint}{$A$.latticedet}{}
\end{cfcode}

\begin{fcode}{bigint}{latticedet}{const bigint_matrix & $A$}
  returns a positive multiple of the determinant of the lattice generated by the columns of $A$
  (see \cite{Duellmann_Thesis:1991}) (I).
\end{fcode}

\begin{cfcode}{void}{$A$.latticedet}{bigint & $x$}
  $x \assign \code{latticedet($A$)}$ (I).
\end{cfcode}

\begin{cfcode}{lidia_size_t *}{$A$.lininc}{}
\end{cfcode}

\begin{fcode}{lidia_size_t *}{lininc}{const bigint_matrix & $A$}
  returns an array of type \code{lidia_size_t} with the rank of $A$ (at position zero) followed
  by the indices of the linearly independent columns of $A$.
\end{fcode}

\begin{cfcode}{void}{$A$.lininc}{base_vector< lidia_size_t > & $v$}
\end{cfcode}

\begin{fcode}{void}{lininc}{base_vector< lidia_size_t > & $v$, const bigint_matrix & $A$}
  stores the rank of $A$ (at position zero) in \code{base_vector} $v$ followed by the indices of
  the linearly independent columns of $A$.  Note that the size of vector $v$ will be adapted if
  necessary.
\end{fcode}

\begin{cfcode}{lidia_size_t *}{$A$.lininr}{}
\end{cfcode}

\begin{fcode}{lidia_size_t *}{lininr}{const bigint_matrix & $A$}
  returns an array of type \code{lidia_size_t} with the rank of $A$ (at position zero) followed
  by the indices of the linearly independent rows of $A$ (see \cite{Mueller_Thesis:1994}).
\end{fcode}

\begin{cfcode}{void}{$A$.lininr}{base_matrix< lidia_size_t > & $v$}
\end{cfcode}

\begin{fcode}{void}{lininr}{base_matrix< lidia_size_t> & $v$, const bigint_matrix & $A$}
  stores the rank of $A$ (at position zero) in \code{base_vector} $v$ followed by the indices of
  the linearly independent rows of $A$.  Note that the size of vector $v$ will be adapted if
  necessary.
\end{fcode}

\begin{cfcode}{lidia_size_t}{$A$.rank}{}
\end{cfcode}

\begin{fcode}{lidia_size_t}{rank}{const bigint_matrix & $A$}
  returns the rank of matrix $A$ (see \cite{Mueller_Thesis:1994}).
\end{fcode}

\begin{fcode}{void}{$A$.reginvimage}{const bigint_matrix & $B$, const bigint_matrix & $C$}
  solves the equation systems $B \cdot X = C$ in the following sense:

  The function calculates \code{bigint} multipliers $g_0, \dots, g_{m-1}$, where $m =
  \code{$C$.columns}$ and a matrix $X$, such that
  \begin{displaymath}
    B \cdot X = C \cdot \begin{pmatrix}
      g_0 & \dots & 0 \\
      \vdots & \ddots & \vdots \\
      0& \dots & g_{m-1}
    \end{pmatrix}
  \end{displaymath}
  and sets the matrix
  \begin{displaymath}
    A \assign \begin{pmatrix}
      X \\
      g_0 \dots g_{m-1}
    \end{pmatrix}
  \end{displaymath}
  if $B$ is regular.  Otherwise the \LEH will be invoked.
\end{fcode}

\begin{fcode}{bigint_matrix}{reginvimage}{const bigint_matrix & $B$, const bigint_matrix & $C$}
  solves the equation systems $B \cdot X = C$ in the following sense:

  The function calculates \code{bigint} multipliers $g_0$, \dots, $g_{m-1}$, where $m =
  \code{$C$.columns}$ and a matrix $X$, such that
  \begin{displaymath}
    B \cdot X = C \cdot \begin{pmatrix}
      g_0 & \dots & 0 \\
      \vdots & \ddots & \vdots \\
      0& \dots & g_{m-1}
    \end{pmatrix}
  \end{displaymath}
  and returns the matrix
  \begin{displaymath}
    \begin{pmatrix}
      X \\
      g_0 \dots g_{m-1}
    \end{pmatrix}
  \end{displaymath}
  if $B$ is regular.  Otherwise the \LEH will be invoked.
\end{fcode}

\begin{fcode}{void}{$A$.solve}{const bigint_matrix & $B$, const bigint * $v$}
  stores the solutions of the linear equation $B \cdot x = v$ to matrix $A$.  The last column of
  matrix $A$ is a solution $x$ of the system and the other columns form a generating system of
  the kernel of the homomorphism corresponding to matrix $B$.  If there is no solution, matrix
  $A$ has only one column of zeros.  If no memory is allocated for the array $v$, the \LEH will
  be invoked.  The behaviour of this function is undefined if $v$ has less than \code{$B$.rows}
  elements.
\end{fcode}

\begin{fcode}{bigint_matrix}{solve}{const bigint_matrix & $B$, const bigint * $v$}
  returns a \code{bigint_matrix} $A$ with the following properties: The last column of matrix
  $A$ is a solution $x$ of the system $B \cdot x = v$ and the other columns form a generating
  system of the kernel of the homomorphism corresponding to matrix $B$.  If there is no
  solution, matrix $A$ has only one column of zeros.  If no memory is allocated for the array
  $v$, the \LEH will be invoked.  The behaviour of this function is undefined if $v$ has less
  than \code{$B$.rows} elements.
\end{fcode}

\begin{fcode}{void}{$A$.solve}{const bigint_matrix & $B$, const math_vector< bigint > & $v$}
  stores the solutions of the linear equation $B \cdot x = v$ to matrix $A$.  The last column of
  matrix $A$ is a solution $x$ of the system and the other columns form a generating system of
  the kernel of the homomorphism corresponding to matrix $B$.  If there is no solution, matrix
  $A$ has only one column of zeros.  If $\code{$v$.size} \neq \code{$B$.rows}$, the \LEH will be
  invoked.
\end{fcode}

\begin{fcode}{bigint_matrix}{solve}{const bigint_matrix & $B$, const math_vector< bigint > & $v$}
  returns a \code{bigint_matrix} $A$ with the following properties: The last column of matrix
  $A$ is a solution $x$ of the system $B \cdot x = v$ and the other columns form a generating
  system of the kernel of the homomorphism corresponding to matrix $B$.  If there is no
  solution, matrix $A$ has only one column of zeros.  If $\code{$v$.size} \neq \code{$B$.rows}$,
  the \LEH will be invoked.
\end{fcode}

\begin{fcode}{void}{$A$.snf}{}
  transforms $A$ to Smith Normal Form (I).
\end{fcode}

\begin{fcode}{bigint_matrix}{snf}{const bigint_matrix & $A$}
  returns the Smith Normal Form of $A$(I).
\end{fcode}

\begin{fcode}{void}{$A$.snf}{bigint_matrix & $B$, bigint_matrix & $C$}
  transforms $A$ in Smith Normal Form and sets $B$, $C$ to the corresponding transformation
  matrices with $\SNF(A) = B \cdot A \cdot C$ (I).
\end{fcode}

\begin{fcode}{bigint_matrix}{snf}{const bigint_matrix & $A$, bigint_matrix & $B$, bigint_matrix & $C$}
  returns the Smith Normal Form of $A$ and sets $B$, $C$ to the corresponding transformation
  matrices with $\SNF(A) = B \cdot A \cdot C$ (I).
\end{fcode}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\STITLE{Special functions}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\SSTITLE{Multiple of the lattice determinant}

\begin{enumerate}
\item Method:

  \begin{cfcode}{bigint}{$A$.latticedet1}{}
  \end{cfcode}
  \begin{fcode}{bigint}{latticedet1}{const bigint_matrix & $A$}
    returns a positive multiple of the determinant of the lattice generated by the columns of $A$
    (see \cite{Duellmann_Thesis:1991}).
  \end{fcode}

  \begin{cfcode}{void}{$A$.latticedet1}{bigint & $x$}
    $x \assign \code{latticedet1($A$)}$.
  \end{cfcode}

\item Method:

  \begin{cfcode}{bigint}{$A$.latticedet2}{}
  \end{cfcode}
  \begin{fcode}{bigint}{latticedet2}{const bigint_matrix & $A$}
    returns a positive multiple of the determinant of the lattice generated by the columns of
    $A$.  First this functions computes two regular submatrices with full rank.  Then it
    computes the determinants $\mathit{DET}_1$ and $\mathit{DET}_2$ of these matrices.  Finally
    it returns the greates common divisor of $\mathit{DET}_1$ and $\mathit{DET}_2$.
  \end{fcode}

  \begin{cfcode}{void}{$A$.latticedet2}{bigint & $x$}
    $x \assign \code{latticedet2($A$)}$
  \end{cfcode}
\item Method:

  \begin{cfcode}{bigint}{$A$.latticedet3}{}
  \end{cfcode}

  \begin{fcode}{bigint}{latticedet3}{const bigint_matrix & $A$}
    returns a positive multiple of the determinant of the lattice generated by the columns of
    $A$.  In the first step the columns of matrix $A$ are sorted by the euclidian norm.  Next it
    computes a regular submatrix with full rank generated by columns with norm as small as
    possible.  Finally it returns the determinant of this builded matrix.
  \end{fcode}

  \begin{cfcode}{void}{$A$.latticedet3}{bigint & $x$}
    $x \assign \code{latticedet3($A$)}$
  \end{cfcode}
\end{enumerate}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\SSTITLE{Kernel}

\begin{enumerate}
\item Method:

  \begin{fcode}{void}{$A$.kernel1}{const bigint_matrix & $B$}
    stores a basis of the kernel of the homomorphism generated by matrix $B$ to $A$.
  \end{fcode}

  \begin{fcode}{bigint_matrix}{kernel1}{const bigint_matrix & $B$}
    returns a matrix where the columns form a base of the kernel of the homomorphism generated
    by matrix $B$.
  \end{fcode}
  The underlying algorithm of these two functions is described in \cite{Mueller_Thesis:1994}.

\item Method:

  \begin{fcode}{void}{$A$.kernel2}{const bigint_matrix & $B$}
    stores a basis of the kernel of the homomorphism with matrix $B$ to $A$.
  \end{fcode}

  \begin{fcode}{bigint_matrix}{kernel2}{const bigint_matrix & $B$}
    returns a matrix where the columns form a base of the kernel of the homomorphism generated
    by matrix $B$.
  \end{fcode}

  The underlying algorithm of these two functions works as follow:

  In a first step the algorithm computes the Hermite Normal Form of matrix $B$ and the
  corresponding transformation matrix $T\!R$ by using \code{B.hnf_havas()} (Description of this
  algorithm follows later.) Then it counts the number of leading zero columns in the normal
  form, say $l$ is this number.  Finally the leading $l$ columns of the matrix $T\!R$ build the
  searched basis.
\end{enumerate}
The differences in the results of these functions are that on the one hand \code{kernel1}
usually creates a basis with smaller entries than \code{kernel2} but on the other hand the
kernel2 functions are faster.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\SSTITLE{Hermite Normal Form}

The following functions transform the given matrix in Hermite Normal Form (HNF).  A matrix $A$
in HNF is an upper triangular matrix with:
\begin{displaymath}
  a_{i, \code{$A$.columns}-\code{$A$.rows}+i} > a_{i,j}\geq 0 \quad \forall j >
  (\code{$A$.columns}-\code{$A$.rows}+i)
\end{displaymath}
In these functions we assume that for the given matrices the rank is equal to the number of
rows.  If this condition is not satisfied, the functions using modular methods for the
computation (i.e. the functions, whose names start with \code{hnfmod}) invoke the \LEH, whereas
the other functions terminate at the position, where this is detected, returning a partially HNF
reduced matrix.
\begin{enumerate}
\item Method:

  \begin{fcode}{bigint_matrix}{hnf}{const bigint_matrix& $A$}
    Equivalent to \code{bigint_matrix $B$ = $A$; $B$.hnf_havas(); return $B$;}
  \end{fcode}

  \begin{fcode}{bigint_matrix}{hnf_gls_solver}{const bigint_matrix& $A$, bigint_matrix& $T$}
    Equivalent to \code{bigint_matrix $B$ = $A$; $B$.hnf_havas($T$); return $B$;}
  \end{fcode}


\item Method:

  \begin{fcode}{void}{$A$.hnf_cg}{(const matrix< long >& $B$,
      long Bound1, const bigint& Bound2, int $n$}
  \end{fcode}

  \begin{fcode}{void}{$A$.hnf_cg}{(const matrix< long >& $B$, bigint_matrix& $T$,
      long Bound1, const bigint& Bound2, int $n$}
  \end{fcode}

\item Method:

  \begin{fcode}{void}{$A$.hnf_ref}{}
  \end{fcode}

\item Method:

  \begin{fcode}{void}{$A$.hnf_gls_solver}{}
  \end{fcode}

  \begin{fcode}{void}{$A$.hnf_gls_solver}{bigint_matrix& $T$}
  \end{fcode}

\item Method:

  \begin{fcode}{void}{$A$.hnf_havas}{lidia_size_t KernAlgo $= 0$, lidia_size_t mgcdModul $= 5$, lidia_size_t normalizeModul $= 1$}
    Algorithm by Havas.
  \end{fcode}

  \begin{fcode}{void}{$A$.hnf_havas}{bigint_matrix& $T$, lidia_size_t KernAlgo $= 0$, lidia_size_t mgcdModul $= 5$, lidia_size_t normalizeModul $= 1$}
    Algorithm by Havas.
  \end{fcode}

\item Method:

  \begin{fcode}{void}{$A$.hnf_kannan}{lidia_size_t $S = 0$}
    Algorithm by Kannan.
  \end{fcode}

  \begin{fcode}{void}{$A$.hnf_kannan}{bigint_matrix& $T$, lidia_size_t $S = 0$}
    Algorithm by Kannan.
  \end{fcode}

\item Method:

  \begin{fcode}{void}{$A$.hnf_storjohann}{}
    Algorithm by Storjohann.
  \end{fcode}

  \begin{fcode}{void}{$A$.hnf_storjohann}{bigint_matrix& $T$, bigint_matrix& $C$, bigint_matrix & $Q$}
    Algorithm by Storjohann.
  \end{fcode}

\item Method:

  \begin{fcode}{void}{$A$.hnfmod_dkt}{const bigint& $d$}
    Algortithm by Domich Kannan, and Trotter.
  \end{fcode}

  \begin{fcode}{void}{$A$.hnfmod_dkt}{bigint& $T$, const bigint& $d$}
    Algortithm by Domich Kannan, and Trotter.
  \end{fcode}

  \begin{fcode}{void}{hnfmod_dkt}{}
    Equivalent to \code{$A$.hnfmod_dkt($A$.latticedet())}.
  \end{fcode}

  \begin{fcode}{void}{hnfmod_dkt}{bigint& $T$, const bigint& $d$}
    Equivalent to \code{$A$.hnfmod_dkt($T$, $A$.latticedet())}.
  \end{fcode}

\item Method:

  \begin{fcode}{void}{$A$.hnf_cohen}{}
    Equivalent to \code{$A$.hnf_cohen($A$.latticedet())}.
  \end{fcode}

  \begin{fcode}{void}{hnf_cohen}{const bigint& $d$}
    Algorithm from \cite{Cohen:1995}.
  \end{fcode}

\item Method:

  \begin{fcode}{void}{$A$.hnfmod_mueller}{bigint_matrix& $T$}
    Algorithm by M\"uller \cite{Mueller_Thesis:1994}.
  \end{fcode}

\end{enumerate}

A description of these algorithms and references to the original papers are
contained in \cite{Theobald:2000}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\SSTITLE{Smith Normal Form}

The following functions tranform the given matrix into Smith Normal Form (SNF).  A matrix in SNF
is a diagonal matrix $A = (a_{i,j})$ ($0 \leq i \leq n$, $0 \leq j \leq n$) such that for all $0
\leq i < n$:
\begin{align*}
  a_{i,i} & \geq 0 \\
  a_{n,n} & \geq 0 \\
  a_{i,i} & \mid a_{i+1,i+1}
\end{align*}
\begin{enumerate}
\item Method:

  \begin{fcode}{void}{$A$.snf_simple}{}
    transforms $A$ to Smith Normal Form using a variant of Gau\ss-Jordan elimination.
  \end{fcode}

  \begin{fcode}{bigint_matrix}{snf_simple}{const bigint_matrix & $A$}
    returns the Smith Normal Form of $A$ using a variant of Gau\ss-Jordan elimination.
  \end{fcode}

  \begin{fcode}{void}{$A$.snf_simple}{bigint_matrix & $C$, bigint_matrix & $B$}
    transforms $A$ in Smith Normal Form and sets $B$ and $C$ to the corresponding transformation
    matrices (i.e. $\SNF(A) = C \cdot A \cdot B$) using a variant of Gau\ss-Jordan elimination.
  \end{fcode}

  \begin{fcode}{bigint_matrix}{snf_simple}{const bigint_matrix & $A$, bigint_matrix & $C$, bigint_matrix & $B$}
    returns the Smith Normal Form of $A$ and sets $B$ and $C$ to the corresponding
    transformation matrices (i.e. $\SNF(A) = C \cdot A \cdot B$) using a variant of
    Gau\ss-Jordan elimination.
  \end{fcode}

\item Method:

  \begin{fcode}{void}{$A$.snf_hartley}{}
    transforms $A$ to Smith Normal Form using a variant of the algorithm of Hartley and Hawkes.
  \end{fcode}

  \begin{fcode}{bigint_matrix}{snf_hartley}{const bigint_matrix & $A$}
    returns the Smith Normal Form of $A$ using a variant of the algorithm of Hartley and Hawkes.
  \end{fcode}

  \begin{fcode}{void}{$A$.snf_hartley}{bigint_matrix & $C$, bigint_matrix & $B$}
    transforms $A$ in Smith Normal Form and sets $B$ and $C$ to the corresponding transformation
    matrices (i.e. $\SNF(A) = C \cdot A\cdot B$) using a variant of the algorithm of Hartley and
    Hawkes.
  \end{fcode}

  \begin{fcode}{bigint_matrix}{snf_hartley}{const bigint_matrix & $A$, bigint_matrix & $C$, bigint_matrix & $B$}
    returns the Smith Normal Form of $A$ and sets $B$ and $C$ to the corresponding
    transformation matrices (i.e. $\SNF(A) = C \cdot A\cdot B$) using a variant of the algorithm
    of Hartley and Hawkes.
  \end{fcode}

\item Method:

  \begin{fcode}{void}{$A$.snf_havas}{}
    transforms $A$ to Smith Normal Form using results of \cite{Havas/Holt/Rees:1993}
    \cite{Havas/Majewski:1997} and \cite{Havas/Sterling:1979}.
  \end{fcode}

  \begin{fcode}{bigint_matrix}{snf_havas}{const bigint_matrix & $A$}
    returns the Smith Normal Form of $A$ using results of \cite{Havas/Holt/Rees:1993}
    \cite{Havas/Majewski:1997} and \cite{Havas/Sterling:1979}.
  \end{fcode}

  \begin{fcode}{void}{$A$.snf_havas}{bigint_matrix & $C$, bigint_matrix & $B$}
    transforms $A$ in Smith Normal Form and sets $B$ and $C$ to the corresponding transformation
    matrices (i.e. $\SNF(A) = C \cdot A \cdot B$) using results of \cite{Havas/Holt/Rees:1993}
    \cite{Havas/Majewski:1997} \cite{Havas/Sterling:1979}.
  \end{fcode}

  \begin{fcode}{bigint_matrix}{snf_havas}{const bigint_matrix & $A$, bigint_matrix & $C$, bigint_matrix & $B$}
    returns the Smith Normal Form of $A$ and sets $B$ and $C$ to the corresponding
    transformation matrices (i.e. $\SNF(A) = C \cdot A \cdot B$) using results of
    \cite{Havas/Holt/Rees:1993} \cite{Havas/Majewski:1997} \cite{Havas/Sterling:1979}.
  \end{fcode}
\end{enumerate}
The following functions are based on results of \cite{Havas/Holt/Rees:1993},
\cite{Havas/Majewski:1997} and \cite{Havas/Sterling:1979}.  The extensions \code{add},
\code{mult}, \code{new} specify how column norms and row norms are combined for choosing the
pivot strategy and the paramter $k$ is used to select the $L_k$-norm which is used as described
in these papers (default: $k = 1$).  If $k < 0$ the behaviour of the functions is undefined.

Member functions transform the given (member) matrix in Smith Normal Form.  Functions return the
Smith Normal Form of the first argument.

All functions with more then two arguments compute also the corresponding transformation
matrices $B$ and $C$ with $\SNF(A) = C \cdot A \cdot B$:

\begin{fcode}{void}{$A$.snf_mult}{lidia_size_t $k$ =1}
\end{fcode}

\begin{fcode}{bigint_matrix}{snf_mult}{const bigint_matrix & $A$, lidia_size_t $k$ = 1}
\end{fcode}

\begin{fcode}{void}{$A$.snf_mult}{bigint_matrix & $C$, bigint_matrix & $B$, lidia_size_t $k$ =1}
\end{fcode}

\begin{fcode}{bigint_matrix}{snf_mult}{const bigint_matrix & $A$, bigint_matrix & $C$,
    bigint_matrix & $B$, lidia_size_t $k$ = 1}%
\end{fcode}

\begin{fcode}{void}{$A$.snf_add}{lidia_size_t $k$ = 1}
\end{fcode}

\begin{fcode}{bigint_matrix}{snf_add}{const bigint_matrix & $A$, lidia_size_t $k$ = 1}
\end{fcode}

\begin{fcode}{void}{$A$.snf_add}{bigint_matrix & $C$, bigint_matrix & $B$, lidia_size_t $k$ = 1}
\end{fcode}

\begin{fcode}{bigint_matrix}{snf_add}{const bigint_matrix & $A$, bigint_matrix & $C$,
    bigint_matrix & $B$, lidia_size_t $k$ = 1}%
\end{fcode}

\begin{fcode}{void}{$A$.snf_new}{lidia_size_t $k$ = 1}
\end{fcode}

\begin{fcode}{bigint_matrix}{snf_new}{const bigint_matrix & $A$, lidia_size_t $k$ = 1}
\end{fcode}

\begin{fcode}{void}{$A$.snf_new}{bigint_matrix & $C$, bigint_matrix & $B$, lidia_size_t $k$ = 1}
\end{fcode}

\begin{fcode}{bigint_matrix}{snf_new}{const bigint_matrix & $A$, bigint_matrix & $C$,
    bigint_matrix & $B$, lidia_size_t $k$ = 1}%
\end{fcode}

The following functions use modular algorithms, which are based on \cite{Cohen:1995} and
\cite{Domich:1989}.

\begin{enumerate}
\item Method:

  \begin{fcode}{void}{$A$.snfmod_dkt}{}
    transforms $A$ to Smith Normal Form \cite{Domich:1989}.
  \end{fcode}

  \begin{fcode}{bigint_matrix}{snfmod_dkt}{const bigint_matrix & $A$}
    returns the Smith Normal Form of $A$ \cite{Domich:1989}.
  \end{fcode}

  \begin{fcode}{void}{$A$.snfmod_dkt}{const bigint & $x$}
    transforms $A$ to Smith Normal Form assuming that $x$ is a multiple of the lattice
    determinant \cite{Domich:1989}.
  \end{fcode}

  \begin{fcode}{bigint_matrix}{snfmod_dkt}{const bigint_matrix & $A$, const bigint & $x$}
    returns the Smith Normal Form of $A$ assuming that $x$ is a multiple of the lattice
    determinant \cite{Domich:1989}.
  \end{fcode}

\item Method:

  \begin{fcode}{void}{$A$.snfmod_cohen}{}
    transforms $A$ to Smith Normal Form \cite{Cohen:1995}.
  \end{fcode}

  \begin{fcode}{bigint_matrix}{snfmod_cohen}{const bigint_matrix & $A$}
    returns the Smith Normal Form of $A$ \cite{Cohen:1995}.
  \end{fcode}

  \begin{fcode}{void}{$A$.snfmod_cohen}{const bigint & $x$}
    transforms $A$ to Smith Normal Form assuming that $x$ is a multiple of the lattice
    determinant \cite{Cohen:1995}.
  \end{fcode}

  \begin{fcode}{bigint_matrix}{snfmod_cohen}{const bigint_matrix & $A$, const bigint & $x$}
    returns the Smith Normal Form of $A$ assuming that $x$ is a multiple of the lattice
    determinant \cite{Cohen:1995}.
  \end{fcode}
\end{enumerate}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\SEEALSO

\SEE{base_matrix}, \SEE{math_matrix},
\SEE{base_vector}, \SEE{math_vector}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\NOTES

By inspection of the file \code{LiDIA/bigint_matrix.h} you will discover additional routines for
computing normal forms, the kernel, \dots.  These versions are not yet completely tested, but
should be faster than the well tested functions, that are documented.  In the next release these
functions should be included.  So, if you feel a bit adventurous you might try them and help us
to debug them.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\EXAMPLES

\begin{quote}
\begin{verbatim}
#include <LiDIA/bigint_matrix.h>

int main()
{
    lidia_size_t c = 7, d = 5;

    bigint_matrix A(c,c);
    A.randomize((bigint)10);

    bigint *tmp = A.row(5);
    A.sto_row(tmp,7,3);

    bigint_matrix B, C;

    B = A;
    A.hnf_simple();
    cout << "hnf_simple" << A << flush;

    B = A;
    A.hnf_havas();
    cout << "hnf_havas" << A << flush;

    B = A;
    A.hnf_havas_cont();
    cout << "hnf_havas_cont" << A << flush;

    B = A;
    A.hnf_havas_cont(C);
    cout << A << B*C << flush;

    return 0;
}
\end{verbatim}
\end{quote}

For further examples please refer to \path{LiDIA/src/simple_classes/bigint_matrix_appl.cc}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\AUTHOR

Stefan Neis, Patrick Theobald