%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%%  bigmod_matrix.tex       LiDIA documentation
%%
%%  This file contains the documentation of the class bigint_matrix
%%
%%  Copyright   (c)   1995   by  LiDIA-Group
%%
%%  Author: Stefan Neis

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

\NAME

\CLASS{bigmod_matrix} \dotfill Linear algebra over $\ZmZ$


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

\ABSTRACT

\code{bigmod_matrix} is a class for doing linear algebra over the residue class ring $\ZmZ$,
where $m$ may be any non-negative integer (for $m = 0$ we do the computations over $\bbfZ$).
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 (\ZmZ)^{k \times l} \enspace,\quad 0\leq i < k,\, 0 \leq j < l
\end{displaymath}
or for representing a homomorphism by its matrix.  In the first case, the class supports for
example computing ``standard generating systems'', in the second case it may be used for
computing the image or the kernel of the homomorphism.

This version is an experimental version which mainly supplies routines needed by \code{modules}
and \code{ideals} in algebraic number fields.  However, we believe, our new algorithms might be
of interest also to other people.  Note however, that the interface of this class is not yet
very stable and will change in future releases.  Especially it is not yet very consistent with
the template classes for matrices.


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

\DESCRIPTION

A variable of type \code{bigmod_matrix} is derived from \code{bigint_matrix} and contains an
additional \code{bigint} $m$ which describes the modulus of the matrix.  Due to this derivation
step, you may call all functions written for \code{bigint_matrices} also on
\code{bigmod_matrices}.  Note however, that the functions inherited from \code{bigint_matrix}
will not reduce their results modulo $m$, but the functions written for \code{bigmod_matrix}
rely on a reduced input! However quite some functions of \code{bigint_matrix} can be used safely
anyway (for example \code{transpose} or \code{diag} with reasonable arguments).  However, be
very careful, which functions you do use.  Especially the \code{sto_column_vector} or
\code{sto_row_vector} functions should be avoided.

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$.


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

\CONS

If $a\leq 0$ or $b\leq 0$ in one of the following constructors the \LEH will be invoked.

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

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

\begin{fcode}{ct}{bigmod_matrix}{lidia_size_t $a$, lidia_size_t $b$, const bigint & $m$}
  constructs an $a \times b$ matrix over $\ZmZ$ initialized with zero.
\end{fcode}

\begin{fcode}{ct}{bigmod_matrix}{const bigmod_matrix & $A$}
  constructs a copy of matrix $A$.
\end{fcode}

\begin{fcode}{ct}{bigmod_matrix}{const base_matrix< bigint > & $A$, const bigint & $m$ = 0}
  constructs a copy of matrix $A$ where every entry is reduced modulo $m$.
\end{fcode}

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


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

\ASGN

Let $A$ be of type \code{bigmod_matrix}.  The operator \code{=} is overloaded.  For consistency
reasons, the following functions are also implemented:

\begin{fcode}{void}{$A$.assign}{const bigmod_matrix & $B$}
\end{fcode}

\begin{fcode}{void}{assign}{bigmod_matrix & $A$, const bigmod_matrix & $B$}
  sets the dimensions and the modulus of matrix $A$ to the dimensions and the modulus of matrix
  $B$ and copies each entry of $B$ to the corresponding position in $A$.
\end{fcode}

\begin{fcode}{void}{$A$.assign}{const base_matrix< bigint > & $B$, const bigint & $m$ = 0}
\end{fcode}

\begin{fcode}{void}{assign}{bigmod_matrix & $A$, const base_matrix< bigint > & $B$,
    const bigint & $m$ = 0}%
  sets the dimensions of matrix $A$ to the dimensions of matrix $B$, sets the modulus of matrix
  $A$ to $m$, and reduces each entry of $B$ modulo $m$ and stores it to the corresponding
  position in $A$.
\end{fcode}


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

\ACCS

Let $A$ be of type \code{bigmod_matrix}.  Note that the numbering of columns and rows starts
with zero.  Also note that for reading access the functions of class \code{bigint_matrix} and
thereby of class \code{base_matrix< bigint >} can safely be used.  However for storing elements,
we would like to reduce the elements by the modulus of the matrix.  For this purpose the
following functions (and only these!!) are supported.

\begin{fcode}{void}{$A$.sto_row}{const bigint * $v$, lidia_size_t $j$, lidia_size_t $i$}
  stores $j$ entries of array $v$ in row $i$ of matrix $A$ starting at column zero, reducing
  them by the modulus of $A$.  If $j > \code{$A$.columns}$ or $j\leq 0$ or $i\geq
  \code{$A$.rows}$ or $i < 0$, the \LEH will be invoked.
\end{fcode}

\begin{fcode}{void}{$A$.sto_column}{const bigint * $v$, lidia_size_t $j$, lidia_size_t $i$}
  stores $j$ entries of array $v$ in column $i$ of matrix $A$ starting at row zero, reducing
  them by the modulus of $A$.  If $j > \code{$A$.rows}$ or $j\leq 0$ or $i\geq
  \code{$A$.columns}$ or $i < 0$, the \LEH will be invoked.
\end{fcode}

\begin{fcode}{void}{$A$.sto}{lidia_size_t $i$, lidia_size_t $j$, const bigint & $x$}
  stores $x$ as $a_{i,j}$ reducing it modulo the modulus of $A$.  If $i\geq \code{$A$.rows}$ or
  $i < 0$ or $j\geq \code{$A$.columns}$ or $j < 0$, the \LEH will be invoked.
\end{fcode}

\begin{cfcode}{const bigint &}{$A$.get_modulus}{}
\end{cfcode}

\begin{fcode}{const bigint &}{get_modulus}{const bigmod_matrix & $A$}
  returns the modulus of the matrix $A$.
\end{fcode}

\begin{fcode}{void}{$A$.set_modulus}{const bigint & $m$}
\end{fcode}

\begin{fcode}{void}{set_modulus}{bigmod_matrix & $A$, const bigint & $m$}
  sets the modulus of the matrix $A$ to $m$.  Note that the entries of the matrix are not
  changed!
\end{fcode}


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

\STITLE{Lifting and Reducing}

Let $A$ be of type \code{bigmod_matrix}.

\begin{fcode}{void}{$A$.reduce}{const bigint & $m$}
\end{fcode}

\begin{fcode}{void}{reduce}{bigmod_matrix & $A$, const bigint & $m$}
  This interprets $A$ as generating a module over $\ZmZ$ (and accordingly may modify $A$).  Note
  that $m$ must divide the previously set modulus, since otherwise this is not considered to be
  a valid operation and the \LEH will be invoked.
\end{fcode}

\begin{fcode}{void}{$A$.lift}{const bigint & $m$}
\end{fcode}

\begin{fcode}{void}{lift}{bigmod_matrix & $A$, const bigint & $m$}
  This interprets $A$ as generating a module over $\ZmZ$ (and accordingly may modify $A$).  Note
  that $m$ must be a multiple of the previously set modulus, since otherwise this is not
  considered to be a valid operation and the \LEH will be invoked.
\end{fcode}


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

\STITLE{Split Functions}

Let $A$ be of type \code{bigmod_matrix}.  The following split functions allow area overlap of
the submatrices as described in the documentation of the class \code{base_matrix< T >}.

If the given conditions in the descriptions of the following functions are not satisfied, the
\LEH will be invoked.

\begin{cfcode}{void}{$A$.split}{bigmod_matrix & $B$, bigmod_matrix & $C$, bigmod_matrix & $D$, bigmod_matrix & $E$}
  takes matrix $A$ apart into the submatrices $B$, $C$, $D$, and $E$, with
  \begin{displaymath}
    A = \begin{pmatrix}
      B & C \\
      D & E
    \end{pmatrix}\enspace,
  \end{displaymath}
  where the following conditions have to be satisfied:
  \begin{itemize}
  \item $\code{$B$.rows}, \code{$C$.rows}, \code{$D$.rows}, \code{$E$.rows} \leq
    \code{$A$.rows}$
  \item $\code{$B$.columns}, \code{$C$.columns}, \code{$D$.columns}, \code{$E$.columns} \leq
    \code{$A$.columns}$
  \end{itemize}
  The entries that are stored into $B$, $C$, $D$, and $E$, respectively, are always reduced
  modulo the corresponding modulus.
\end{cfcode}

\begin{cfcode}{void}{$A$.split_h}{bigmod_matrix & $B$, bigmod_matrix & $C$}
  takes matrix $A$ apart into the submatrices $B$ and $C$, with $A = \begin{pmatrix} B & C
  \end{pmatrix}$ where the following conditions have to be satisfied:
  \begin{itemize}
  \item $\code{$B$.rows}, \code{$C$.rows} \leq \code{$A$.rows}$
  \item $\code{$B$.columns}, \code{$C$.columns} \leq \code{$A$.columns}$
  \end{itemize}
  The entries that are stored into $B$ and $C$, respectively, are always reduced modulo the
  corresponding modulus.
\end{cfcode}

\begin{cfcode}{void}{$A$.split_v}{bigmod_matrix & $B$, bigmod_matrix & $C$}
  takes matrix $A$ apart into the submatrices $B$ and $C$, with $A = \begin{pmatrix} B \\ C
  \end{pmatrix}$, where the following conditions have to be satisfied:
  \begin{itemize}
  \item $\code{$B$.rows}, \code{$C$.rows} \leq \code{$A$.rows}$
  \item $\code{$B$.columns}, \code{$C$.columns} \leq \code{$A$.columns}$
  \end{itemize}
  The entries that are stored into $B$ and $C$, respectively, are always reduced modulo the
  corresponding modulus.
\end{cfcode}


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

\STITLE{Compose Functions}

Let $A$ be of type \code{bigmod_matrix}.  The following compose functions allow area overlap of
the submatrices as described in the documentation of class \code{base_matrix< T >}.  The
matrices $B$, $C$, $D$ and $E$ remain unchanged.

If the given conditions in the descriptions of the following functions are not satisfied, the
\LEH will be invoked.

\begin{fcode}{void}{$A$.compose}{const bigmod_matrix & $B$, const bigmod_matrix & $C$, const bigmod_matrix & $D$, const bigmod_matrix & $E$}
  composes the matrices $B$, $C$, $D$ and $E$ to the matrix $A$, with $A = \begin{pmatrix}
    B & C \\ D & E \end{pmatrix}$ where the following conditions have to be satisfied:
  \begin{itemize}
  \item $\code{$B$.rows}, \code{$C$.rows}, \code{$D$.rows}, \code{$E$.rows} \leq
    \code{$A$.rows}$
  \item $\code{$B$.columns}, \code{$C$.columns}, \code{$D$.columns}, \code{$E$.columns} \leq
    \code{$A$.columns}$
  \end{itemize}
  The entries that are stored into $A$ are always reduced modulo the modulus of $A$.
\end{fcode}

\begin{fcode}{void}{$A$.compose_h}{const bigmod_matrix & $B$, const bigmod_matrix & $C$}
  composes the matrices $B$ and $C$ to the matrix $A$, with $A = \begin{pmatrix} B & C
  \end{pmatrix}$ where the following conditions have to be satisfied:
  \begin{itemize}
  \item $\code{$B$.rows}, \code{$C$.rows} \leq \code{$A$.rows}$
  \item $\code{$B$.columns}, \code{$C$.columns} \leq \code{$A$.columns}$
  \end{itemize}
  The entries that are stored into $A$ are always reduced modulo the modulus of $A$.
\end{fcode}

\begin{fcode}{void}{$A$.compose_v}{const bigmod_matrix & $B$, const bigmod_matrix & $C$}
  composes the matrices $B$ and $C$ to the matrix $A$, with $A = \begin{pmatrix} B \\ C
  \end{pmatrix}$ where the following conditions have to be satisfied:
  \begin{itemize}
  \item $\code{$B$.rows}, \code{$C$.rows} \leq \code{$A$.rows}$
  \item $\code{$B$.columns}, \code{$C$.columns} \leq \code{$A$.columns}$
  \end{itemize}
  The entries that are stored into $A$ are always reduced modulo the modulus of $A$.
\end{fcode}


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

\STITLE{Swap Functions}

Obviously, the function \code{swap_rows} and \code{swap_columns} of class \code{bigint_matrix}
(or more precisely of \code{base_matrix< T >}) can be safely used.  Moreover there is the
following function.

\begin{fcode}{void}{swap}{bigmod_matrix & $A$, bigmod_matrix & $B$}
  swaps $A$ and $B$.
\end{fcode}


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

\ARTH

The class \code{bigmod_matrix} supports the following operators, which
always involve reduction by the modulus of the input matrices.

\begin{center}
  \begin{tabular}{|c|rcl|l|}\hline
    unary & & $op$ & \code{bigmod_matrix} & $op \in \{ \code{-} \}$ \\\hline
    binary & \code{bigmod_matrix} & $op$ & \code{bigmod_matrix}
    & $op \in \{ \code{+}, \code{-}, \code{*} \}$\\\hline
    binary with & \code{bigmod_matrix} & $op$ & \code{bigmod_matrix}
    & $op \in \{\code{+=}, \code{-=}, \code{*=} \}$\\
    assignment & & & &\\\hline
    binary & \code{bigmod_matrix} & $op$ & \code{bigint}
    & $op \in \{ \code{+}, \code{-}, \code{*} \}$\\\hline
    binary with & \code{bigmod_matrix} & $op$ & \code{bigint}
    & $op \in \{ \code{+=}, \code{-=}, \code{*=} \}$\\
    assignment & & & &\\\hline
    binary & \code{bigmod_matrix} & $op$ & \code{(bigint *)} & $op \in \{ \code{*} \}$\\\hline
  \end{tabular}
\end{center}

Here the operators operating on two matrices and the unary minus implement the usual operations
known from linear algebra.  Especially the moduli of the input matrices have to be the same,
otherwise the \LEH will be invoked; if the dimensions of the operands do not satisfy the usual
restrictions, the \LEH will also be invoked.  Note that the dimensions of the resulting matrix
are adapted to the right dimensions known from linear algebra if necessary.

The operator \code{bigmod_matrix * (bigint *)} realizes the matrix-vector-multiplication.  If
the number of elements does not satisfy the usual restrictions known from linear algebra the
behaviour is undefined.

The operators $op$ which have a single element of type \code{bigint} in their list of arguments
perform the operation $op$ componentwise and reduce the result by the modulus of the matrix.
E.g.~$\code{bigmod_matrix} \cdot \code{bigint}$ multiplies each entry of the matrix by the given
scalar, and reduces by the modulus of the matrix.

To avoid copying, all operators also exist as functions and of course the restrictions for the
dimensions are still valid:

\begin{fcode}{void}{add}{bigmod_matrix & $C$, const bigmod_matrix & $A$, const bigmod_matrix & $B$}
  $C \assign A+B$.
\end{fcode}

\begin{fcode}{void}{add}{bigmod_matrix & $C$, const bigmod_matrix & $B$, const bigint & $e$}
  Let $r = \code{$B$.rows}$ and $c = \code{$B$.columns}$.
  \begin{displaymath}
    \begin{pmatrix}
      c_{0,0} & \dots & c_{0,c-1}\\
      \vdots & \ddots & \vdots \\
      c_{r-1,0} & \dots & c_{r-1,c-1}
    \end{pmatrix} \assign 
    \begin{pmatrix}
      b_{0,0}+e & \dots & b_{0,c-1}+e\\
      \vdots & \ddots & \vdots \\
      b_{r-1,0}+e & \dots & b_{r-1,c-1}+e
    \end{pmatrix}\enspace.
  \end{displaymath}
\end{fcode}

\begin{fcode}{void}{subtract}{bigmod_matrix & $C$, const bigmod_matrix & $A$, const bigmod_matrix & $B$}
  $C \assign A-B$.
\end{fcode}

\begin{fcode}{void}{subtract}{bigmod_matrix & $C$, const bigmod_matrix & $B$, const bigint & $e$}
  Let $r = \code{$B$.rows}$ and $c = \code{$B$.columns}$.
  \begin{displaymath}
    \begin{pmatrix}
      c_{0,0} & \dots & c_{0,c-1}\\
      \vdots & \ddots & \vdots \\
      c_{r-1,0} & \dots & c_{r-1,c-1}
    \end{pmatrix} \assign 
    \begin{pmatrix}
      b_{0,0}-e & \dots & b_{0,c-1}-e\\
      \vdots & \ddots & \vdots \\
      b_{r-1,0}-e & \dots & b_{r-1,c-1}-e
    \end{pmatrix}\enspace.
  \end{displaymath}
\end{fcode}

\begin{fcode}{void}{multiply}{bigmod_matrix & $C$, const bigmod_matrix & $A$, const bigmod_matrix & $B$}
  $C \assign A \cdot B$.
\end{fcode}

\begin{fcode}{void}{multiply}{bigmod_matrix& $C$, const bigmod_matrix & $B$, const bigint & $e$}
  Let $r = \code{$B$.rows}$ and $c = \code{$B$.columns}$.
  \begin{displaymath}
    \begin{pmatrix}
      c_{0,0} & \dots & c_{0,c-1}\\
      \vdots & \ddots & \vdots \\
      c_{r-1,0} & \dots & c_{r-1,c-1}
    \end{pmatrix} \assign 
    \begin{pmatrix}
      b_{0,0} \cdot e & \dots & b_{0,c-1} \cdot e\\
      \vdots & \ddots & \vdots \\
      b_{r-1,0} \cdot e & \dots & b_{r-1,c-1} \cdot e
    \end{pmatrix}\enspace.
  \end{displaymath}
  Note that in this special case reduction is done by the modulus of $C$.  This is helpful in
  some contexts while disturbing in others!
\end{fcode}

\begin{fcode}{void}{multiply}{bigint * & $v$, const bigmod_matrix & $A$, const bigint * $w$}
  assigns the result of the muliplication $A \cdot w$ to $v$
  (matrix-vector-multiplication).  If a suitable amount of memory has not
  been allocated for the arrays $w$ and $v$, the behaviour of
  this function is undefined.
\end{fcode}

\begin{fcode}{void}{negate}{bigmod_matrix& $B$, const bigmod_matrix & $A$}
  $B \assign -A$.
\end{fcode}


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

\COMP

The binary operators \code{==} and \code{!=} are overloaded and can be used for comparison by
components.  Let $A$ be an instance of type \code{bigmod_matrix}.

\begin{cfcode}{bool}{$A$.equal}{const bigmod_matrix & $B$}
  returns \TRUE if $A$ and $B$ are identical, \FALSE otherwise.
\end{cfcode}

\begin{fcode}{bool}{equal}{const bigmod_matrix & $A$, const bigmod_matrix & $B$}
  returns \TRUE if $A$ and $B$ are identical, \FALSE otherwise.
\end{fcode}

\begin{cfcode}{bool}{$A$.unequal}{const bigmod_matrix & $B$}
  returns \FALSE if $A$ and $B$ are identical, \TRUE otherwise.
\end{cfcode}

\begin{fcode}{bool}{unequal}{const bigmod_matrix & $A$, const bigmod_matrix & $B$}
  returns \FALSE if $A$ and $B$ are identical, \TRUE otherwise.
\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.  Linear algebra over $\ZmZ$ can
be done following two philosophies: Either you are content to get a partial result and a factor
of $m$ (for example for reducing the partial result and using the chinese remainder theorem.
This however is not very good for ``small'' $m$) or you want a result over $\ZmZ$ no
matter what.  Since this can also be done efficiently, we offer both methods.  So far, however,
not both versions of all functions are supported.

\begin{fcode}{void}{$A$.adj}{const bigmod_matrix & $B$, bigint & $f$}
\end{fcode}

\begin{fcode}{bigmod_matrix}{adj}{const bigmod_matrix & $B$, bigint & $f$}
  stores either the adjoint matrix of $B$ to $A$ or a non-trivial factor of $m$ to $f$.
\end{fcode}

\begin{fcode}{void}{$A$.inv}{const bigmod_matrix & $B$, bigint & $f$}
\end{fcode}

\begin{fcode}{bigmod_matrix}{inv}{const bigmod_matrix & $B$, bigint & $f$}
  stores either the inverse matrix of $B$ to $A$ or a non-trivial factor of $m$ to $f$.
\end{fcode}

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

\begin{fcode}{bigint *}{charpoly}{const bigmod_matrix & $A$, bigint & $f$}
  returns either an array $v$ of coefficients of the characteristic polynomial of $A$, where
  $v[i]$ contains the coefficient of $x^i$ or sets $f$ to some non-trivial factor of $m$.
\end{fcode}

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

\begin{fcode}{bigint}{det}{const bigmod_matrix & $A$, bigint & $f$}
  either returns the determinant of matrix $A$ or sets $f$ to some non-trivial factor of $m$.
\end{fcode}

\begin{cfcode}{void}{$A$.det}{bigint & $x$, bigint & $f$}
  either $x \assign \code{det}(A)$ or $f$ is set to some non-trivial factor of $m$.
\end{cfcode}

\begin{fcode}{void}{$A$.image}{const bigmod_matrix & $B$, bigint & $f$}
  either stores a generating system of the image of the homomorphism defined by $B$ to $A$ or
  sets $f$ to some non-trivial factor of $m$.
\end{fcode}

\begin{fcode}{bigmod_matrix}{image}{const bigmod_matrix & $B$, bigint & $f$}
  either returns a generating system of the image of the homomorphism defined by $B$ or sets $f$
  to some non-trivial factor of $m$.
\end{fcode}

\begin{fcode}{void}{$A$.image}{const bigmod_matrix & $B$}
  stores a generating system of the image of the homomorphism defined by $B$ to $A$.
\end{fcode}

\begin{fcode}{bigmod_matrix}{image}{const bigmod_matrix & $B$}
  returns a generating system of the image of the homomorphism defined by $B$.
\end{fcode}

\begin{fcode}{void}{$A$.unique_image}{const bigmod_matrix & $B$}
  stores a uniquely determined generating system of the image of the homomorphism defined by $B$
  to $A$ .
\end{fcode}

\begin{fcode}{bigmod_matrix}{unique_image}{const bigmod_matrix & $B$}
  returns a uniquely determined generating system of the image of the homomorphism defined by
  $B$.
\end{fcode}

\begin{fcode}{void}{$A$.kernel}{const bigmod_matrix & $B$, bigint & $f$}
  either stores a generating system of the kernel of the homomorphism defined by matrix $B$ to
  $A$ or sets $f$ to some non-trivial factor of $m$.
\end{fcode}

\begin{fcode}{bigmod_matrix}{kernel}{const bigmod_matrix & $B$, bigint & $f$}
  either returns a generating system of the kernel of the homomorphism defined by matrix $B$ to
  $A$ or sets $f$ to some non-trivial factor of $m$.
\end{fcode}

\begin{fcode}{void}{$A$.kernel}{const bigint_matrix & $B$}
  stores a generating system of the kernel of the homomorphism defined by matrix $B$ to $A$.
\end{fcode}

\begin{fcode}{bigint_matrix}{kernel}{const bigint_matrix & $B$}
  returns a generating system of the kernel of the homomorphism defined by matrix $B$ to $A$.
\end{fcode}


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

\IO

The \code{istream} operator \code{>>} and the \code{ostream} operator \code{<<} are overloaded.
The \code{istream} operator \code{>>} reads matrices in the following format from istream:

\begin{displaymath}
  r \sqcup c \sqcup m \sqcup a_{0,0} \sqcup a_{0,1} \sqcup
  \dots \sqcup a_{0,c-1} \sqcup a_{1,0} \sqcup \dots \sqcup a_{1,c-1}
  \sqcup  \dots \sqcup a_{r-1,0} \sqcup \dots \sqcup a_{r-1,c-1}
\end{displaymath}
where $r = \code{$A$.rows}$, $c = \code{$A$.columns}$, and $m = A.modulus$.

The \code{ostream} operator \code{<<} outputs the matrix in a beautified format
which looks as follows:
\begin{displaymath}
  \begin{array}{cccccc}
    (& a_{0,0} & a_{0,1} & \dots & a_{0,c-1}&)\\
    (& a_{1,0} &  \dots & \dots & a_{1,c-1}&)\\
    (& \vdots & \vdots & \vdots & \vdots &)\\
    (& a_{r-1,0} & \dots & \dots & a_{r-1,c-1}&)
  \end{array}
  \bmod m \enspace.
\end{displaymath}

For supporting more input and output formats we suggest to read and write \code{bigint_matrices}
and the modulus separately, thus enabling all the formats supported by \code{bigint_matrix}.


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

\WARNINGS

The behaviour of the function

\begin{fcode}{void}{multiply}{bigmod_matrix& $C$, const bigmod_matrix & $B$, const bigint & $e$}
\end{fcode}

may be surprising sometimes, since the modulus of $C$ is \emph{not} set to the modulus of $B$
and reduction is done by the modulus of $C$, \emph{not} by the modulus of $B$.


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

\SEEALSO

\SEE{base_matrix}, \SEE{math_matrix},
\SEE{bigint_matrix}


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

\NOTES

\begin{enumerate}
\item As described in the introduction this version is very preliminary.

\item As usually in C++ the numbering of columns and rows starts with zero.
\end{enumerate}


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

\AUTHOR

Stefan Neis, Patrick Theobald
