diff options
Diffstat (limited to 'macros/latex/contrib/siam/proc2e.all')
-rw-r--r-- | macros/latex/contrib/siam/proc2e.all | 1746 |
1 files changed, 1746 insertions, 0 deletions
diff --git a/macros/latex/contrib/siam/proc2e.all b/macros/latex/contrib/siam/proc2e.all new file mode 100644 index 0000000000..b10bc47a35 --- /dev/null +++ b/macros/latex/contrib/siam/proc2e.all @@ -0,0 +1,1746 @@ + + +This file constitutes the full distribution for SIAM Proceedings +Series LaTeX version macros. The files included here are: + +proc2e.tex (An example file, also containing documentation) + +proc2e.sty (The style file) + +siamproc.bst (for BiBTeX users) + +To use these macros, separate the files at the indicated cut lines. + +%%%%%%%%%%%%%%%%%%%%%%%%CUT HERE%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +% This is proc2e.tex, an example file for use with the SIAM LaTeX2e +% 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. +%% +%% +%% +%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%- +%%% + +\documentclass[twoside,leqno,11pt]{article} +\usepackage{proc2e} + + +\begin{document} +\cleardoublepage +\pagestyle{headings} + +\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} + +%%%%%%%%%%%%%%%%%%%%%%%%%%CUT HERE%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +% This is proc2e.sty. +% This file may be freely distributed but may not be altered in any way. +% 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 is a file of macros and definitions for creating a chapter for +% publication in the SIAM Proceedings series using LaTeX2e. + +% Report the version. +\message{*** SIAM LaTeX2e Proceedings Series macro package, version 1.1, +October 28, 1996 ***} + +\pretolerance=800 +\tolerance=10000 +\sloppy + + +\vsize=56pc +\hsize=36pc +\baselineskip=13pt +\hoffset -.5in +\voffset -.5in +\footskip=18pt +\topmargin 24pt +\headheight 12pt +\headsep 15pt +\textheight 53.5pc \advance\textheight by \topskip +\textwidth 36pc +\parskip 0pt +\parindent 18pt +\def\topfraction{.9} +\def\textfraction{.1} +\def\topnumber{2} +%% footnotes to be set 8/10 +\def\footnotesize{\@setsize\footnotesize{11pt}\ixpt\@ixpt + % \indent + \abovedisplayskip \z@ + \belowdisplayskip\z@ + \abovedisplayshortskip\abovedisplayskip + \belowdisplayshortskip\belowdisplayshortskip +\def\@listi{\leftmargin\leftmargini \topsep 3pt plus 1pt minus 1pt + \parsep 2pt plus 1pt minus 1pt + \itemsep \parsep}} + +\let\referencesize\footnotesize + +\footnotesep 0pt + +\skip\footins 12pt plus 12pt + +\def\footnoterule{\kern3\p@ \hrule width 3em\vspace{3pt}} % the \hrule is .4pt high + + +\def\ps@plain{\let\@mkboth\@gobbletwo + \def\@oddfoot{{\hfil\small\thepage\hfil}}% + \def\@oddhead{} + \def\@evenhead{}\def\@evenfoot{}} + + + +\def\ps@headings{\let\@mkboth\markboth + \def\@oddfoot{}\def\@evenfoot{}% + \def\@evenhead{{\rm\thepage}\hspace*{2pc}{\sc\leftmark}\hfil}% + \def\@oddhead{\hfil{\noindent\sc\rightmark}\hspace*{2pc}{\rm\thepage}}% + + + +\def\ps@myheadings{\let\@mkboth\@gobbletwo + \def\@oddfoot{}\def\@evenfoot{}% + \def\@oddhead{\hfil{\sc\rightmark}\hspace*{2pc}{\normalsize\rm\thepage}}% + \def\@evenhead{{\normalsize\rm\thepage}\hspace*{2pc}{\sc\leftmark}\hfil}% +% \def\chaptermark##1{}% + % \def\sectionmark##1{}\def\subsectionmark##1{}} +}} + + + +\def\theequation{\arabic{equation}} + +\def\abstract{\if@twocolumn +\section*{Abstract} +\else \small +\begin{center} +{\bf Abstract\vspace{-.5em}\vspace{3pt}} +\end{center} +\quotation +\fi} +\def\endabstract{\if@twocolumn\else\endquotation\fi} + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% % +% THEOREMS, PROOFS, ALGORITHMS % +% % +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%% defined proof environment by theorem model (took out counter) + +\def\qed{{\qquad \vbox{\hrule\hbox{% + \vrule height1.3ex\hskip0.8ex\vrule}\hrule + }}\par} + +\def\newproof#1{\@nprf{#1}} + +\def\@nprf#1#2{\@xnprf{#1}{#2}} + +\def\@xnprf#1#2{\expandafter\@ifdefinable\csname #1\endcsname +\global\@namedef{#1}{\@prf{#1}{#2}}\global\@namedef{end#1}{\@endproof}} + +\def\@prf#1#2{\@xprf{#1}{#2}} + +\def\@xprf#1#2{\@beginproof{#2}{\csname the#1\endcsname}\ignorespaces} + + + +%%% defined algorithm environment by theorem model + +\def\newalgorithm#1{\@ifnextchar[{\@oalg{#1}}{\@nalg{#1}}} + +\def\@nalg#1#2{% +\@ifnextchar[{\@xnalg{#1}{#2}}{\@ynalg{#1}{#2}}} + +\def\@xnalg#1#2[#3]{\expandafter\@ifdefinable\csname #1\endcsname +{\@definecounter{#1}\@addtoreset{#1}{#3}% +\expandafter\xdef\csname the#1\endcsname{\expandafter\noexpand + \csname the#3\endcsname \@thmcountersep \@thmcounter{#1}}% +\global\@namedef{#1}{\@alg{#1}{#2}}\global\@namedef{end#1}{\@endalgorithm}}} + +\def\@ynalg#1#2{\expandafter\@ifdefinable\csname #1\endcsname +{\@definecounter{#1}% +\expandafter\xdef\csname the#1\endcsname{\@thmcounter{#1}}% +\global\@namedef{#1}{\@alg{#1}{#2}}\global\@namedef{end#1}{\@endalgorithm}}} + +\def\@oalg#1[#2]#3{\expandafter\@ifdefinable\csname #1\endcsname + {\global\@namedef{the#1}{\@nameuse{the#2}}% +\global\@namedef{#1}{\@alg{#2}{#3}}% +\global\@namedef{end#1}{\@endalgorithm}}} + +\def\@alg#1#2{\refstepcounter + {#1}\@ifnextchar[{\@yalg{#1}{#2}}{\@xalg{#1}{#2}}} + +\def\@xalg#1#2{\@beginalgorithm{#2}{\csname the#1\endcsname}\ignorespaces} +\def\@yalg#1#2[#3]{\@opargbeginalgorithm{#2}{\csname + the#1\endcsname}{#3}\ignorespaces} + + + + +\def\@beginproof#1{\rm {\it #1.\ }} +\def\@endproof{\outerparskip 0pt\endtrivlist} + +\def\@begintheorem#1#2{\it {\sc #1\ #2.\ }} +\def\@opargbegintheorem#1#2#3{\it + {\sc #1\ #2\ (#3).\ }} +\def\@endtheorem{\outerparskip 0pt\endtrivlist} + +%\def\@begindefinition#1#2{\rm \trivlist \item[\hskip \labelsep{\sc #1\ #2.}]} +%\def\@opargbegindefinition#1#2#3{\rm \trivlist +% \item[\hskip \labelsep{\sc #1\ #2.\ (#3)}]} +%\def\@enddefinition{\outerparskip 0pt\endtrivlist} + + +\def\@beginalgorithm#1#2{\rm \trivlist \item[\hskip \labelsep{\sc #1\ #2.}]} +\def\@opargbeginalgorithm#1#2#3{\rm \trivlist + \item[\hskip \labelsep{\sc #1\ #2.\ (#3)}]} +\def\@endalgorithm{\outerparskip 6pt\endtrivlist} + + +\newskip\outerparskip + +%\def\trivlist{\parsep\outerparskip +% \@trivlist \labelwidth\z@ \leftmargin\z@ +% \itemindent\parindent \def\makelabel##1{##1}} +% +%\def\@trivlist{\topsep=0pt\@topsepadd\topsep +% \if@noskipsec \leavevmode \fi +% \ifvmode \advance\@topsepadd\partopsep \else \unskip\par\fi +% \if@inlabel \@noparitemtrue \@noparlisttrue +% \else \@noparlistfalse \@topsep\@topsepadd \fi +% \advance\@topsep \parskip +% \leftskip\z@\rightskip\@rightskip \parfillskip\@flushglue +% \@setpar{\if@newlist\else{\@@par}\fi}% +% \global\@newlisttrue \@outerparskip\parskip} +% +% +%\def\endtrivlist{\if@newlist\@noitemerr\fi +% \if@inlabel\indent\fi +% \ifhmode\unskip \par\fi +% \if@noparlist \else +% \ifdim\lastskip >\z@ \@tempskipa\lastskip \vskip -\lastskip +% \advance\@tempskipa\parskip \advance\@tempskipa -\@outerparskip +% \vskip\@tempskipa +% \fi\@endparenv\fi +% \vskip\outerparskip} + + + + \newproof{@proof}{Proof} + \newenvironment{proof}{\begin{@proof}}{\end{@proof}} + + \newtheorem{@theorem}{Theorem}[section] + \newenvironment{theorem}{\begin{@theorem}}{\end{@theorem}} + +% \newalgorithm{@algorithm}{Algorithm}[section] +% \newenvironment{algorithm}{\begin{@algorithm}}{\end{@algorithm}} + + + +\newtheorem{lemma}{Lemma}[section] +\newtheorem{fact}{Fact}[section] +\newtheorem{corollary}{Corollary}[section] +\newtheorem{axiom}{Axiom}[section] +\newtheorem{cond}{Condition}[section] +\newtheorem{property}{Property}[section] +\newtheorem{proposition}{Proposition}[section] + +\newtheorem{Conjecture}{Conjecture}[section] +\newtheorem{Definition}{Definition}[section] +\newtheorem{Lemma}{Lemma}[section] +\newtheorem{Remark}{Remark}[section] + +\newproof{Example}{Example} +\newproof{Method}{Method} +\newproof{Exercise}{Exercise} + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% % +% TABLE AND FIGURE CAPTIONS % +% % +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + \def\@figtxt{figure} +\long\def\@makecaption#1#2{\small +\setlength{\parindent}{18pt} +\baselineskip 14pt + \ifx\@captype\@figtxt + \vskip 10pt + \setbox\@tempboxa\hbox{{\sc #1} {\it #2}} + \ifdim \wd\@tempboxa >\hsize {\sc #1} {\it #2}\par \else \hbox +to\hsize{\hfil\box\@tempboxa\hfil}% + \fi\else\hbox to\hsize{\hfil{\sc #1}\hfil}% + \setbox\@tempboxa\hbox{{\it #2}}% + \ifdim \wd\@tempboxa >\hsize {\it #2}\par \else + \hbox to \hsize{\hfil\box\@tempboxa\hfil}\fi + \vskip 10pt + \fi} + + +%\newif\iftable \global\tablefalse + + +%\long\def\@makecaption#1#2{% +%\setlength{\parindent}{18pt} +% \vskip 12pt +% \iftable + % \hbox to \hsize{\hfil\sc #1\hfil} + % \hbox to \hsize{\hfil\it #2\hfil} + % \global\tablefalse + % \else + % \setbox\@tempboxa\hbox{{\small#1} {\small\it#2}} + % \ifdim \wd\@tempboxa >\hsize + % \indent{\small#1}{\small\it#2}\par + % \else + % \hbox to\hsize{\hfil\box\@tempboxa\hfil}\fi + % \fi} +% \vskip 6pt} + + + +%\def\figure{\global\tablefalse\@float{figure}} +\def\fnum@figure{\par\sc Fig. \thefigure.\ } +%\def\fnum@figure{\par\sc Fig. \thefigure\ } + +%\def\table{\global\tabletrue\@float{table}} +\def\fnum@table{\small \sc Table \thetable} + + + + + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% % +% SECTIONS % +% % +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +\def\section{\@startsection {section}{1}{\z@}{-3.5ex plus -1ex minus + -.2ex}%{2.3ex plus .2ex} +{2pt}{\large\bf}} +\def\subsection{\@startsection{subsection}{2}{\z@}{-3.25ex plus -1ex minus + -.2ex}%{1.5ex plus .2ex} +{2pt}{\large\bf}} +\def\subsubsection{\@startsection {subsubsection}{3}{\z@}{1.3ex plus .5ex minus + .2ex}{-.5em plus -.1em}{\normalsize\bf}} + + + + + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% %% +%% BIBLIOGRAPHY %% +%% %% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +\def\thebibliography#1{% +%\cleardoublepage +\parindent 0em +\vspace{9pt} +\begin{flushleft}\large\bf {References}\end{flushleft} +\addvspace{3pt}\nopagebreak\list + %% default is no labels, for those not using \cite or BibTeX +{[\arabic{enumi}]} {\settowidth\labelwidth{[#1]} +%%{[\arabic{enumi}]}{\settowidth\labelwidth{mm} +\leftmargin\labelwidth +\leftmargin=17pt + \advance\leftmargin\labelsep + \usecounter{enumi}\@bibsetup} +\def\newblock{\hskip .11em plus .33em minus -.07em} + \sloppy\clubpenalty4000\widowpenalty4000 + \sfcode`\.=1000\relax} + + + +%% setup 8/10 type +\def\@bibsetup{%\itemindent=0pt +\itemsep=0pt \parsep=0pt +\small} + +\def\sameauthor{\leavevmode\vrule height 2pt depth -1.6pt width 23pt} + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% % +% INDEX % +% % +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +%makeindex.sty official version 6.4 +%The second line came from /usr/misc/lib/tex82/report.sty. + +\def\theindex{\@restonecoltrue\if@twocolumn\@restonecolfalse\fi +\columnseprule \z@ +\columnsep 35pt\twocolumn[\chapter*{Index}] + \parskip\z@ plus .3pt\relax\let\item\@idxitem} + + +\def\printindex{\cleardoublepage\markboth{INDEX}{INDEX} +\addcontentsline{toc}{chapter}{Index}\@input{\jobname.ind}} + +\ps@headings + + +%%% end of style file + +%%%%%%%%%%%%%%%%%%%%%%%%%%CUT HERE%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +% This is siamproc.bst +% SIAM bibliography style (29-Jan-88 version) +% numeric labels, alphabetic order, Mathematical Reviews abbreviations, +% names in \sc, titles in italics, book titles mixed upper-lower and article +% titles lowercase, commas separate all fields except before "notes". +% +% History +% 1/30/86 (HWT) Original version, by Howard Trickey. +% 6/15/87 (HWT) Fix format.editors---Martin Costabel. +% 1/29/88 (OP&HWT) Updated for BibTeX version 0.99a, Oren Patashnik; +% THIS `siam' VERSION DOES NOT WORK WITH BIBTEX 0.98i. + +ENTRY + { address + author + booktitle + chapter + edition + editor + howpublished + institution + journal + key + month + note + number + organization + pages + publisher + school + series + title + type + volume + year + } + {} + { label } + +INTEGERS { output.state before.all mid.sentence after.block } + +FUNCTION {init.state.consts} +{ #0 'before.all := + #1 'mid.sentence := + #2 'after.block := +} + +STRINGS { s t } + +FUNCTION {output.nonnull} +{ 's := + output.state mid.sentence = + { ", " * write$ } + { output.state after.block = + { add.period$ write$ + newline$ + "\newblock " write$ + } + 'write$ + if$ + mid.sentence 'output.state := + } + if$ + s +} + +FUNCTION {output} +{ duplicate$ empty$ + 'pop$ + 'output.nonnull + if$ +} + +FUNCTION {output.check} +{ 't := + duplicate$ empty$ + { pop$ "empty " t * " in " * cite$ * warning$ } + 'output.nonnull + if$ +} + +FUNCTION {output.bibitem} +{ newline$ + "\bibitem{" write$ + cite$ write$ + "}" write$ + newline$ + "" + before.all 'output.state := +} + +FUNCTION {fin.entry} +{ add.period$ + write$ + newline$ +} + +FUNCTION {new.block} +{ output.state before.all = + 'skip$ + { after.block 'output.state := } + if$ +} + +FUNCTION {not} +{ { #0 } + { #1 } + if$ +} + +FUNCTION {and} +{ 'skip$ + { pop$ #0 } + if$ +} + +FUNCTION {or} +{ { pop$ #1 } + 'skip$ + if$ +} + +FUNCTION {new.block.checka} +{ empty$ + 'skip$ + 'new.block + if$ +} + +FUNCTION {field.or.null} +{ duplicate$ empty$ + { pop$ "" } + 'skip$ + if$ +} + +FUNCTION {emphasize} +{ duplicate$ empty$ + { pop$ "" } + { "{\em " swap$ * "}" * } + if$ +} + +FUNCTION {scapify} +{ duplicate$ empty$ + { pop$ "" } + { "{\sc " swap$ * "}" * } + if$ +} + +INTEGERS { nameptr namesleft numnames } + +FUNCTION {format.names} +{ 's := + #1 'nameptr := + s num.names$ 'numnames := + numnames 'namesleft := + { namesleft #0 > } + { s nameptr "{f.~}{vv~}{ll}{, jj}" format.name$ 't := + nameptr #1 > + { namesleft #1 > + { ", " * t * } + { numnames #2 > + { "," * } + 'skip$ + if$ + t "others" = + { " et~al." * } + { " and " * t * } + if$ + } + if$ + } + 't + if$ + nameptr #1 + 'nameptr := + namesleft #1 - 'namesleft := + } + while$ +} + +STRINGS { last.authors } + +FUNCTION {init.last.authors} +{ "" 'last.authors := +} + +FUNCTION {format.authors} +{ author empty$ + { "" 'last.authors := + "" + } + { author last.authors = + { "\leavevmode\vrule height 2pt depth -1.6pt width 23pt" } + { author format.names }% scapify } + if$ + author 'last.authors := + } + if$ +} + +FUNCTION {format.organization} +{ organization empty$ + { "" 'last.authors := + "" + } + { organization last.authors = + { "\leavevmode\vrule height 2pt depth -1.6pt width 23pt" } + { organization scapify } + if$ + organization 'last.authors := + } + if$ +} + +FUNCTION {format.editors} +{ editor empty$ + { "" 'last.authors := + "" + } + { editor last.authors = + { "\leavevmode\vrule height 2pt depth -1.6pt width 23pt" } + { editor format.names scapify } + if$ + editor num.names$ #1 > + { ", eds." * } + { ", ed." * } + if$ + editor 'last.authors := + } + if$ +} + +FUNCTION {format.ineditors} +{ editor empty$ + { "" } + { editor format.names + editor num.names$ #1 > + { ", eds." * } + { ", ed." * } + if$ + } + if$ +} + +FUNCTION {format.title} +{ title empty$ + { "" } + { title "t" change.case$ emphasize } + if$ +} + +FUNCTION {n.dashify} +{ 't := + "" + { t empty$ not } + { t #1 #1 substring$ "-" = + { t #1 #2 substring$ "--" = not + { "--" * + t #2 global.max$ substring$ 't := + } + { { t #1 #1 substring$ "-" = } + { "-" * + t #2 global.max$ substring$ 't := + } + while$ + } + if$ + } + { t #1 #1 substring$ * + t #2 global.max$ substring$ 't := + } + if$ + } + while$ +} + +FUNCTION {format.date} +{ year empty$ + { month empty$ + { "" } + { "there's a month but no year in " cite$ * warning$ + month + } + if$ + } + { month empty$ + 'year + { month " " * year * } + if$ + } + if$ +} + +FUNCTION {format.btitle} +{ title emphasize +} + +FUNCTION {tie.or.space.connect} +{ duplicate$ text.length$ #3 < + { "~" } + { " " } + if$ + swap$ * * +} + +FUNCTION {either.or.check} +{ empty$ + 'pop$ + { "can't use both " swap$ * " fields in " * cite$ * warning$ } + if$ +} + +FUNCTION {format.bvolume} +{ volume empty$ + { "" } + { "vol.~" volume * + series empty$ + 'skip$ + { " of " * series * } + if$ + "volume and number" number either.or.check + } + if$ +} + +FUNCTION {format.number.series} +{ volume empty$ + { number empty$ + { series field.or.null } + { "no.~" number * + series empty$ + { "there's a number but no series in " cite$ * warning$ } + { " in " * series * } + if$ + } + if$ + } + { "" } + if$ +} + +FUNCTION {format.edition} +{ edition empty$ + { "" } + { edition "l" change.case$ "~ed." * } + if$ +} + +INTEGERS { multiresult } + +FUNCTION {multi.page.check} +{ 't := + #0 'multiresult := + { multiresult not + t empty$ not + and + } + { t #1 #1 substring$ + duplicate$ "-" = + swap$ duplicate$ "," = + swap$ "+" = + or or + { #1 'multiresult := } + { t #2 global.max$ substring$ 't := } + if$ + } + while$ + multiresult +} + +FUNCTION {format.pages} +{ pages empty$ + { "" } + { pages multi.page.check + { "pp.~" pages n.dashify * } + { "p.~" pages * } + if$ + } + if$ +} + +FUNCTION {format.vol.year} +{ volume field.or.null + year empty$ + { "empty year in " cite$ * warning$ } + { " (" year * ")" * * } + if$ +} + +FUNCTION {format.chapter.pages} +{ chapter empty$ + 'format.pages + { type empty$ + { "ch.~" chapter * } + { type "l" change.case$ chapter tie.or.space.connect } + if$ + pages empty$ + 'skip$ + { ", " * format.pages * } + if$ + } + if$ +} + +FUNCTION {format.in.ed.booktitle} +{ booktitle empty$ + { "" } + { editor empty$ + { "in " booktitle * } + { "in " booktitle * ", " * format.ineditors * } + if$ + } + if$ +} + +FUNCTION {empty.misc.check} +{ author empty$ title empty$ howpublished empty$ + month empty$ year empty$ note empty$ + and and and and and + key empty$ not and + { "all relevant fields are empty in " cite$ * warning$ } + 'skip$ + if$ +} + +FUNCTION {format.thesis.type} +{ type empty$ + 'skip$ + { pop$ + type "l" change.case$ + } + if$ +} + +FUNCTION {format.tr.number} +{ type empty$ + { "Tech. Rep." } + 'type + if$ + number empty$ + { "l" change.case$ } + { number tie.or.space.connect } + if$ +} + +FUNCTION {format.article.crossref} +{ key empty$ + { journal empty$ + { "need key or journal for " cite$ * " to crossref " * crossref * + warning$ + "" + } + { "in " journal * } + if$ + } + { "in " key * } + if$ + " \cite{" * crossref * "}" * +} + +FUNCTION {format.crossref.editor} +{ editor #1 "{vv~}{ll}" format.name$ + editor num.names$ duplicate$ + #2 > + { pop$ " et~al." * } + { #2 < + 'skip$ + { editor #2 "{ff }{vv }{ll}{ jj}" format.name$ "others" = + { " et~al." * } + { " and " * editor #2 "{vv~}{ll}" format.name$ * } + if$ + } + if$ + } + if$ +} + +FUNCTION {format.book.crossref} +{ volume empty$ + { "empty volume in " cite$ * "'s crossref of " * crossref * warning$ + "in " + } + { "vol.~" volume * + " of " * + } + if$ + editor empty$ + editor field.or.null author field.or.null = + or + { key empty$ + { series empty$ + { "need editor, key, or series for " cite$ * " to crossref " * + crossref * warning$ + "" * + } + { series * } + if$ + } + { key * } + if$ + } + { format.crossref.editor * } + if$ + " \cite{" * crossref * "}" * +} + +FUNCTION {format.incoll.inproc.crossref} +{ editor empty$ + editor field.or.null author field.or.null = + or + { key empty$ + { booktitle empty$ + { "need editor, key, or booktitle for " cite$ * " to crossref " * + crossref * warning$ + "" + } + { "in " booktitle * } + if$ + } + { "in " key * } + if$ + } + { "in " format.crossref.editor * } + if$ + " \cite{" * crossref * "}" * +} + +FUNCTION {article} +{ output.bibitem + format.authors "author" output.check + format.title "title" output.check + crossref missing$ + { journal "journal" output.check + format.vol.year output + } + { format.article.crossref output.nonnull } + if$ + format.pages output + new.block + note output + fin.entry +} + +FUNCTION {book} +{ output.bibitem + author empty$ + { format.editors "author and editor" output.check } + { format.authors output.nonnull + crossref missing$ + { "author and editor" editor either.or.check } + 'skip$ + if$ + } + if$ + format.btitle "title" output.check + crossref missing$ + { format.bvolume output + format.number.series output + publisher "publisher" output.check + address output + } + { format.book.crossref output.nonnull } + if$ + format.edition output + format.date "year" output.check + new.block + note output + fin.entry +} + +FUNCTION {booklet} +{ output.bibitem + format.authors output + format.title "title" output.check + howpublished new.block.checka + howpublished output + address output + format.date output + new.block + note output + fin.entry +} + +FUNCTION {inbook} +{ output.bibitem + author empty$ + { format.editors "author and editor" output.check } + { format.authors output.nonnull + crossref missing$ + { "author and editor" editor either.or.check } + 'skip$ + if$ + } + if$ + format.btitle "title" output.check + crossref missing$ + { format.bvolume output + format.number.series output + publisher "publisher" output.check + address output + } + { format.book.crossref output.nonnull } + if$ + format.edition output + format.date "year" output.check + format.chapter.pages "chapter and pages" output.check + new.block + note output + fin.entry +} + +FUNCTION {incollection} +{ output.bibitem + format.authors "author" output.check + format.title "title" output.check + crossref missing$ + { format.in.ed.booktitle "booktitle" output.check + format.bvolume output + format.number.series output + publisher "publisher" output.check + address output + format.edition output + format.date "year" output.check + } + { format.incoll.inproc.crossref output.nonnull } + if$ + format.chapter.pages output + new.block + note output + fin.entry +} + +FUNCTION {inproceedings} +{ output.bibitem + format.authors "author" output.check + format.title "title" output.check + crossref missing$ + { format.in.ed.booktitle "booktitle" output.check + format.bvolume output + format.number.series output + address empty$ + { organization output + publisher output + format.date "year" output.check + } + { address output.nonnull + format.date "year" output.check + organization output + publisher output + } + if$ + } + { format.incoll.inproc.crossref output.nonnull } + if$ + format.pages output + new.block + note output + fin.entry +} + +FUNCTION {conference} { inproceedings } + +FUNCTION {manual} +{ output.bibitem + author empty$ + { format.organization output } + { format.authors output.nonnull } + if$ + format.btitle "title" output.check + author empty$ + 'skip$ + { organization output } + if$ + address output + format.edition output + format.date output + new.block + note output + fin.entry +} + +FUNCTION {mastersthesis} +{ output.bibitem + format.authors "author" output.check + format.title "title" output.check + "Master's thesis" format.thesis.type output.nonnull + school "school" output.check + address output + format.date "year" output.check + new.block + note output + fin.entry +} + +FUNCTION {misc} +{ output.bibitem + format.authors output + format.title output + howpublished new.block.checka + howpublished output + format.date output + new.block + note output + fin.entry + empty.misc.check +} + +FUNCTION {phdthesis} +{ output.bibitem + format.authors "author" output.check + format.btitle "title" output.check + "PhD thesis" format.thesis.type output.nonnull + school "school" output.check + address output + format.date "year" output.check + new.block + note output + fin.entry +} + +FUNCTION {proceedings} +{ output.bibitem + editor empty$ + { format.organization output } + { format.editors output.nonnull } + if$ + format.btitle "title" output.check + format.bvolume output + format.number.series output + address empty$ + { editor empty$ + 'skip$ + { organization output } + if$ + publisher output + format.date "year" output.check + } + { address output.nonnull + format.date "year" output.check + editor empty$ + 'skip$ + { organization output } + if$ + publisher output + } + if$ + new.block + note output + fin.entry +} + +FUNCTION {techreport} +{ output.bibitem + format.authors "author" output.check + format.title "title" output.check + format.tr.number output.nonnull + institution "institution" output.check + address output + format.date "year" output.check + new.block + note output + fin.entry +} + +FUNCTION {unpublished} +{ output.bibitem + format.authors "author" output.check + format.title "title" output.check + new.block + note "note" output.check + format.date output + fin.entry +} + +FUNCTION {default.type} { misc } + +MACRO {jan} {"Jan."} + +MACRO {feb} {"Feb."} + +MACRO {mar} {"Mar."} + +MACRO {apr} {"Apr."} + +MACRO {may} {"May"} + +MACRO {jun} {"June"} + +MACRO {jul} {"July"} + +MACRO {aug} {"Aug."} + +MACRO {sep} {"Sept."} + +MACRO {oct} {"Oct."} + +MACRO {nov} {"Nov."} + +MACRO {dec} {"Dec."} + +MACRO {acmcs} {"ACM Comput. Surveys"} + +MACRO {acta} {"Acta Inf."} + +MACRO {cacm} {"Comm. ACM"} + +MACRO {ibmjrd} {"IBM J. Res. Dev."} + +MACRO {ibmsj} {"IBM Syst.~J."} + +MACRO {ieeese} {"IEEE Trans. Softw. Eng."} + +MACRO {ieeetc} {"IEEE Trans. Comput."} + +MACRO {ieeetcad} + {"IEEE Trans. Comput.-Aided Design Integrated Circuits"} + +MACRO {ipl} {"Inf. Process. Lett."} + +MACRO {jacm} {"J.~Assoc. Comput. Mach."} + +MACRO {jcss} {"J.~Comput. System Sci."} + +MACRO {scp} {"Sci. Comput. Programming"} + +MACRO {sicomp} {"SIAM J. Comput."} + +MACRO {tocs} {"ACM Trans. Comput. Syst."} + +MACRO {tods} {"ACM Trans. Database Syst."} + +MACRO {tog} {"ACM Trans. Gr."} + +MACRO {toms} {"ACM Trans. Math. Softw."} + +MACRO {toois} {"ACM Trans. Office Inf. Syst."} + +MACRO {toplas} {"ACM Trans. Prog. Lang. Syst."} + +MACRO {tcs} {"Theoretical Comput. Sci."} + +READ + +FUNCTION {sortify} +{ purify$ + "l" change.case$ +} + +INTEGERS { len } + +FUNCTION {chop.word} +{ 's := + 'len := + s #1 len substring$ = + { s len #1 + global.max$ substring$ } + 's + if$ +} + +FUNCTION {sort.format.names} +{ 's := + #1 'nameptr := + "" + s num.names$ 'numnames := + numnames 'namesleft := + { namesleft #0 > } + { nameptr #1 > + { " " * } + 'skip$ + if$ + s nameptr "{vv{ } }{ll{ }}{ f{ }}{ jj{ }}" format.name$ 't := + nameptr numnames = t "others" = and + { "et al" * } + { t sortify * } + if$ + nameptr #1 + 'nameptr := + namesleft #1 - 'namesleft := + } + while$ +} + +FUNCTION {sort.format.title} +{ 't := + "A " #2 + "An " #3 + "The " #4 t chop.word + chop.word + chop.word + sortify + #1 global.max$ substring$ +} + +FUNCTION {author.sort} +{ author empty$ + { key empty$ + { "to sort, need author or key in " cite$ * warning$ + "" + } + { key sortify } + if$ + } + { author sort.format.names } + if$ +} + +FUNCTION {author.editor.sort} +{ author empty$ + { editor empty$ + { key empty$ + { "to sort, need author, editor, or key in " cite$ * warning$ + "" + } + { key sortify } + if$ + } + { editor sort.format.names } + if$ + } + { author sort.format.names } + if$ +} + +FUNCTION {author.organization.sort} +{ author empty$ + { organization empty$ + { key empty$ + { "to sort, need author, organization, or key in " cite$ * warning$ + "" + } + { key sortify } + if$ + } + { "The " #4 organization chop.word sortify } + if$ + } + { author sort.format.names } + if$ +} + +FUNCTION {editor.organization.sort} +{ editor empty$ + { organization empty$ + { key empty$ + { "to sort, need editor, organization, or key in " cite$ * warning$ + "" + } + { key sortify } + if$ + } + { "The " #4 organization chop.word sortify } + if$ + } + { editor sort.format.names } + if$ +} + +FUNCTION {presort} +{ type$ "book" = + type$ "inbook" = + or + 'author.editor.sort + { type$ "proceedings" = + 'editor.organization.sort + { type$ "manual" = + 'author.organization.sort + 'author.sort + if$ + } + if$ + } + if$ + " " + * + year field.or.null sortify + * + " " + * + title field.or.null + sort.format.title + * + #1 entry.max$ substring$ + 'sort.key$ := +} + +ITERATE {presort} + +SORT + +STRINGS { longest.label } + +INTEGERS { number.label longest.label.width } + +FUNCTION {initialize.longest.label} +{ "" 'longest.label := + #1 'number.label := + #0 'longest.label.width := +} + +FUNCTION {longest.label.pass} +{ number.label int.to.str$ 'label := + number.label #1 + 'number.label := + label width$ longest.label.width > + { label 'longest.label := + label width$ 'longest.label.width := + } + 'skip$ + if$ +} + +EXECUTE {initialize.longest.label} + +ITERATE {longest.label.pass} + +FUNCTION {begin.bib} +{ preamble$ empty$ + 'skip$ + { preamble$ write$ newline$ } + if$ + "\begin{thebibliography}{" longest.label * "}" * write$ newline$ +} + +EXECUTE {begin.bib} + +EXECUTE {init.state.consts} + +EXECUTE {init.last.authors} + +ITERATE {call.type$} + +FUNCTION {end.bib} +{ newline$ + "\end{thebibliography}" write$ newline$ +} + +EXECUTE {end.bib} + |