% lnummat.dem
% LaTeX package LJour1 1.0: demo file for Numerische Mathematik
% (c) Springer-Verlag HD
%----------------------------------------------------------------------
%
% customization
\documentstyle[bibay,leqno]{pljour1}
\journalname{Numerische Mathematik} % State name of journal
\renewcommand{\subclassname}
{{\it Mathematics Subject Classification (1991):\/}}
\newcommand{\DXDYCZ}[3]{\left( \frac{ \partial #1 }{ \partial #2 }
\right)_{#3}}
% end of customization
%
\begin{document}
%
\title{ Optimality relationships for $p$-cyclic
SOR\thanks{Research supported in part by the US Air Force under
grant no. AFOSR-88-0285 and the National Science Foundation under
grant no. DMS-85-0285.}\fnmsep\thanks{Second footnote.}}
\subtitle{A demonstration text}
\author{Daniel J. Pierce\inst{1} \and Apostolos
Jadjidimos\inst{2}\fnmsep\thanks{{\it Present address:\/} Department
of Computer Science, Purdue University, West Lafayette, IN 47907, USA.}
\and Robert J. Plemmons\inst{3}}
\mail{R. Plemmons}
\titlerunning{Optimality relationships for $p$-cyclic SOR}
\authorrunning{D. J. Pierce et al.}
\institute{Boeing Computer Service, P.O. Box 24346, MS 7L-21,
Seattle, WA 98124-0346, USA \and
Department of Mathematics, University of Ioannina, GR-45 1210
Ionnanina, Greece \and
Department of Computer Science and Mathematics, North Carolina
State University, \\
Raleigh, NC 27695-8205, USA}
\date{Received January 20, 1992}
\maketitle
\begin{abstract}
The optimality question for block $p$-cyclic matrix into a block
$q$-cyclic form, $q < p$, results in asymptotically faster SOR
convergence for the same amount of work per iteration. As a
consequence block 2-cyclic SOR is optimal under these conditions.
\end{abstract}
\subclass{65N30}
\section{Introduction}
This text was compiled to demonstrate the use of the Springer
\LaTeX\ macropackages {\em LJour1\/} for one-column journals.
Please refer to \cite{leslie} for general information on coding \LaTeX{}
and to the \cite{springer} for information concerning the Springer
layout.
Parts of this ``article" were taken from different real articles, but
may have been changed to show a special feature of a macro.
\section{Notation}
Here are a few examples of how to use special fonts. Vectors are denoted
by boldface letters: $\vec V,\; \vec W$. Tensors are denoted by sans
serif letters: $\tens{A, B}$. If no tensors are needed, sans serif
letters may be reserved for other purposes. Vector spaces may be denoted
by gothic letters: $\frak{G, H}$. Sets of functions are denoted by
script letters: ${\cal W}_i,{\cal F}$. Sets of numbers are denoted by
special roman letters ${\Bbb R}, {\Bbb C}$.
You are of course (within limits) free to design your own notation but
sticking to conventions makes your article easier for others to read.
\section{Preliminaries}
Let us state a few well known results and demonstrate how to typeset
lists. The functions $f$ and $g$ of (1) and (2) fulfill the following
assumptions:
\begin{enumerate}
\item $f: B_f \subset {\Bbb R}^n \times {\Bbb R}^n \times [a,b] \to
{\Bbb R}^n$ \\
$f^\prime _x$, $f^\prime_y$ exist and are continous
\item ker$(f^\prime _y (y, x, t)) = N (t)\quad \forall (y, x, t)
\in B_f$ \\
${\rm rank} (f^\prime _y (y, x, t)) = r$ \\
${\rm dim} (N (t)) = n - r$
\item $Q(t)$ denotes a projection onto $N(t)$ \\
$Q$ is smooth and $P(t) := I - Q (t)$
\item The matrix $G (y, x, t) := f^\prime _y (y, x, t) + f^\prime
_x (y, x, t) Q (t)$ is nonsingular \\
$\forall (y, x, t) \in B_f$\quad (i.e. (1) is transferable)
\item $g: B_g \subset {\Bbb R}^n \times {\Bbb R}^n \to M \subset
{\Bbb R}^n$ \\
$g^\prime _{x_a} , g^\prime _{x_b}$ exist and are continuous\\
${\rm im} (g^\prime _{x_a} , g^\prime _{x_b}) =: M$
\end{enumerate}
Now we give another example of a list with changed indentation.
\begin{description}[Shoot.]
\item[Shoot.]
Collocation methods for this type of equations are considered. Shooting
and difference methods for linear, {\em solvable} DAE's, also with
higher index, are treated in \cite{wendl} under the assumption that
consistent initial values can be calculated and a stable integration
method is available.
\item[Diff.]
This paper aims at constructing an algorithm for solving a BVP in
transferable nonlinear DAE's with nonsingular Jacobian and the same
dimension as in the ODE case.
\begin{description}[Jacob.]
\item[Jacob.] We also deal with Jacobians, which means that we
explain the functions, advantages and inconveniences of calling them not
Jacobians.
\item[Nonl.] Nonlinear functions play an important role in
this connection. Please note that we always call them nonlinear whenever
they are not linear.
\end{description}
\end{description}
\section{The shooting method}
The natural way to construct a shooting method to solve equations
of type DAE is described by \cite{yser}.
The physical meaning of $ \sigma_0 $ and $K$ is clearly visible in
the equations above. $\sigma_0$ represents a frequency of the order one
per free-fall time. $K$ is
proportional to the ratio of the free-fall time and the cooling time.
Substituting into Baker's criteria, using thermodynamic identities
and definitions of thermodynamic quantities,
\begin{displaymath}
\Gamma_1 = \DXDYCZ{\ln P}{\ln \rho}{S} \, , \;
\chi^{}_\rho = \DXDYCZ{\ln P}{\ln \rho}{T} \, , \;
\kappa^{}_{P} = \DXDYCZ{\ln \kappa}{\ln P}{T}
\end{displaymath}
\begin{displaymath}
\nabla_{\rm ad} = \DXDYCZ{\ln T}{\ln P}{S} \, , \;
\chi^{}_T = \DXDYCZ{\ln P}{\ln T}{\rho} \, , \;
\kappa^{}_{T} = \DXDYCZ{\ln \kappa}{\ln T}{T}
\end{displaymath}
one obtains, after some pages of algebra, the conditions for
{\em stability} given
below:
\begin{eqnarray}
\frac{\pi^2}{8} \frac{1}{\tau_{\rm ff}^2}
( 3 \Gamma_1 - 4 )
& > & 0 \label{ZSDynSta} \\
\frac{\pi^2}{\tau_{\rm co}
\tau_{\rm ff}^2}
\Gamma_1 \nabla_{\rm ad}
\left[ \frac{ 1- 3/4 \chi^{}_\rho }{ \chi^{}_T }
( \kappa^{}_T - 4 )
+ \kappa^{}_P + 1
\right]
& > & 0 \label{ZSSecSta} \\
\frac{\pi^2}{4} \frac{3}{\tau_{ \rm co }
\tau_{ \rm ff }^2
}
\Gamma_1^2 \, \nabla_{\rm ad} \left[
4 \nabla_{\rm ad}
- ( \nabla_{\rm ad} \kappa^{}_T
+ \kappa^{}_P
)
- \frac{4}{3 \Gamma_1}
\right]
& > & 0 \label{ZSVibSta}
\end{eqnarray}
For further examples and a physical discussion of the stability criteria
see \cite{tetz} or \cite{yser}.
\subsection{Disadvantages of the method}
The disadvantage of Eq. (\ref{ZSVibSta}) is the singularity of the
Jacobian. If we use the representation of
$z_i = P_i z_i + Q_i z_i =: u_i + v_i$, we obtain the following system
\begin{eqnarray}
g (u_0 + v_0 , x (t_m, t_{m-1}, u_{m-1}))& = & 0 \label{dis}\\
u_i - P_i x (t_i; t_{i-1}, u_{i-1}) & = & 0\;,
\quad i = 1, \ldots , m-1\;. \label{das}
\end{eqnarray}
\subsection{Specialization of $V$}
Now we specialize $V := \hat S^\prime $ in. Let $P_D$ be a
projector with ${\rm im} (P_D) = M$. If we demand Eq. (\ref{das}) and
\begin{eqnarray*}
VV^- &=& P_D \\
V^-V &=& P\; ,
\end{eqnarray*}
%
the generalized inverse $V^-$ in uniquely determined. Using Lemma 1 we
construct a regular matrix $K$ so that ${\rm im} (P_D) \oplus {\rm im}
(K^{-1} Q) = {\Bbb R}^n$. This provides the possibility to add without
loss $(K^{-1} Q) = {\Bbb R}^n$. This provides the possibility to add,
without loss of information, the Eqs.\ts (\ref{dis}) and (\ref{six})
(after multiplying by $K^{-1})$. The following shooting operator is
created
\begin{equation}
\quad S (\xi ) := \left\{
\begin{array}{ll}
S_1 (\xi):= & \left\{
\begin{array} {ll}
g (u_0 + v_0, x (t_m; t_{m-1}, u_{m-1})) + K^{-1} Q_0 u_0
&\quad (a)\\
u_i - P_i x (t_i; t_{i-1} , u_{i-1})\; i = 1, \ldots , m-1
& \quad(b)
\end{array} \right. \\
S_2 (\xi) := & \left\{
\begin{array} {ll}
Q_0 y_0 + P_0 v_0 & \quad (c)\\
f(y_0, u_0 + v_0, t_0) & \quad (d) \quad ,
\end{array}
\right.
\end{array} \right.\label{six}
\end{equation}
%
with $\xi := (u_0 , u_1, \ldots , u_{m-1} , y_0, v_0)^{\rm T}$.
\begin{lemma}
Let $V$ be a singular matrix and $V^-$ a reflexive inverse of $V$ with
Sect. (2.3) and $VV^- = P_D$, $V^-V = P$, where $P$ and $P_D$ satisfy
the conditions of Lemma 2.1. Then the matrix $V + K^{-1} Q$ is
nonsingular and
%
\[ (V + K^{-1} Q) ^{-1} = V^- + QK\; , \]
%
where $K$ is defined in Sect. (2.2).
\end{lemma}
\begin{proof}
\begin{eqnarray*}
(V + K^{-1}Q)(V^- + QK) & = & VV^- + VQK + K^{-1}QV^- + K^{-1} QK \\
& = & P_D + 0 + 0 + Q_D = I\; . \quad\qed
\end{eqnarray*}
\end{proof}
\begin{remark}
The value $w := (P_s v_0 + Q_0 G^{-1} f (y_0, u_0 + v_0, t_0))$ at
the right-hand side of Eq. (16) is the solution of the linear system
\begin{equation}
J_4 \left(\begin{array}{c} \eta \\ w \end{array} \right)
= \left(\begin{array}{c} Q_0 y_0 + P_0 v_0 \\
f (y_0, u_0 + v_0, t_0) \end{array} \right)
\end{equation}
\end{remark}
\begin{figure}\picplace {4 cm}
\firstcaption{The doping profile $C (t)$ has the same structure as
$N_-$}
\secondcaption{The doping profile of $C (z)$}
\end{figure}
This leads to the following algorithm to compute the iteration $\xi^i$:
\begin{description}[5 ---]
\item[0 -- ] initial value $\xi^0 := (u_0^0 , \ldots , u^0_{m-1} , y_0^0
, v_0^0)$
\item[1 -- ] $i:= 0$
\item[2 -- ] compute $u^{i+1}$ with (3.16)
\item[3 -- ] compute $y^{i+1}_0, v_0^{i+1}$ with (3.17) using $\Delta
u^{i+1} := u^{i+1} - u^i$
\item[4 -- ]$i:= i + 1$
\item[5 -- ]{\tt IF} accuracy not reached {\tt THEN GOTO 2 ELSE STOP}
\end{description}
\begin{theorem} Let the assumptions (A), (B) be fulfilled. Then the
non-linear equation
$$
S (\xi) = 0
$$
has a nonsingular Jacobian in a neighbourhood of
$$
\xi = \xi_\star := (u_{\star 0}, \ldots , u_{\star m-1} , y_{\star 0},
v_{\star 0})\; ,
$$
which corresponds with $x_\star$.
\end{theorem}
\section{Implementation}
If listing of a program is desired, this is possible too \cite{darnell}
\begin{verbatim}
void get_two_kbd_chars()
{
extern char KEYBOARD;
char c0, c1;
c0 = KEYBOARD;
c1 = KEYBOARD;
}
\end{verbatim}
\section{Solutions}
We solve this problem with the relative accuracy of integration $1d-4$.
The experimental tests of the Standard Model and thereby of the
unification of the weak and electromagnetic interactions have reached a
new level of accuracy. The results are given in Table \ref{KapSou}.
\begin{table}
\caption{Opacity sources}\label{KapSou}
\centering
\begin{tabular}{ll}
\hline\noalign{\smallskip}
Source & T/[K] \\
\noalign{\smallskip}
\hline
\noalign{\smallskip}
Yorke 1979, Yorke 1980a & $\leq 1700^{\rm a}$ \\
Kr\"ugel 1971 & $1700 \leq T \leq 5000$ \\
Cox and Stewart 1969 & $5000 \leq $ \\
\noalign{\smallskip}\hline\noalign{\smallskip}
$^{\rm a}$ This is a footnote.
\end{tabular}
\end{table}
\begin{acknowledgement}I wish to thank Prof. Dr. Roswitha M\"arz for
many helpful discussions.\end{acknowledgement}
\begin{thebibliography}[9]{References}
% Note that space for square brackets is added to the width of the label
% specified in the [] argument. If you don't use []s in your
% bibliography, specify a narrower label or omit the specification
% altogether. In this case \parindent is used.
\bibitem{}{darnell}{(Darnell, 1988)}
Darnell, P.A., Margolis, P.E. (1988): C, A software engineering
approach. Springer Verlag Berlin Heidelberg New York
\bibitem{}{leslie}{Lamport (1986)}
Lamport, L. (1986): \LaTeX: A document preparation system.
Addison-Wesley Publishing Company, Inc.
\bibitem{}{seroul}{Seroul (1989)}
Seroul, R., Levy, S. (1989): A beginner's book of \TeX{}. Springer New
York Berlin Heidelberg
\bibitem{}{springer}{LJour1 user's guide}
LJour1: Springer's \LaTeX{} style file for journals with one-column
layout. Springer Heidelberg
\bibitem{}{stroud}{Strout (1971)}
Strout, A.H. (1971): approximate calculation of multiple integrals.
Prentice Hall, Englewood Cliffs, N.J.
\bibitem{}{tetz}{Tetzlaff (1970)}
Tetzlaff, A. (1970): Stability in the Common Market. To appear.
\bibitem{}{wendl}{Wendland (1987)}
Wendland, W.L., (1987): Strongly elliptic boundary integral equations.
In: A. Iserles, M. Powell, eds., The state of the art in numerical
analysis. Clarendon Press, Oxford, pp. 511--561
\bibitem{}{yser}{Yserentant (1983)}
Yserentant, H. (1983): A remark on the numerical computation of
improper integrals. Computing {\bf 30}, 179--183
\medskip\noindent
\bibitem{Please}{}{}refer to a recent issue of the journal for further
examples on how to format references.
\end{thebibliography}
\end{document}