\documentclass{article}
\usepackage{amsmath}
\newcommand{\ct}{\texttt}
\newcommand{\luint}{\ct{lu\_int}}
\newcommand{\double}{\ct{double}}

% page size
\setlength{\hoffset}{-1in}
\setlength{\voffset}{-1in}
\setlength{\oddsidemargin}{3.5cm}
\setlength{\evensidemargin}{3.5cm}
\setlength{\topmargin}{2cm}
\setlength{\textwidth}{14cm}
\setlength{\textheight}{22cm}

\title{BASICLU User Guide}
\author{Version 2.2}

\begin{document}
\maketitle

%\setcounter{tocdepth}{1}
\tableofcontents
\newpage

%-------------------------------------------------------------------------------
\section{Algorithm}
%-------------------------------------------------------------------------------
BASICLU implements a right-looking $LU$ factorization with dynamic Markowitz
search and columnwise threshold pivoting. After a column modification to the
matrix it applies either a permutation or the Forrest-Tomlin update to maintain
a factorized form. It uses the method of Gilbert and Peierls to solve triangular
systems with a sparse right-hand side. A more detailed explanation of the method
is given in [Technical Report ERGO 17-002,
http://www.maths.ed.ac.uk/ERGO/preprints.html].

%-------------------------------------------------------------------------------
\section{Installation}
\label{sec:install}
%-------------------------------------------------------------------------------
\subsection{Compiling BASICLU}
Compiling BASICLU requires GNUmake and a C compiler that (partly) supports the
ANSI C99 standard.

To compile the package type \ct{make} in the BASICLU directory. This will create
a static and a shared library inside \ct{lib/}. It will also compile a
standalone program \ct{maxvolume} in \ct{example/}. You can call the latter with
the matrices in \ct{example/data/}.

Compiler and linker flags can be changed in \ct{config.mk} or can be given to
\ct{make} on the command line. See the documentation in \ct{config.mk}.

\subsection{The integer type}
BASICLU integer variables are of type \luint, which is \ct{typedef}'ed in
\ct{basiclu.h}. \luint\ must be a signed integer type. The default is
\ct{int64\_t}. It can be changed before compiling the package. Note:
\begin{itemize}
\item The BASICLU routines do not check for integer overflow. It is in your
  responsibility to choose a sufficiently large integer type for your problems.
\item It is required that all integer values arising in the computation can be
  stored in \double\ variables and converted back to \luint\ without altering
  their value.
\end{itemize}

%-------------------------------------------------------------------------------
\section{Low level C interface}
%-------------------------------------------------------------------------------
The low level C interface consists of routines which do not allocate memory.
Memory must be provided by the user and reallocated on request. To use the low
level C interface, user code must include \ct{basiclu.h}. Defined constants
start with \ct{BASICLU\_} and function names start with \ct{basiclu\_}.

Memory must be provided in form of four \luint\ arrays and four \double\ arrays:
\begin{description}
\item{\ct{istore}, \ct{xstore}} are arrays whose size depends only on the matrix
  dimension (see \ct{basiclu\_initialize} for their required length).
  \ct{xstore} is used to input parameters to the routines and to return
  information to the user. The indices of \ct{xstore} which the user may access
  have defined names, e.\,g.\ \ct{xstore[BASICLU\_STATUS]} holds the status
  code. \ct{istore} need not be accessed by the user.
\item{\ct{Li}, \ct{Lx}, \ct{Ui}, \ct{Ux}, \ct{Wi}, \ct{Wx}} are arrays whose
  required size is not known in advance. Their size must be given by the user
  as parameters (see below) and BASICLU will request reallocation if the size is
  insufficient. These arrays need not be accessed by the user.
\end{description}

\newpage
\subsection{basiclu\_initialize}
{\footnotesize
\input{basiclu_initialize}
}

\newpage
\subsection{basiclu\_factorize}
{\footnotesize
\input{basiclu_factorize}
}

\newpage
\subsection{basiclu\_get\_factors}
{\footnotesize
\input{basiclu_get_factors}
}

\newpage
\subsection{basiclu\_solve\_dense}
{\footnotesize
\input{basiclu_solve_dense}
}

\newpage
\subsection{basiclu\_solve\_sparse}
{\footnotesize
\input{basiclu_solve_sparse}
}

\newpage
\subsection{basiclu\_solve\_for\_update}
{\footnotesize
\input{basiclu_solve_for_update}
}

\newpage
\subsection{basiclu\_update}
{\footnotesize
\input{basiclu_update}
}
\newpage

%-------------------------------------------------------------------------------
\section{High level C interface}
%-------------------------------------------------------------------------------
The high level C interface consists of wrapper functions around the low level
interface which do memory allocation. They maintain the arrays used by the low
level interface inside a \ct{struct basiclu\_object}. To use the high level C
interface, user code must include \ct{basiclu.h}. Defined constants start with
\ct{BASICLU\_} and function names start with \ct{basiclu\_obj\_}.

\newpage
\subsection{basiclu\_object}
{\footnotesize
\input{basiclu_object}
}

\newpage
\subsection{basiclu\_obj\_initialize}
{\footnotesize
\input{basiclu_obj_initialize}
}

\newpage
\subsection{basiclu\_obj\_get\_dim}
{\footnotesize
\input{basiclu_obj_get_dim}
}

\newpage
\subsection{basiclu\_obj\_factorize}
{\footnotesize
\input{basiclu_obj_factorize}
}

\newpage
\subsection{basiclu\_obj\_get\_factors}
{\footnotesize
\input{basiclu_obj_get_factors}
}

\newpage
\subsection{basiclu\_obj\_solve\_dense}
{\footnotesize
\input{basiclu_obj_solve_dense}
}

\newpage
\subsection{basiclu\_obj\_solve\_sparse}
{\footnotesize
\input{basiclu_obj_solve_sparse}
}

\newpage
\subsection{basiclu\_obj\_solve\_for\_update}
{\footnotesize
\input{basiclu_obj_solve_for_update}
}

\newpage
\subsection{basiclu\_obj\_update}
{\footnotesize
\input{basiclu_obj_update}
}

\newpage
\subsection{basiclu\_obj\_free}
{\footnotesize
\input{basiclu_obj_free}
}

\newpage
\subsection{basiclu\_obj\_maxvolume}
{\footnotesize
\input{basiclu_obj_maxvolume}
}
\newpage
 
%-------------------------------------------------------------------------------
\section{Julia interface}
%-------------------------------------------------------------------------------
BASICLU can be used from the Julia programming language. The easiest way is to
install the artifact \ct{basiclu\_jll}, which provides a precompiled library.
Alternatively the code can be compiled from source as described in
Section~\ref{sec:install}. In this case ensure that \ct{int64\_t} is used as
integer type (this is the default). To use the locally compiled library,
environment variable \ct{JULIA\_BASICLU\_LIBRARY\_PATH} must point to the
\ct{lib/} directory.

The following is an example for a Julia program using BASICLU. See also the
documentation of the module functions and \ct{Julia/test.jl}.
{\footnotesize
\begin{verbatim}
include("BASICLU/Julia/basiclu.jl")
m = 1000
obj = basiclu.basiclu_object(m)
B = sprand(m,m,5e-3) + I                     # get a sparse matrix
basiclu.factorize(obj, B)
rhs = randn(m)                               # get a right-hand side
lhs = basiclu.solve(obj, rhs, 'N')
res = norm(B*lhs-rhs,Inf)                    # compute residual
col = sparsevec([1], [1.0], m)               # vector to be inserted into B
lhs = basiclu.solve_for_update(obj, col, getsol=true)
vmax, j = findmax(abs.(lhs))
piv = lhs[j]
basiclu.solve_for_update(obj, j)            # prepare to replace column j of B
piverr = basiclu.update(obj, piv)
lhs = basiclu.solve(obj, rhs, 'N')
B[:,j] = col
res = norm(B*lhs-rhs,Inf)
\end{verbatim}
}
\end{document}