\documentstyle[IEEEtran]{article}
\begin{document}
\tolerance 10000
\title{Linear Algebraic Equations in Kaucher Arithmetic}
\author{A. V. Lakeyev}

\pagestyle{myheadings}

\markright{APIC'95, El Paso,
Extended Abstracts,
A Supplement to the international journal of {\rm Reliable
Computing}\ \ \ \ \ \ \ \ \ \ \  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\ \ \ \ \ \ \ \ \ \ \ \ \ }

\maketitle

\auffil{The author is with 
Irkutsk Computing Center, Russian Academy of Science, 
Siberian Division, Lermontov Str.134, Irkutsk 664033, Russia,
email lakeyev@icc.ccsoan.irkutsk.su.}

\begin{abstract}
S. P. Shary \cite{1} and L.~V.~ Kupriyanova \cite{2}
have proven that an
algebraic interval solution of linear equation in Kaucher's extended
arithmetic allows us to obtain maximal interval estimates
for various sets of solutions of interval linear algebraic systems 
(namely, for united, tolerable, controlled, and some
other solution
sets; for definitions, see \cite{1}). 

   In this paper, we derive a 
special analytical representation of interval
product in Kaucher's arithmetic \cite{3,4} 
in terms of lattice
operations (i.e., positive and negative parts, module, least upper bound),
and we use this representation to 
formulate numerical (non-interval) equations that are equivalent to
linear interval equations. 

For several interesting classes of interval linear equations, 
this reformulation enables us 
to reduce these equations to 
equations of
the type $x=M\vert x\vert + a$ that 
have been studied earlier by J. Rohn \cite{5,6}. 

This reformulation also 
enable us to prove that for these classes, 
the problem of checking whether a given interval linear 
system has a solution is
NP-complete.
\end{abstract}

\section{Kaucher Arithmetic (Extended Interval Arithmetic): 
Definitions and Denotations}
Let us first recall the basic notions of Kaucher arithmetic.

\begin{itemize}
\item The main objects of Kaucher arithmetic are pairs of real numbers that
are called {\it extended intervals}. A pair consisting of real
numbers $a$ and $b$ is denoted by $[a,b]$.
\item The set of all such intervals
is denoted by 
$$I^*(R)=\{ [ \underline{x}, \overline{x} ] \; \vert \;
\underline{x}, \overline{x} \in R \}$$
(in this
paper, we will
use notations from \cite{4}). 
\item Intervals for which $a\le b$ are called {\it proper intervals}. The
set of all proper intervals is denoted by 
$$ I(R)=\{ [ \underline{x}, \overline{x} ] \; \vert \;
\underline{x} \leq \overline{x}, \;
\underline{x}, \overline{x} \in R \}.$$
\end{itemize}

In this paper, we will (as usual in interval arithmetic) 
identify $x \in R$ with an
interval $[x,x]$, and thus assume that $$R \subset I(R).$$ 

The following are the basic operations of Kaucher arithmetic. By $*$,
let us denote any operation from the set $\{+,-,\cdot\}$. 
Let $ {\rm x} = [ \underline{x}, \overline{x} ]\in I^*(R)$, 
${\rm y} = [ \underline{y}, \overline{y} ] \; \in I^*(R)$, and
let $\{ {\rm x_i} \}_{i \in J}$ is an bounded set of extended
intervals 
$ {\rm x}_i = [ \underline{x}_i, \overline{x}_i ] \in I^*(R)$.
Then:
\begin{itemize}
\item $dual({\rm x}) = [ \overline{x}, \underline{x} ]$

\item $
pro({\rm x}) := {\rm if \; x \; proper \; then \; x, \; else} \;
dual({\rm x});$

\item 
$${\bf sup}\{ {\rm x}_i \; \vert \; i \in J \} =$$
$$ [\inf\{ \underline{x}_i
\; \vert \;
i \in J \}, \sup\{ \overline{x}_i \; \vert \; i \in J \} ];$$

\item $${\bf inf}\{ {\rm x}_i \; \vert \; i \in J \} =$$
$$ [ \sup\{ \underline{x}_i
\; \vert \;
i \in J \}, \inf\{ \overline{x}_i \; \vert \; i \in J \}];$$

\item $\Omega ^ {\rm x} ({\rm t}) := {\rm if \; x \; proper 
\; then \; t, \; else \;}
dual({\rm t});$

\item $
{\rm x}*{\rm y} = \Omega ^ {\rm x} (\Omega ^ {\rm y}  (\{ x*y \; \vert  \;
x \in pro({\rm x}),y \in pro({\rm y})\})).$
\end{itemize}

In this paper, we will also use the following denotations for
operations with real numbers $x$ and $y$:
\begin{itemize}
\item $x^+ = max\{ x,0 \}$;
\item $x^- = max\{ -x,0 \}$;
\item $x \vee y = max\{ x,y\}$.
\end{itemize}

\section{Interval Product in $I^*(R)$} 

\noindent {\bf THEOREM 1.} {\it For any
$ {\rm x} = [ \underline{x}, \overline{x} ]\in I^*(R)$ and for any 
${\rm y} = [ \underline{y}, \overline{y} ]\in I^*(R)$,
the following equality holds:
$${\rm x \cdot y} =$$ $$[
(\underline{x}^+\underline{y}^+)\vee (\overline{x}^-\overline{y}^-)
-
(\overline{x}^+\underline{y}^-)\vee (\underline{x}^-\overline{y}^+),$$
$$(\overline{x}^+\overline{y}^+)\vee (\underline{x}^-\underline{y}^-)
-
(\underline{x}^+\overline{y}^-)\vee (\overline{x}^-\underline{y}^+)
]. \eqno{(1)}$$}
\medskip

If we know how many of the two intervals (if any) are proper, then we can
simplify the formula (1):
\newpage
  
\noindent {\bf THEOREM 2.} {\it Let ${\rm x, y} \in I^*(R)$. Then:
\begin{itemize}
\item[1)] if both intervals $\rm x$ and $\rm y$ are proper, then 
$$
{\rm x \cdot y} = [
\underline{x}^+\underline{y}^+ + \overline{x}^-\overline{y}^-
-
(\overline{x}^+\underline{y}^-)\vee (\underline{x}^-\overline{y}^+)
,$$
$$(\overline{x}^+\overline{y}^+)\vee (\underline{x}^-\underline{y}^-)
-
\underline{x}^+\overline{y}^- - \overline{x}^-\underline{y}^+
], \eqno{(2)}
$$  
\item[2)] if neither $\rm x$, nor $\rm y$ is proper, then 
$$
{\rm x \cdot y} = [
(\underline{x}^+\underline{y}^+)\vee (\overline{x}^-\overline{y}^-)
-
\overline{x}^+\underline{y}^- - \underline{x}^-\overline{y}^+
,$$ $$
\overline{x}^+\overline{y}^+ + \underline{x}^-\underline{y}^-
-
(\underline{x}^+\overline{y}^-)\vee (\overline{x}^-\underline{y}^+)
], \eqno{(3)}
$$
\item[3)] if one of the intervals $\rm x$, $\rm y$ 
is proper, and another one is
not proper, then
$$
{\rm x \cdot y} = [
\underline{x}^+\underline{y}^+ + \overline{x}^-\overline{y}^-
-
\overline{x}^+\underline{y}^- - \underline{x}^-\overline{y}^+
,$$ $$
\overline{x}^+\overline{y}^+ + \underline{x}^-\underline{y}^-
-
\underline{x}^+\overline{y}^- - \overline{x}^-\underline{y}^+
]. \eqno{(4)}
$$\end{itemize}}
\medskip
  
\section{Linear Equations in $I^*(R^n)$} 
Let us fix integers $m$ and $n$. 
\begin{itemize}
\item By
$I^*(R^n)$ and $I^*(R^{m \times n})$, we will denote 
the sets of $n$-dimensional
vectors and of $m \times n$ matrixes with elements from $I^*(R)$,
\item y $I(R^n)$ and $I(R^{m \times n})$
we denote
the sets of $n$-dimensional
vectors and of $m \times n$ matrixes with elements from $I(R)$.
\item In the following text:
\begin{itemize}
\item[$\bullet$]
$ {\bf A} = [ \underline{A},\overline{A} ]$ will denote an (extended)
interval matrix (from $I^*(R^{m \times n})$), and
\item[$\bullet$]
${\bf b} = [ \underline{b},\overline{b}]$ will denote an extended
interval vector (from $I^*(R^m)$).
\end{itemize}
\end{itemize}
  
We consider the linear algebraic equation
$$ {\bf Ax = b}, \eqno{(5)}$$
where
${\bf x} = [\underline{x},\overline{x} ] \in I^*(R^n),$
and the product of the matrix {\bf A} and the vector {\bf x} is
defined in the usual way,
through the addition and multiplication in $I^*(R)$.

We will also need some denotations for real-valued vectors and
matrices:
\begin{itemize}
\item On real-valued vectors and matrices, 
operations $ +, -, {}^+, \; {}^-, \, \vee $, and 
$\vert \cdot \vert$ mean component-wise operations. 
\begin{itemize}
\item[]
For example, if
$A$ is a matrix with components $A_{ij}$, then $|A|$denotes the matrix
with components $|A_{ij}|$. 
\end{itemize}
\item For an arbitrary vector $x$, $diag(x)$ will denote a diagonal matrix
whose diagonal is the vector $x$. 
\item $e^n=(1,...,1)\in R^n$ will denote a
vector with all components equal to 1.
\end{itemize}
\medskip
  
\noindent {\bf THEOREM 3.} {\it If
$ {\bf A}{\bf x} = [\underline{{\bf A}{\bf x}} \;,\;
\overline{{\bf A}{\bf x}} ]  $ then}
$$
\overline{{\bf A}{\bf x}} =(\overline{A}^+ diag(\overline{x}^+)
\lor
\underline{A}^- diag(\underline{x}^-)e^n-$$
$$(\underline{A}^+ diag(\overline{x}^-)
\lor
\overline{A}^- diag(\underline{x}^+) )e^n,
\eqno{(6)}
$$
$$
\underline{{\bf A}{\bf x}} =(\underline{A}^+ diag(\underline{x}^+)
\lor
\overline{A}^- diag(\overline{x}^-)e^n-$$
$$\overline{A}^+ diag(\underline{x}^-)
\lor
\underline{A}^- diag(\overline{x}^+) )e^n.
\eqno{(7)}
$$
\medskip

If we equate the expressions from the right-hand sides of equations 
(6) and (7) with $ \overline{b} $
and  $\underline{b}$ respectively, we will get the explicit form of
the interval system of equations (5).
If we replace $a \vee b$ by $(1/2)\cdot(a+b-|a-b|)$, and use matrix
notations, then this representation can be reformulated as follows:
\medskip
  
\noindent{\bf THEOREM 4.} {\it The vector
${\bf x} = [ \underline{x} \;,\; \overline{x} ] \in I^*(R^n) $
is a solution to the equation (5) iff}
$$
\pmatrix{
\overline{A}^+ & \underline{A}^- \cr
\underline{A}^- & \overline{A}^+ }
{\pmatrix{
\overline{x} \cr
-\underline{x} }}^+
- 
\pmatrix{
\underline{A}^+ & \overline{A}^- \cr
\overline{A}^- & \underline{A}^+ }
{\pmatrix{
\overline{x} \cr
-\underline{x} }}^-
+ $$ $$
\left\vert
\pmatrix{
\overline{A}^+ & -\underline{A}^- \cr
-\underline{A}^- & \overline{A}^+ }
{\pmatrix{
diag(\overline{x}) \cr
diag(-\underline{x}) }}^+
\right\vert
%\right. 
e^n
- $$ $$
\left.
\left\vert
 \pmatrix{
\underline{A}^+ & -\overline{A}^- \cr
-\overline{A}^- & \underline{A}^+ }
{\pmatrix{
diag(\overline{x}) \cr
diag(-\underline{x}) }}^-
\right\vert
\right.
e^n = $$ $$2 \;
\pmatrix{
\overline{b} \cr
-\underline{b} }. \eqno{(8)}
$$
\medskip
  
If $ {\bf A} \in I(R^{m \times n})$ or  $dual({\bf A}) \in I(R^{m \times n})$,
then we can replace one of $\vee$ by + in the formulas (6),(7), and get rid of
one of the terms in (8) by using Theorem 2.
  
The system (8) can be further simplified if 
$ dual({\bf A}) \in I(R^{m \times n})$,
and we are interested in a solution ${\bf x} \in I(R^n)$ (as  shown 
in \cite{1,2}, in this case ${\bf x}$ is an inner estimate of the united set
of solutions of the corresponding interval system):
\medskip
  
\noindent {\bf THEOREM 5.} {\it If $ dual({\bf A}) \in I(R^{m \times n})$,
then ${\bf x} \in I(R^n)$ is a solution of (5) iff}
$$
\pmatrix{
\overline{A}^+ & \underline{A}^- \cr
\underline{A}^- & \overline{A}^+ }
{\pmatrix{
\overline{x} \cr
-\underline{x} }}^+
\;\; - \;\;
\pmatrix{
\underline{A}^+ & \overline{A}^- \cr
\overline{A}^- & \underline{A}^+ }
{\pmatrix{
\overline{x} \cr
-\underline{x} }}^-
=$$ $$
\pmatrix{
\overline{b} \cr
-\underline{b} }.
\eqno{(9)}
$$
\medskip
\newpage
  
By introducing denotations
$$C^+ = {1 \over 2}( \overline{A}^+ + \underline{A}^+ ), \;\;
C^- = {1 \over 2}( \underline{A}^- + \overline{A}^- ),$$
$$D^+ = {1 \over 2}( \overline{A}^+ - \underline{A}^+ ), \;\;
D^- = {1 \over 2}( \underline{A}^- - \overline{A}^- ),$$
we can represent the system (9) in the following form
$$
\pmatrix{
C^+ & C^- \cr
C^- & C^+ }
\pmatrix{
\overline{x} \cr
-\underline{x} }
\;\; + \;\;
\pmatrix{
D^+ & D^- \cr
D^- & D^+ }
\left\vert \;
\pmatrix{
\overline{x} \cr
-\underline{x} } \;
\right\vert
=$$ $$
\pmatrix{
\overline{b} \cr
-\underline{b} }.
\eqno{(10)}
$$
  
Such system have been thoroughly analyzed by 
J. Rohn \cite{5} (see also \cite{6}). In particular, by
using the concept of ``nonexpanding matrix" and 
Theorem 6.1.5 from \cite{6},
we can prove the following statement. Let us denote:
$$
\tilde{C} =
\pmatrix{
C^+ & C^- \cr
C^- & C^+ }, \;\;
\tilde D =
\pmatrix{
D^+ & D^- \cr
D^- & D^+ },$$
$$C = {1 \over 2}( \overline{A} + \underline{A} ), \;\;
C_0 = {1 \over 2}( \vert \underline{A} \vert + \vert \overline{A} \vert ), \;\;
$$
$$
D = {1 \over 2}( \overline{A} - \underline{A} ), \;\;
D_0 = {1 \over 2}( \vert \overline{A} \vert - \vert \underline{A} \vert ).
$$
\medskip
  
\noindent {\bf THEOREM 6.} {\it 
Let $m=n$, $C$ and $C_0$ be nonsingular matrixes (this condition 
is equivalent
to nonsingularity of $\tilde{C}$), and let ${\tilde{C}}^{-1}\tilde{D}$ be
nonexpanding. Then, the equation (10) has a unique solution for every
$\overline{b},\underline{b} $. If, in addition,
$ C^{-1}_0 D \leq {\bf 0} $, and
$\overline{b}, \underline{b} $ satisfy
the inequality 
$C_0^{-1} \overline{b} \geq C_0^{-1} \underline{b} $, then this solution
belongs to $I(R^n)$.}
\medskip

We note that here, 
$$
{\tilde{C}}^{-1} = {1 \over 2}
\pmatrix{
C^{-1}_0 + C^{-1} & C^{-1}_0 - C^{-1} \cr
C^{-1}_0 - C^{-1} & C^{-1}_0 + C^{-1} },$$
$${\tilde{C}}^{-1}\tilde{D} = {1 \over 2}
\pmatrix{
C^{-1}_0 D + C^{-1} D_0 & C^{-1}_0 D - C^{-1} D_0 \cr
C^{-1}_0 D - C^{-1} D_0 & C^{-1}_0 D + C^{-1} D_0 }.
$$
  
It is interesting to mention that, in addition to the above-described
case, the equation (8) can be 
transformed into an equivalent form (10) in
the following two additional cases: 
\begin{itemize}
\item[1)] when $ {\bf A} \in I(R^{m \times n})$ and 
$dual({\bf x}) \in I(R^n)$; 
\item[2)] when ${\underline{a}}_{ij}{\overline{a}}_{ij} \geq 0 $
for all $i,j$ (where ${\underline{a}}_{ij}$ and ${\overline{a}}_{ij}$ are the
elements of the matrices $\underline{A}$ and $\overline{A}$).
\end{itemize}
In these cases, we can prove results similar to Theorem 6.
  
\section{NP-completeness} 
Let us define a special class of interval equations (5). We will say
that an equation (5) belong to the class $E$ if all of the following
conditions are satisfied:
\begin{itemize}
\item $m=n$;
\item matrixes and vectors are integer-valued;
\item $\underline{A} \geq {\bf 0}$, 
$\overline{A} \geq {\bf 0},$ and 
$\overline{b} \geq \underline{b} $;
\item the matrix 
$C = {1 \over 2}( \overline{A} + \underline{A} )$ is nonsingular;
\item the number of solutions of (5) is finite 
(e.g., is bounded by $\leq 2^{n+1} $).
\end{itemize}
  
Due to the above conditions, the equation (5) is equvalent to (10) and,
moreover,
$$ C^+ = C, \;\; D^+ = D, \;\; C^- = D^- = {\bf 0}. $$
Then, the equations (10) can be further simplified, into the following
system:
$$\left \{
\matrix{
C \overline{x} + D \vert \overline{x} \vert = \overline{b}, \cr
C \underline{x} = D \vert \underline{x} \vert + \underline{b}.
}
\right.\eqno{(11)}
$$
  
If we are looking for a solution 
that belongs to $I(R^n)$ 
(i.e., for which ${\bf x} = [ \underline{x},\overline{x} ] \in I(R^n)$),
then we must add the cooresponding inequality 
$$\underline{x} \leq \overline{x}.
\eqno{(12)}$$
to the equations (11). \medskip
  
\noindent {\bf THEOREM 7.}
{\it On the class $E$, the following problems are NP-complete:
\begin{itemize}
\item Checking whether a given system has an extended interval
solution (i.e., a solution 
from the set $I^*(R^n)$).
\item Checking whether a given system has a proper interval
solution (i.e., a solution 
from the set $I(R^n)$).
\end{itemize}
Both problems remain NP-complete if we restrict the class of problems
by additionally imposing one of the following two conditions:
$$\underline{A} \geq \overline{A} \geq {\bf 0}$$ or
$$\overline{A} \geq \underline{A} \geq {\bf 0}.$$}
  
\noindent{\it Comments.}
It is interesting to notice that if
we impose an additional condition $\overline{A} \geq \underline{A}$
(that makes an interval matrix $\bf A$ proper), and if we are looking 
looking for proper solutions ${\bf x}\in I(R^n)$, then the problem (5)
becomes equivalent to 
to the problem of finding a solution of an 
linear interval system of equations \cite{7}
in classical interval arithmetic. 

If, instead of the condition
$\overline{A} \geq \underline{A}$, we impose the condition 
$\underline{A} \geq \overline{A}$, then the problem of finding a
proper solution corresponds to a problem of finding,
using the equation (5), of inner interval estimate of the united set of
solution \cite{1}. This problem is thus also proven to be NP-complete.
\medskip

As a corollary, we obtain the following result:
\medskip

\noindent{\bf COROLARY.} {\it 
Solvability problem for equations of the form
$$\tilde{C} \tilde{x} = \tilde{D} \vert \tilde{x} \vert + \tilde{b}$$
with a nonsingular matrix  $\tilde{C}$ and
$\tilde{C} \geq \tilde{D} \geq {\bf 0}$ is NP-complete.}
\medskip

\noindent{\it Comment.} This corollary solves an open problem that has
been previously formulated
by J. Rohn \cite{pr}.
\medskip

\noindent{\bf Idea of the Proof of Theorem 7.}
The proof of results from Theorem 7 is done by formulating a 
polynomial reducibility of
the problem PARTITION to the problems, formulated in this Theorem.

\begin{thebibliography}{99}
  
\bibitem{4}    
 E. Gardenes and A. Trepat, ``Fundamentals of SIGLA, an interval computing
system over the completed set of intervals,'' {\it Computing}, 1980,
Vol. 24, pp. 161--179.

\bibitem{3}    
E. Kaucher, ``Interval analysis in the extended interval spase {\bf IR}'',
{\it Computing}, Suppl. 2, 1980, pp.33--49.

\bibitem{2}
L. V. Kupriyanova, ``Inner estimation of the united solution set to
interval linear algebraic system,''
{\it Interval Computation}, 1995 (to appear).

\bibitem{6}    
A. Neumaier, {\bf Interval Methods for Systems of Equations}, Cambridge
University Press, Cambridge, 1989.
  
\bibitem{7}  
 M. Ratschek and W. Sauer, ``Linear Interval Equations'', {\it Computing},
1982, Vol. 28, pp. 105--115.

\bibitem{5}    
J. Rohn, ``Systems of Linear Interval Equations'', {\it Linear Algebra Appl.},
1989, Vol. 126, pp. 39--78.

\bibitem{pr} J. Rohn, Private communication.

\bibitem{1}  
S. P. Shary, ``Algebraic approach to interval linear static identification,
tolerance and control problems, or One more application of Kaucher
arithmetic,''
{\it Interval Computations}, 1995 (to appear).

\end{thebibliography}
\end{document}