%
% Zweiter Teil des englischen PASCAL--XSC Textes
% ============================================
%
%
% Neues Kapitel
% =============
%
\subsection{Accurate Expressions}
%
The implementation of inclusion algorithms with automatic result verification
or validation (see \cite{psc17},\cite{tagungsband},\cite{psc18},\cite{ullrich})
makes extensive use of the
accurate evaluation of dot products with the property (see \cite{psc5})
\[
  \mbox{(RG)} \:\:\: a \bigodot b := \bigcirc \sum_{i=1}^{n} a_i \cdot b_i,
                  \:\: \bigcirc \in \{\Box,\bigtriangleup,
                  \raisebox{2pt}{$\bigtriangledown$}\},
                  \:\: n \in \N.
\]
To evaluate this kind of expression the new datatype
{\sl dotprecision\,} was introduced. This datatype accomodates
the full floating-point
range with double exponents (see \cite{psc5},\cite{tagungsband}).
Based upon this type, so-called {\em accurate expressions\/}
(\#-expressions), can be
formulated by an accurate symbol (\#, \#$*$, \#$<$, \#$>$, or
\#\#) followed by an {\em exact expression\/} enclosed in parentheses.
The exact expression must have the form of a dot product expression and
is evaluated without any rounding error.
The following standard operations
are available for {\sl dotprecision\/}:
%
\begin{itemize}
  \itemsep0em
  \item conversion of {\sl real\,} and {\sl integer\,} values to
        {\sl dotprecision\,} (\#)
  \item rounding of {\sl dotprecision\,} values to {\sl real\,};
        in particular:
        downwardly directed rounding (\#{$<$}),
        upwardly directed rounding (\#{$>$}), and
        rounding to the nearest (\#{$*$})
  \item rounding of a {\sl dotprecision\,} expression to the smallest
        enclosing interval (\#\#)
  \item addition of a {\sl real\,} number or the product of two
        {\sl real\,} numbers to a variable of type {\sl dotprecision\,}
  \item addition of a dot product to a variable of type {\sl dotprecision\,}
  \item addition and subtraction of {\sl dotprecision\,} numbers
  \item monadic minus of a {\sl dotprecision\,} number
  \item the standard function {\sl sign\,} returns
        $-1$, $0$, or $+1$, depending
        on the sign of the {\sl dotprecision\,} number
\end{itemize}
To obtain the unrounded or correctly rounded result of a dot product
expression, the user needs to parenthesize the expression and precede it by the
symbol $\#$ which may optionally be followed by a symbol for the rounding
mode.
Table 6 shows the possible rounding modes with respect to the
dot product expression form (see the appendix on
page \pageref{app} for details).
%
% Tabelle mit den dot precision Rundungen
% =======================================
%
\begin{center}
  \small
    %
    \begin{tabular}{|c|c|c|}
      \hline
      %----------------------------------------------------------------------
        \rule[-1.5ex]{0ex}{4ex}
        Symbol
      & Expression Form
      & Rounding Mode                             \\
      %
      \hline \hline
      %---------------------------------------------
      %---------------------------------------------
        $\# *$
        \rule[-1.5ex]{0ex}{4ex}
      & scalar, vector or matrix
      & nearest                                   \\
      \hline
      %---------------------------------------------
        $\# \! <$
        \rule[-1.5ex]{0ex}{4ex}
      & scalar, vector or matrix
      & downwards                                 \\
      \hline
      %---------------------------------------------
        $\# \! >$
        \rule[-1.5ex]{0ex}{4ex}
      & scalar, vector or matrix
      & upwards                                   \\
      \hline
      %---------------------------------------------
        $\#\#$
        \rule[-1.5ex]{0ex}{4ex}
      & scalar, vector or matrix
      & smallest enclosing interval               \\
      \hline
      %---------------------------------------------
        $\#$
        \rule[-1.5ex]{0ex}{4ex}
      & scalar only
      & exact, no rounding                        \\
      \hline
      %---------------------------------------------
    \end{tabular}\\[1.5ex]
    %
    {\normalsize Table 6:~ Rounding Modes for Accurate Expressions}
\end{center}
%

\noindent
In practice, dot product expressions may contain a large number of terms
making an explicit notation very cumbersome.
To alleviate this difficulty in mathematics, the symbol $\sum_{ }$
is used. If for instance $A$ and $B$ are \mbox{$n$-dimensional} matrices,
then the evaluation of
\[
  \sum_{k=1}^n A(i,k) \cdot B(k,j)
\]
represents a dot product expression.
PASCAL--XSC provides the equivalent shorthand notation {\bf sum} for this
purpose. The corresponding PASCAL--XSC statement for this expression is
\begin{quote}
  D := \#{({\bf for} k:=1 {\bf to} n {\bf sum} (A[i,k]$*$B[k,j]))}
\end{quote}
where D is a {\sl dotprecision\,} variable.

Dot product expressions or accurate expressions are used mainly in
computing defect
expressions. Let, for instance, in case of a linear system $Ax=b$,
$A \in \R^{n \times n}$, $x,b \in \R^n$, be $Ay \! \approx \! b$.
Then an enclosure of the defect is given by
$\raute (b-Ay)$ and is realized in PASCAL--XSC via
%
\begin{quote}
  \#\#{(b $-$ A$*$y);}
\end{quote}
%
with only one interval rounding oper\-ation per component. To get verified
inclusions of linear systems of equations it is necessary to evaluate
the defect expression
\[
  \raute (E - RA)
\]
were $R \approx A^{-1}$ and $E$ is the identity matrix.
In PASCAL--XSC this expression can be programmed as
%
\begin{quote}
  \#\#{(id(A) $-$ R$*$A);}
\end{quote}
%
where an interval matrix is computed with only one rounding
oper\-ation per component. The function
{\sl id($\ldots$)\,}
is a part of the module for real matrix/vector arithmetic and generates
an identity matrix of appropriate dimension according to the shape of A
(see section \ref{sec:psc8}).
%
% Neues Kapitel
% =============
%
\subsection{The String Concept}
%
The tools provided for handling strings in standard PASCAL do not enable
convenient text processing. For this reason,
a string concept was integrated into the language definition of PASCAL--XSC
which allows a
comfortable handling of textual information and even symbolic computation.
With this new data
type {\sl string}, the user can work with strings of up to 255
characters. Provided a string doesn't exceed a certain range, the user can
specify the length in the
{\sl string\,} declaration part. Thus a string {\sl s\/} declared by
%
\begin{quote}
  {\bf var} s: string[40];
\end{quote}
%
can be up to 40 characters long.
The following standard operations are available:
%
\begin{itemize}
  \item concatenation
    \begin{quote}
      \hspace{-2em} {\bf operator} + (a,b: string) conc: string;
    \end{quote}
  \item actual length
    \begin{quote}
      \hspace{-2em} {\bf function} length(s: string): integer;
    \end{quote}
  \item conversion {\sl string\,} $\rightarrow$ {\sl real\,}
    \begin{quote}
      \hspace{-2em} {\bf function} rval(s: string): real;
    \end{quote}
  \item conversion {\sl string\,} $\rightarrow$ {\sl integer\,}
    \begin{quote}
      \hspace{-2em} {\bf function} ival(s: string): integer;
    \end{quote}
  \item conversion {\sl real\,} $\rightarrow$ {\sl string\,}
    \begin{quote}
      \hspace{-2em} {\bf function}
      image(r: real; width,fracs,round: integer): string;
    \end{quote}
  \item conversion {\sl integer\,} $\rightarrow$ {\sl string\,}
    \begin{quote}
      \hspace{-2em} {\bf function} image(i,len: integer): string;
    \end{quote}
  \item extraction of substrings
    \begin{quote}
      \hspace{-2em} {\bf function} substring(s: string; i,j: integer): string;
    \end{quote}
  \item position of first appearance
    \begin{quote}
      \hspace{-2em} {\bf function} pos(sub,s: string): integer;
    \end{quote}
  \item relational operators $<$=, $<$, $>$=, $>$, $<>$, =, and {\bf in}
\end{itemize}
%
% Neues Kapitel
% =============
%
\subsection{Standard Modules}
\label{sec:psc8}
%
The following standard modules are available:
%
\begin{itemize}
  \itemsep0em
  \item interval arithmetic (I\_\,ARI)
  \item complex arithmetic (C\_\,ARI)
  \item complex interval arithmetic (CI\_\,ARI)
  \item real matrix/vector arithmetic (MV\_\,ARI)
  \item interval matrix/vector arithmetic (MVI\_\,ARI)
  \item complex matrix/vector arithmetic (MVC\_\,ARI)
  \item complex interval matrix/vector arithmetic (MVCI\_\,ARI)
\end{itemize}
%
These modules may be incorporated via the {\bf use}-statement described
in section \ref{sec:psc4}.
As an example, table 7 exhibits the operators provided by the
module for interval matrix/vector arithmetic.
%
\begin{center}
  \scriptsize
  \setlength{\arraycolsep}{2pt}
  \setlength{\tabcolsep}{2pt}
  %
  \begin{tabular}{|c||c|c|c|c|c|c|}
    \hline
    %----------------------------------------------------------------------
      \begin{tabular}{c}
        \setlength{\unitlength}{1.0em}
        \begin{picture}(6,4)
          \put(-0.5,4){\line(3,-2){6.50}}
          \put(0,2){\makebox(0,0)[tl]{left}}
          \put(0,1){\makebox(0,0)[tl]{operand}}
          \put(6,3){\makebox(0,0)[br]{right}}
          \put(6,2){\makebox(0,0)[br]{operand}}
        \end{picture}
      \end{tabular}
    %
    & \begin{tabular}{c}  integer      \\ real        \end{tabular}
    & interval
    & rvector
    & ivector
    & rmatrix
    & imatrix                                                           \\
    %
    \hline \hline
    %---------------------------------------------------------------------
    %---------------------------------------------------------------------
      monadic \rule[-1ex]{0ex}{3ex}
    &
    &
    &
    & $ +,- $
    &
    & $ +,- $                                                           \\
    %
    \hline
    %---------------------------------------------------------------------
      \begin{tabular}{c}  integer \\ real  \end{tabular}
      \rule[-2ex]{0ex}{6ex}
    &
    &
    &
    & $ * $
    &
    & $ * $                                                             \\
    %
    \hline
    %---------------------------------------------------------------------
      interval \rule[-1ex]{0ex}{3ex}
    &
    &
    & $ * $
    & $ * $
    & $ * $
    & $ * $                                                             \\
    %
    \hline
    %---------------------------------------------------------------------
      rvector
    &
    & $ *,/ $
    & $ +* $
    & $ \begin{array}{c}
          +*,      \\
          +,-,*,   \\
          \mbox{\bf in},=,<>
        \end{array} $
    &
    &                                                                   \\
    %
    \hline
    %---------------------------------------------------------------------
      ivector
    & $ *,/ $
    & $ *,/ $
    & $ \begin{array}{c}
          +*,      \\
          +,-,*,   \\
          =,<>
        \end{array} $
    & $ \begin{array}{c}
          +*,**,     \\
          +,-,*,     \\
          \mbox{\bf in},=,<>,><,   \\
          <=,<,>=,>
        \end{array} $
    &
    &                                                                   \\
    %
    \hline
    %---------------------------------------------------------------------
      rmatrix
    &
    & $ *,/ $
    &
    & $ * $
    & $ +* $
    & $ \begin{array}{c}
          +*,      \\
          +,-,*,   \\
          \mbox{\bf in},=,<>
        \end{array} $                                                   \\
    %
    \hline
    %---------------------------------------------------------------------
      imatrix
    & $ *,/ $
    & $ *,/ $
    & $ * $
    & $ * $
    & $ \begin{array}{c}
          +*,      \\
          +,-,*,   \\
          =,<>
        \end{array} $
    & $ \begin{array}{c}
          +*,**,     \\
          +,-,*,     \\
          \mbox{\bf in},=,<>,><,   \\
          <=,<,>=,>
        \end{array} $                                                   \\
    %
    \hline
    %---------------------------------------------------------------------
  \end{tabular}\\[1.5ex]
  %
  {\normalsize Table 7:~ \parbox[t]{0.7\textwidth}{Predefined Arithmetical and
           Relational Operators of the Module MVI\_\,ARI}}
\end{center}
%

\noindent
In addition to these operators, the module MVI\_\,ARI
provides the following generically named standard operators, functions, and
procedures
\begin{quote}
  {\sl intval, inf, sup, diam, mid, blow, transp, null, id,
       read,\,} and {\sl write.}
\end{quote}
The function {\sl intval\,} is used to generate interval vectors and matrices
respectively, whereas {\sl inf\,} and {\sl sup\,} are selection functions
for the infimum and supremum of an interval object.
The diameter and the midpoint of interval vectors and matrices are determined
via {\sl diam\,} and {\sl mid},
{\sl blow\,} yields an interval inflation and {\sl transp\,} is used to
get the transposed of a matrix.
\pagebreak

\noindent
Zero vectors and matrices are generated by the function {\sl null}, while
{\sl id\,} returns an identity matrix of appropriate shape.
Finally, there are the generic input/output-procedures
{\sl read\,} and {\sl write},
which may be used in connection with all matrix/vector data types defined
in the modules mentioned above.
%
% Neues Kapitel
% =============
%
%
\subsection{Problem-Solving Routines}
%
PASCAL--XSC routines for solving common numerical
problems are supplied by means of an
additional module library.
The applied methods
compute a highly accurate inclusion of the true solution of the problem
and, at the same time, prove existence and uniqueness of the solution in
the given interval.  The advantages of these new routines are listed in the
following:
\begin{itemize}
  \itemsep0em
  \item The solution is computed with maximum or highly, but always controlled
        accuracy, even in many ill-conditioned cases.
  \item The correctness of the result is automatically verified, i.\ e.\
        an inclusion set is computed which
        guarantees existence and uniqueness of the exact solution within.
  \item In case no solution exists or the problem is extremely
        ill-conditioned, an error
        message is indicated.
  \item Since the user has almost no chance to make an error or to
        misinterpret something,
        these routines may also be
        applied by non-specialists.
\end{itemize}
Particularly, PASCAL--XSC routines cover the following subjects:
\begin{itemize}
  \itemsep0em
  \item linear systems of equations
        \begin{itemize}
          \itemsep0em
          \item full systems ({\sl real,
                complex, interval, cinterval\/})
          \item matrix inversion ({\sl real,
                complex, interval, cinterval\/})
          \item least squares problems ({\sl real,
                complex, interval, cinterval\/})
          \item computation of pseudo inverses ({\sl real,
                complex, interval, cinterval\/})
          \item band matrices ({\sl real\/})
          \item sparse matrices ({\sl real\/})
        \end{itemize}
  \item polynomial evaluation
        \begin{itemize}
          \itemsep0em
          \item in one variable ({\sl real, complex, interval, cinterval\/})
          \item in several variables ({\sl real\/})
        \end{itemize}
  \item zeros of polynomials ({\sl real, complex, interval, cinterval\/})
  \item eigenvalues and eigenvectors
        \begin{itemize}
          \itemsep0em
          \item symmetric matrices ({\sl real\/})
          \item arbitrary matrices ({\sl real, complex, interval,
                cinterval\/})
        \end{itemize}
\pagebreak
  \item initial and boundary value problems of ordinary differential equations
        \begin{itemize}
          \itemsep0em
          \item linear
          \item nonlinear
        \end{itemize}
  \item evaluation of arithmetic expressions
  \item noninear systems of equations
  \item numerical quadrature
  \item integral equations
  \item automatic differentiation
\end{itemize}
%
\section{The Implementation of PASCAL--XSC}
%
Since 1976, a PASCAL extension for scientific computation has been
in the process of being defined and developed
at the Institute for Applied Mathematics at the University of Karlsruhe.
The PASCAL-SC compiler has been implemented
on several computers (Z80, 8088, and 68000 processors) under various operating
systems. This compiler was already
in the marketplace for the IBM PC/AT and the
ATARI-ST (see \cite{psc8}, \cite{psc13}).

The new PASCAL--XSC compiler
is now available for
personal computers, workstations, mainframes, and
supercomputers by means of an implementation in C.
Via a PASCAL--XSC-to-C precompiler and a runtime system implemented in C
the language PASCAL--XSC may be used, among other systems, on all UNIX
systems in an almost identical way. Thus, the user has the possibility to
develop his programs for example on a personal computer and afterwards get
them running on a mainframe via the same compiler.

A complete description of the language PASCAL--XSC and the arithmetic
modules as well as a collection of sample programs is given in
\cite{pxscbuch} and \cite{pxscbook}.
%
\section{PASCAL--XSC Sample Program}
%
In the following, a complete PASCAL--XSC program is listed, which demonstrates
the use of some of the arithmetic modules.
Using the module
LIN\_\,SOLV, the solution of a system of linear equations is enclosed in an
interval vector by succecsive interval iterations.

The procedure {\sl main\/}, which is called in the body of {\sl lin\_sys\/},
is only used for reading the dimension of the system and for allocation
of the dynamic variables.
The numerical method itself is started by the call of procedure
\mbox{\sl linear\_system\_solver\/} defined in module LIN\_SOLV.
This procedure may be called with arbitrary dimension of the used arrays.

For detailed information on iteration methods with automatic result
verification
see \cite{psc17}, \cite{tagungsband}, \cite{psc18}, or
\cite{psc14}, for example.
%
\pagebreak%
%
% PASCAL--XSC Beispielprogramm
%
\subsection*{Main Program}
%
\newcommand{\bs}{\normalsize\bf}
%
\begin{flushleft}
\small
\setlength{\tabcolsep}{0pt}
%
\LL \\
{\bs program} lin\_sys (input,output);                         \\
\LL                                                                       \\
\begin{tabular}{rll}
\{~ & Program for verified solution of a linear system of equations. The  & ~\} \\
\{~ & matrix A and the right-hand side b of the system are to be read in. & ~\} \\
\{~ & The program delivers either a verified solution or a corresponding  & ~\} \\
\{~ & failure message.                                                    & ~\} \\
\end{tabular} \LL\\
\LL                                                                       \\
\LL \\
\begin{tabular}{lrllll}
{\bs use}                    & \{~ & lin\_solv & ~:~ & linear system solver            & ~\} \\
\LL lin\_solv, mv\_ari, mvi\_ari;~ & \{~ & mv\_ari    & ~:~ & matrix/vector arithmetic & ~\} \\
                             & \{~ & mvi\_ari   & ~:~ & matrix/vector interval arithmetic & ~\} \\
{\bs var}                                                                   \\
\LL  n  :  integer;      &     &        &   &                             \\
\end{tabular} \\
\LL               \\
\LL  \\
\{- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -\} \\
\LL                                                                       \\
{\bs procedure} main (n : integer);                                               \\
\LL                                                                       \\
\begin{tabular}{rll}
 \{~ & The matrix A and the vectors b, x are allocated dynamically with   & ~\} \\
 \{~ & this subroutine being called. The Matrix A and the right-hand side & ~\} \\
 \{~ & b are read in and linear\_system\_solver is called.            & ~\} \\
\end{tabular}\\
\LL \\
\LL                                                                       \\
{\bs var}                                                                   \\
\begin{tabular}{lll}
\LL  ok & ~:~ &  boolean;                                                       \\
\LL  b  & ~:~ &  rvector[1..n];                                                 \\
\LL  x  & ~:~ &  ivector[1..n];                                                 \\
\LL  A  & ~:~ &  rmatrix[1..n,1..n];                                            \\
\end{tabular}\\
\LL                                                                       \\
\LL \\
{\bs begin}                                                                       \\
\LL \\
\LL  writeln('Please enter the matrix A:');                               \\
\LL  read(A);                                                        \\
\LL \\
\LL  writeln('Please enter the right-hand side b:');                      \\
\LL  read(b);                                                        \\
\LL                                                                       \\
\LL  linear\_system\_solver(A,b,x,ok);                                \\
\LL                                                                       \\
\LL  {\bs if} ok {\bs then}                                                           \\
\LL \\
\LL\LL    {\bs begin}                                                         \\
\LL\LL\LL      writeln('The given matrix A is non-singular and the solution '); \\
\LL\LL\LL      writeln('of the linear system is contained in:');      \\
\LL\LL\LL      write(x);                                         \\
\LL\LL    {\bs end}                                                           \\
\LL \\
\LL  {\bs else}                                                                 \\
\LL \\
\LL\LL    writeln('No solution found !');                               \\
\LL                                                                       \\
{\bs end}; \LL \{procedure main\}                                                      \\
\LL                                                                       \\
\{- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -\} \\
\LL                                                                       \\
{\bs begin}                                                                       \\
\LL \\
\LL  write('Please enter the dimension n of the linear system: '); \\
\LL  read(n);\\
\LL  main(n);                                                             \\
\LL \\
{\bs end}. \{program lin\_sys\}
%
\end{flushleft}
%
%
\newpage
%
\subsection*{Module LIN\_SOLV}
%
\begin{flushleft}
\small
\setlength{\tabcolsep}{0pt}
%
\LL \\
{\bs module} lin\_solv;                                         \\
\LL                                                                       \\
 \{ Verified solution of the linear system of equations Ax = b. \}          \\
\LL                                                                       \\
\begin{tabular}{lrllll}
{\bs use}                      & \{~ & i\_ari  & ~:~ & interval arithmetic               & ~\} \\
\LL i\_ari, mv\_ari, mvi\_ari;~ & \{~ & mv\_ari & ~:~ & matrix/vector arithmetic   & ~\} \\
                               & \{~ & mvi\_ari& ~:~ & matrix/vector interval arithmetic & ~\} \\
\end{tabular}\\
{\bs priority}                                                                    \\
\LL  inf\/lated = $*$; \LL       \{ priority level 2 \}                   \\
\LL                                                                       \\
\LL \\
\{- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -\}\\
\LL \\
\LL                                                                       \\
{\bs operator} inf\/lated (a : ivector; eps : real)inf\/l: ivector[1..ubound(a)];     \\
\LL                                                                       \\
 \{ Computes the so-called epsilon inflation of an interval vector. \}      \\
\LL                                                                       \\
%
{\bs var}                                                                   \\
  \begin{tabular}{lll}
    \LL  i              & ~:~ &  integer;                              \\
    \LL  x              & ~:~ &  interval;                             \\
  \end{tabular}                                                             \\
\LL                                                                       \\
{\bs begin}                                                                       \\
\LL {\bs for} i:= 1 {\bs to} ubound(a) {\bs do}                                 \\
\LL {\bs begin}                                                                 \\
\LL\LL x:= a[i];                                                             \\
\LL\LL {\bs if} (diam(x) $<$$>$ 0) {\bs then}                                    \\
\LL\LL\LL a[i] := (1+eps)$*$x $-$ eps$*$x                                \\
\LL\LL {\bs else}                                                            \\
\LL\LL\LL a[i] := intval( pred (inf(x)), succ (sup(x)) );                \\
\LL {\bs end;} \{for\}                                                    \\
\LL                                                                       \\
\LL  inf\/l := a;                                                           \\
{\bs end}; \LL \{operator inf\/lated\}                                                   \\
\LL                                                                       \\
\LL \\
\{- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -\} \\
\LL                                                          \\
\newpage
{\bs function} approximate\_inverse (A: rmatrix): rmatrix[1..ubound(A),1..ubound(A)];\\
\LL                                                                       \\
\begin{tabular}{rll}
 \{~ & Computation of an approximate inverse of the (n,n)-Matrix A & ~\}\\
 \{~ & by application of the Gaussian elimination method.          & ~\}\\
\end{tabular}\\
\LL                                                                       \\
{\bs var}                                                                   \\
\begin{tabular}{lll}
\LL  i, j, k, n     & ~:~ &  integer;                                          \\
\LL  factor         & ~:~ &  real;                                             \\
\LL  R, Inv, E      & ~:~ &  rmatrix[1..ubound(A),1..ubound(A)];               \\
\end{tabular}\\
\LL                                                                       \\
{\bs begin}                                                                       \\
\LL  n := ubound(A); \LL \{ dimension of A \}                                  \\
\LL                                                                       \\
\LL  E := id(E); \LL \{ identity matrix \}             \\
\LL  R := A;                                                        \\
\LL                                                                       \\
\begin{tabular}{rll}
\LL\{~ & Gaussian elimination step with unit vectors as    & ~\}  \\
\LL\{~ & right-hand sides. Division by R[i,i]=0 indicates  & ~\}  \\
\LL\{~ & a probably singular matrix A.                     & ~\}  \\
\end{tabular}\\
\LL                                                                       \\
\LL    {\bs for} i:= 1 {\bs to} n {\bs do}                                             \\
\LL\LL      {\bs for} j:= (i+1) {\bs to} n {\bs do}                                  \\
\LL\LL      {\bs begin}                                                  \\
\LL\LL\LL        factor := R[j,i]/R[i,i];                         \\
\LL\LL\LL        {\bs for} k:= i {\bs to} n {\bs do} R[j,k] := \#$*$(R[j,k] $-$ factor$*$R[i,k]);             \\
\LL\LL\LL        E[j] := E[j] $-$ factor$*$E[i];                      \\
\LL\LL      {\bs end}; \LL \{for j:= ...\}                                    \\
\LL                                                                       \\
\begin{tabular}{rll}
\LL\{~ & Backward substitution delivers the rows of the inverse of A.  & ~\} \\
\end{tabular}\\
\LL                                                                       \\
\LL    {\bs for} i:= n {\bs downto} 1 {\bs do}                                         \\
\LL\LL      Inv[i] := \#$*$(E[i] $-$ {\bs for} k:= (i+1) {\bs to} n {\bs sum}(R[i,k]$*$Inv[k]))/R[i,i];\\
\LL                                                                       \\
\LL  approximate\_inverse := Inv;                                        \\
{\bs end}; \LL \{function approximate\_inverse\}                                     \\
\LL                                                                       \\
\{- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -\}\\
\LL                                                         \\
\newpage
\begin{tabular}{ll}
{\bs global procedure} linear\_system\_solver~ & (A : rmatrix; b : rvector;    \\
                                      &  {\bs var} x : ivector; {\bs var} ok : boolean);\\
\end{tabular}\\
\LL                                                                       \\
\begin{tabular}{rll}
 \{~ & Computation of a verified inclusion vector for the solution of the &  ~\} \\
 \{~ & linear system of equations. If an inclusion is not achieved after  &  ~\} \\
 \{~ & a certain number of iteration steps the algorithm is stopped and   &  ~\} \\
 \{~ & the parameter ok is set to false.                                  &  ~\} \\
\end{tabular}\\
\LL                                                                       \\
{\bs const}                                                                 \\
\begin{tabular}{llllll}
\LL  epsilon      & ~=~ &  0.25; & ~\{~ & Constant for the epsilon inflation & ~\} \\
\LL  max\_steps & ~=~ &  10;   & ~\{~ & Maximum number of iteration steps  & ~\} \\
\end{tabular}\\
\LL                                                                       \\
{\bs var}                                                                   \\
\begin{tabular}{lll}
\LL  i      & ~:~ &  integer;                     				    \\
\LL  y, z   & ~:~ &  ivector[1..ubound(A)];                                    \\
\LL  R      & ~:~ &  rmatrix[1..ubound(A),1..ubound(A)];                       \\
\LL  C      & ~:~ &  imatrix[1..ubound(A),1..ubound(A)];                       \\
\end{tabular}\\
\LL                                                                       \\
{\bs begin}                                                                       \\
\LL  R := approximate\_inverse(A);                                       \\
\LL                                                                       \\
\begin{tabular}{rll}
\LL\{~ & R$*$b is an approximate solution of the linear system and z is an inclusion & ~\}    \\
\LL\{~ & of this vector. However, it does not usually include the true solution. & ~\}    \\
\end{tabular}\\
\LL                                                                       \\
\LL  z := \#\#(R$*$b);                                                       \\
\LL                                                                       \\
\begin{tabular}{rll}
\LL\{~ & An inclusion of ~I $-$ R$*$A~ is computed with maximum accuracy. & ~\}\\
\LL\{~ & The (n,n) identity matrix is generated by the function call id(A).   & ~\}\\
\end{tabular}\\
\LL                                                                       \\
\LL  C := \#\#(id(A) $-$ R$*$A);                                             \\
\LL                                                                       \\
\LL  x := z; \LL i := 0;                                               \\
\LL  {\bs repeat}                                                        \\
\begin{tabular}{rlll}
\LL\LL    i & ~:=~ & i + 1;   &                                         \\
                &      &          &             			    \\
\LL\LL    y & ~:=~ & x inf\/lated epsilon;~ &
                      \begin{tabular}[t]{rll}
                         \{~ & To obtain a true inclusion the interval & ~\}  \\
                         \{~ & vector c is slightly enlarged.          & ~\}  \\
                      \end{tabular}                                         \\
            &      &               &                                     \\
\LL\LL    x & ~:=~ & z + C$*$y;    & \{ The new iterate is computed. \} \\
            &      &               &                \\
\LL\LL   ok & ~:=~ & x {\bs in} y; & \{ Is c contained in the interior of y? \}\\
            &      &               &                                       \\
\end{tabular} \\
\LL  {\bs until} ok {\bs or} (i = max\_steps);                           \\
{\bs end}; \LL \{procedure linear\_system\_solver\}                  \\
\LL \\
\{- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -\} \\
\LL \\
{\bs end}. \LL \{module lin\_solv\}
%
\end{flushleft}
%
%
\newpage
\section*{Appendix\label{app}}
%
\subsection*{Review of Real and Complex \#-Expressions}
%
\begin{center}
\footnotesize
\mbox{~}\\
{\normalsize Syntax:  ~~~~\#-Symbol  ( Exact Expression )}\\[2ex]
\begin{tabular}{|c||l|c|}
\hline
\#-Symbol  & Result Type & Summands Permitted in the Exact Expression \\
\hline
\hline
\#           &{\sl dotprecision} &\parbox{0.6\tewi}{\begin{itemize}
                              \item {variables, constants, and
                                    special function calls of
                                    type {\sl integer},
                                    {\sl real}, or {\sl dotprecision}}
                              \item {products of type {\sl integer} or
                                    {\sl real}}
                              \item {scalar products of type {\sl real\/}}
                              \end{itemize}} \\
\hline
             &{\sl real} &\parbox{0.6\tewi}{\begin{itemize}
                             \item  {variables, constants, and special
                                    function calls of
                                    type {\sl integer},
                                    {\sl real}, or {\sl dotprecision}}
                             \item  {products of type {\sl integer} or
                                    {\sl real}}
                             \item  {scalar products of type {\sl real\/}}
                             \end{itemize}}\\
\cline{2-3}
             &{\sl complex} &\parbox{0.6\tewi}{\begin{itemize}
                            \item  {variables, constants, and special
                                   function calls of
                                   type {\sl integer},
                                   {\sl real}, {\sl complex}, or
                                   {\sl dotprecision}}
                            \item  {products of type {\sl integer}, {\sl real}, or
                                   {\sl complex}}
                            \item  {scalar products of type {\sl real\/}
                                   or {\sl complex}}
                            \end{itemize}}\\
\cline{2-3}
\begin{tabular}{c}
  \#$*$\\
  \#$<$\\
  \#$>$
\end{tabular}
               &{\sl rvector}&\parbox{0.6\tewi}{\begin{itemize}
                            \item  {variables and special function calls
                                   of type {\sl rvector}}
                            \item  {products of type {\sl rvector}
                                   (\eg {\sl rmatrix} $*$
                                   {\sl rvector}, {\sl real} $*$ {\sl rvector} etc.)}
                            \end{itemize}}\\
\cline{2-3}
               &{\sl cvector} &\parbox{0.6\tewi}{\begin{itemize}
                            \item  {variables and special function calls
                                   of type {\sl
                                   rvector} or {\sl cvector}}
                            \item  {products of type {\sl rvector} or
                                   {\sl cvector} (\eg
                                   {\sl cmatrix} $*$
                                   {\sl rvector}, {\sl real} $*$
                                   {\sl cvector} etc.)}
                            \end{itemize}}\\
\cline{2-3}
               &{\sl rmatrix} &\parbox{0.6\tewi}{\begin{itemize}
                            \item  {variables and special function calls
                                   of type {\sl
                                   rmatrix}}
                            \item  {products of type {\sl rmatrix}}
                            \end{itemize}}\\
\cline{2-3}
               &{\sl cmatrix} &\parbox{0.6\tewi}{\begin{itemize}
                            \item  {variables and special function
                                   calls of type {\sl
                                   rmatrix} or {\sl cmatrix}}
                            \item  {products of type {\sl rmatrix} or
                                   {\sl cmatrix}}
                            \end{itemize}}\\
\hline
\end{tabular}%
%
\end{center}
%
\newpage
%
\subsection*{Review of Real and Complex Interval \#-Expressions}
%
\begin{center}
\footnotesize
\mbox{~}\\
{\normalsize Syntax:  ~~~~\#\# ( Exact Expression )}\\[2ex]
\begin{tabular}{|c||l|c|}
\hline
\#-Symbol & Result Type & Summands Permitted in the Exact Expression\\
\hline
\hline
             &{\sl interval} &\parbox{0.6\tewi}{\begin{itemize}
                            \item  {variables, constants, and special
                                   function calls of
                                   type {\sl integer},
                                   {\sl real}, {\sl interval}, or
                                   {\sl dotprecision}}
                            \item  {products of type {\sl integer},
                                   {\sl real}, or {\sl
                                   interval}}
                            \item  {scalar products of type {\sl real} or
                                   {\sl interval}}
                            \end{itemize}}\\
\cline{2-3}
             &{\sl cinterval} &\parbox{0.6\tewi}{\begin{itemize}
                            \item  {variables, constants, and special
                                   function calls of
                                   type {\sl integer},
                                   {\sl real}, {\sl complex},
                                   {\sl interval}, {\sl cinterval}, or
                                   \mbox{\sl dotprecision}}
                            \item  {products of type {\sl integer},
                                   {\sl real}, {\sl
                                   complex}, {\sl interval}, or
                                   {\sl cinterval}}
                            \item  {scalar products of type {\sl real},
                                   {\sl complex},
                                   {\sl interval}, or {\sl cinterval}}
                            \end{itemize}}\\
\cline{2-3}
\#\#         &{\sl ivector} &\parbox{0.6\tewi}{\begin{itemize}
                            \item  {variables and special function
                                   calls of type {\sl
                                   rvector} or {\sl ivector}}
                            \item  {products of type {\sl rvector} or
                                   {\sl ivector}}
                            \end{itemize}}\\
\cline{2-3}
             &{\sl civector}&\parbox{0.6\tewi}{\begin{itemize}
                            \item  {variables and special function
                                   calls of type {\sl
                                   rvector}, {\sl cvector}, {\sl ivector},
                                   or {\sl civector}}
                            \item  {products of type {\sl rvector},
                                   {\sl cvector}, {\sl
                                   ivector}, or {\sl civector}}
                            \end{itemize}}\\
\cline{2-3}
             &{\sl imatrix} &\parbox{0.6\tewi}{\begin{itemize}
                            \item  {variables and special function
                                   calls of type {\sl
                                   rmatrix} or {\sl imatrix}}
                            \item  {products of type {\sl rmatrix} or
                                   {\sl imatrix}}
                            \end{itemize}}\\
\cline{2-3}
             &{\sl cimatrix} &\parbox{0.6\tewi}{\begin{itemize}
                            \item  {variables and special function
                                   calls of type {\sl
                                   rmatrix}, {\sl cmatrix},
                                   {\sl imatrix}, or {\sl cimatrix}}
                            \item  {products of type {\sl rmatrix},
                                   {\sl cmatrix}, {\sl
                                   imatrix}, or \mbox{\sl cimatrix}}
                            \end{itemize}}\\
\hline
\end{tabular}%
%
\end{center}
%
\newpage
