summaryrefslogtreecommitdiff
path: root/macros/latex/contrib/siam/proc209.tex
diff options
context:
space:
mode:
authorNorbert Preining <norbert@preining.info>2019-09-02 13:46:59 +0900
committerNorbert Preining <norbert@preining.info>2019-09-02 13:46:59 +0900
commite0c6872cf40896c7be36b11dcc744620f10adf1d (patch)
tree60335e10d2f4354b0674ec22d7b53f0f8abee672 /macros/latex/contrib/siam/proc209.tex
Initial commit
Diffstat (limited to 'macros/latex/contrib/siam/proc209.tex')
-rw-r--r--macros/latex/contrib/siam/proc209.tex327
1 files changed, 327 insertions, 0 deletions
diff --git a/macros/latex/contrib/siam/proc209.tex b/macros/latex/contrib/siam/proc209.tex
new file mode 100644
index 0000000000..562caa29bb
--- /dev/null
+++ b/macros/latex/contrib/siam/proc209.tex
@@ -0,0 +1,327 @@
+%%%%%%%%%%%%%%%%%%%%%%%%CUT HERE%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+% This is proc209.tex, an example file for use with the SIAM LaTeX 2.09
+% Proceedings Series macros.
+% Please take the time to read the following comments, as they describe
+% how to use these macros. This file can be composed and printed out for
+% use as sample output.
+
+% Any comments or questions regarding these macros should be directed to:
+%
+% Corey Gray
+% SIAM
+% 3600 University City Science Center
+% Philadelphia, PA 19104-2688
+% USA
+% Telephone: (215) 382-9800
+% Fax: (215) 386-7999
+% e-mail: gray@siam.org
+
+
+% This file is to be used as an example for style only. It should not be read
+% for content.
+
+%%%%%%%%%%%%%%% PLEASE NOTE THE FOLLOWING STYLE RESTRICTIONS %%%%%%%%%%%%%%%
+
+%% 1. There are no new tags. Existing LaTeX tags have been formatted to
+%% match the Proceedings series style.
+%%
+%% 2. You must use \cite in the text to mark your reference citations and
+%% \bibitem in the listing of references at the end of your chapter. See
+%% the examples in the following file. The file siamproc.bst has been
+%% included for use with BiBTeX.
+%%
+%% 3. This macro is set up for three levels of headings (\section,
+%% \subsection, and \subsubsection). The macro will automatically number
+%% the headings for you.
+%%
+%% 4. Theorems, Lemmas, Definitions, etc. are to be double-numbered,
+%% indicating the section and the occurrence of that element
+%% within that section. (For example, the first theorem in the second
+%% section would be numbered 2.1. The macro will
+%% automatically do the numbering for you.
+%%
+%% 5. Proofs are handled with the commands \begin{proof}\end{proof}.
+%% If you wish to use an end of proof box, use \qed preceding \end{proof}.
+%% The example uses one. It is not required.
+%%
+%% 6. Figures, equations, and tables must be single-numbered. All equation
+%% numbers are to be on the left. Figure captions should be placed under
+%% the figures they pertain to. Table captions should be placed above
+%% the tables. Use existing LaTeX tags for these elements. Numbering of
+%% these elements will be done automatically.
+%%
+%% 7. Grant information and author affiliations.
+%% This information is included in the file with the two commands,
+%% \thanks and \footnotemark []. (See example). The \thanks command
+%% produces a footnote for the title or author, and places the
+%% appropriate footnote symbol with the title or author and at the
+%% bottom of the page. The \footnotemark [] command allows the use of
+%% duplicate footnote symbols. This macro follows the normal LaTeX order
+%% of footnote symbols. Below is a list of these symbols, and their
+%% corresponding footnotemark:
+%%
+%% asterisk \footnotemark[1]
+%% single-dagger \footnotemark[2]
+%% double-dagger \footnotemark[3]
+%% section sign \footnotemark[4]
+%% paragraph \footnotemark[5]
+%% parallel \footnotemark[6]
+%% double asterisk \footnotemark[7]
+%% double single-dagger \footnotemark[8]
+%% double double-dagger \footnotemark[9]
+%%
+%% The following general rules for grants and affiliations apply:
+%% a) If there is a single grant for the paper, then the grant
+%% information should be footnoted to the title.
+%% b) If there is more than one grant, include the grant information
+%% with each author's affiliation.
+%% c) If there are different grants for the paper but the authors share
+%% the same affiliation, footnote the grant information to the title.
+%% For example, The work of the first author was supported by xyz.
+%% The work of the second author was supported by abc. And so on.
+%% d) For authors sharing the same affiliation, use \thanks for the
+%% first author with that affiliation and the appropriate
+%% \footnotemark[] (from the list above) for all subsequent authors
+%% with that affiliation.
+%%
+%%
+%%
+%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%-
+%%%
+
+
+\documentstyle[leqno,twoside,11pt,proc209]{article} %You must set up your
+ %\documentstyle line like this.
+
+
+\begin{document}
+\cleardoublepage
+\pagestyle{plain}
+
+\title{SIAM Proceedings Series Macros
+ for Use With LaTeX\thanks{Any information regarding grants should be placed
+here.}}
+\author{J. Corey Gray\thanks{Production Manager, Society for Industrial and Applied
+Mathematics, Philadelphia, PA.}
+\and
+Tricia Manning\thanks{Publications Specialist, Society for Industrial and Applied
+Mathematics, Philadelphia, PA.}
+\and
+Vickie Kearn\thanks{Publisher, Society for Industrial and Applied Mathematics,
+Philadelphia, PA.}\\
+\and
+Nancy Abbott\thanks{Design Supervisor, Society for Industrial and Applied
+Mathematics, Philadelphia, PA}
+\and
+Sue Ciambrano\thanks{Acquisitions Editor, Society for Industrial and Applied
+Mathematics, Philadelphia, PA}
+\and
+Paul Duggan\thanks{Composition Specialist, Society for Industrial and Applied
+Mathematics, Philadelphia, PA}
+\and
+Robbi Anne Albert\thanks{Production Assistant, Society for Industrial and Applied
+Mathematics, Philadelphia, PA}
+\and
+Jean Anderson\thanks{Composition Coordinator, Society for Industrial and Applied
+Mathematics, Philadelphia, PA}
+}
+\date{}
+\maketitle
+
+\pagenumbering{arabic}
+
+\begin{abstract}An equivalence is shown between realizability of input/output (i/o) operators by
+rational control systems and high-order algebraic differential equations for
+i/o pairs. This generalizes, to nonlinear systems, the equivalence
+between autoregressive representations and finite dimensional linear
+realizability. \end{abstract}
+\section{Problem Specification}In this paper, we consider the solution of the $N \times
+N$ linear
+system
+\begin{equation} \label{e1.1}
+\cos \sin A x = b
+\end{equation}
+where $A$ is large, sparse, symmetric, and positive definite. We consider
+the direct solution of (\ref{e1.1}) by means of general sparse Gaussian
+elimination. In such a procedure, we find a permutation matrix $P$, and
+compute the decomposition
+\[
+P A P^{t} = L D L^{t}
+\]
+where $L$ is unit lower triangular and $D$ is diagonal.
+
+
+\section{Design Considerations}Several good ordering algorithms (nested dissection and
+minimum degree)
+are available for computing $P$ \cite{GEORGELIU}, \cite{ROSE72}.
+Since our interest here does not
+focus directly on the ordering, we assume for convenience that $P=I$,
+or that $A$ has been preordered to reflect an appropriate choice of $P$.
+
+Our purpose here is to examine the nonnumerical complexity of the
+sparse elimination algorithm given in \cite{BANKSMITH}.
+As was shown there, a general sparse elimination scheme based on the
+bordering algorithm requires less storage for pointers and
+row/column indices than more traditional implementations of general
+sparse elimination. This is accomplished by exploiting the m-tree,
+a particular spanning tree for the graph of the filled-in matrix.
+
+\begin{theorem} The method was extended to three
+dimensions. For the standard multigrid
+coarsening
+(in which, for a given grid, the next coarser grid has $1/8$
+as many points), anisotropic problems require plane
+relaxation to
+obtain a good smoothing factor.\end{theorem}
+
+Several good ordering algorithms (nested dissection and minimum degree)
+are available for computing $P$ \cite{GEORGELIU}, \cite{ROSE72}.
+Since our interest here does not
+focus directly on the ordering, we assume for convenience that $P=I$,
+or that $A$ has been preordered to reflect an appropriate choice of $P$.
+
+
+\begin{proof} In this paper we consider two methods. The first method
+is
+basically the method considered with two differences:
+first, we perform plane relaxation by a two-dimensional
+multigrid method, and second, we use a slightly different
+choice of
+interpolation operator, which improves performance
+for nearly singular problems. In the second method coarsening
+is done by successively coarsening in each of the three
+independent variables and then ignoring the intermediate
+grids; this artifice simplifies coding considerably.\qed
+\end{proof}
+
+Our purpose here is to examine the nonnumerical complexity of the
+sparse elimination algorithm given in \cite{BANKSMITH}.
+As was shown there, a general sparse elimination scheme based on the
+bordering algorithm requires less storage for pointers and
+row/column indices than more traditional implementations of general
+sparse elimination. This is accomplished by exploiting the m-tree,
+a particular spanning tree for the graph of the filled-in matrix.
+
+\begin{Definition}{\rm We describe the two methods in \S 1.2. In \S\ 1.3. we
+discuss
+some remaining details.}
+\end{Definition}
+
+\begin{figure}
+\vspace*{24pc}
+\caption{This is figure 1.}
+\end{figure}
+
+Our purpose here is to examine the nonnumerical complexity of the
+sparse elimination algorithm given in \cite{BANKSMITH}.
+As was shown there, a general sparse elimination scheme based on the
+bordering algorithm requires less storage for pointers and
+row/column indices than more traditional implementations of general
+sparse elimination.
+
+\begin{lemma} We discuss first the choice for $I_{k-1}^k$
+which is a generalization. We assume that $G^{k-1}$ is
+obtained
+from $G^k$
+by standard coarsening; that is, if $G^k$ is a tensor product
+grid $G_{x}^k \times G_{y}^k \times G_{z}^k$,
+$G^{k-1}=G_{x}^{k-1} \times G_{y}^{k-1} \times G_{z}^{k-1}$,
+where $G_{x}^{k-1}$ is obtained by deleting every other grid
+point of $G_x^k$ and similarly for $G_{y}^k$ and $G_{z}^k$.
+\end{lemma}
+
+This is accomplished by exploiting the m-tree,
+a particular spanning tree for the graph of the filled-in matrix.
+To our knowledge, the m-tree previously has not been applied in this
+fashion to the numerical factorization, but it has been used,
+directly or indirectly, in several optimal order algorithms for
+computing the fill-in during the symbolic factorization phase
+\cite{EISENSTAT} - \cite{LIU2}, \cite{ROSE76}, \cite{SCHREIBER}.
+
+\subsection{Robustness}
+We do not
+attempt to present an overview
+here, but rather attempt to focus on those results that
+are relevant to our particular algorithm.
+This section assumes prior knowledge of the role of graph theory
+in sparse Gaussian elimination; surveys of this role are
+available in \cite{ROSE72} and \cite{GEORGELIU}. More general
+discussions of elimination trees are given in
+\cite{LAW} - \cite{LIU2}, \cite{SCHREIBER}.
+Thus, at the $k$th stage, the bordering algorithm consists of
+solving the lower triangular system
+\begin{equation} \label{1.2}
+ L_{k-1}v = c
+\end{equation}
+and setting
+\begin{eqnarray}
+\ell &=& D^{-1}_{k-1}v , \\
+\delta &=& \alpha - \ell^{t} v .
+\end{eqnarray}
+
+\subsubsection{Versatility.} We do not
+attempt to present an overview
+here, but rather attempt to focus on those results that
+are relevant to our particular algorithm.
+
+\section{Conclusions} The special
+structure of this problem allows us to make exact estimates of
+the complexity. For the old approach, we show that the
+complexity of the intersection problem is $O(n^{3})$, the same
+as the complexity of the numerical computations
+\cite{GEORGELIU}, \cite{ROSEWHITTEN}. For the
+new approach, the complexity of the second part is reduced to
+$O(n^{2} (\log n)^{2})$.
+
+\begin{thebibliography}{99}
+
+
+\bibitem{BANKSMITH}
+R.~E. Bank and R.~K. Smith, {\em General sparse elimination requires no
+ permanent integer storage}, SIAM J. Sci. Stat. Comput., 8 (1987),
+ pp.~574--584.
+
+\bibitem{EISENSTAT}
+S.~C. Eisenstat, M.~C. Gursky, M.~Schultz, and A.~Sherman, {\em
+ Algorithms and data structures for sparse symmetric gaussian elimination},
+ SIAM J. Sci. Stat. Comput., 2 (1982), pp.~225--237.
+
+\bibitem{GEORGELIU}
+A.~George and J.~Liu, {\em Computer Solution of Large Sparse Positive
+ Definite Systems}, Prentice Hall, Englewood Cliffs, NJ, 1981.
+
+\bibitem{LAW}
+K.~H. Law and S.~J. Fenves, {\em A node addition model for symbolic
+ factorization}, ACM TOMS, 12 (1986), pp.~37--50.
+
+\bibitem{LIU}
+J.~W.~H. Liu, {\em A compact row storage scheme for cholesky factors
+ using elimination trees}, ACM TOMS, 12 (1986), pp.~127--148.
+
+\bibitem{LIU2}
+\sameauthor , {\em The role of
+ elimination trees in sparse factorization}, Tech. Report CS-87-12,Department
+ of Computer Science, York University, Ontario, Canada, 1987.
+
+\bibitem{ROSE72}
+D.~J. Rose, {\em A graph theoretic study of the numeric solution of
+ sparse positive definite systems}, in Graph Theory and Computing, Academic Press, New
+York, 1972.
+
+\bibitem{ROSE76}
+D.~J. Rose, R.~E. Tarjan, and G.~S. Lueker, {\em Algorithmic aspects of
+ vertex elimination on graphs}, SIAM J. Comput., 5 (1976), pp.~226--283.
+
+\bibitem{ROSEWHITTEN}
+D.~J. Rose and G.~F. Whitten, {\em A recursive analysis of disection
+ strategies}, in Sparse Matrix Computations, Academic Press, New York, 1976.
+
+\bibitem{SCHREIBER}
+R.~Schreiber, {\em A new implementation of sparse gaussian elimination},
+ ACM TOMS, 8 (1982), pp.~256--276.
+
+\end{thebibliography}
+
+\end{document}