diff options
Diffstat (limited to 'Master/texmf-dist/source/latex')
| -rw-r--r-- | Master/texmf-dist/source/latex/siam/ltexconf.all | 112 | ||||
| -rw-r--r-- | Master/texmf-dist/source/latex/siam/ltexnec.all | 1923 | ||||
| -rw-r--r-- | Master/texmf-dist/source/latex/siam/ltexpprt.all | 702 | ||||
| -rw-r--r-- | Master/texmf-dist/source/latex/siam/ltexproc.all | 1784 | ||||
| -rw-r--r-- | Master/texmf-dist/source/latex/siam/ptexconf.all | 102 | ||||
| -rw-r--r-- | Master/texmf-dist/source/latex/siam/ptexnec.all | 707 | ||||
| -rw-r--r-- | Master/texmf-dist/source/latex/siam/ptexpprt.all | 724 | ||||
| -rw-r--r-- | Master/texmf-dist/source/latex/siam/ptexproc.all | 704 | ||||
| -rw-r--r-- | Master/texmf-dist/source/latex/siam/soda209.all | 682 | ||||
| -rw-r--r-- | Master/texmf-dist/source/latex/siam/soda2e.all | 688 | ||||
| -rw-r--r-- | Master/texmf-dist/source/latex/siam/sodaptex.all | 722 |
11 files changed, 0 insertions, 8850 deletions
diff --git a/Master/texmf-dist/source/latex/siam/ltexconf.all b/Master/texmf-dist/source/latex/siam/ltexconf.all deleted file mode 100644 index 2e4a638f423..00000000000 --- a/Master/texmf-dist/source/latex/siam/ltexconf.all +++ /dev/null @@ -1,112 +0,0 @@ - -Please answer the following: - -1. Name of conference - -2. Type of Presentation - Contributed: Lecture form - Poster form - Minisymposium: - -3. Equipment for Visual Support - Lecture Form/Minisymposium: - Overhead Projector - 2" x 2" Slide Projector (35mm) - Poster Form: - Easel Poster Board - Other (specify) - -More sophisticated equipment can be provided, but you may be -required to pay the rental fee. For details, indicate your -requirements below: - - -4. If you are a speaker in a minisymposium, who is the organizer? - -5. What is the minisymposium title? - -6. If more than one author, who will present the paper? - -% This is a macro file for creating a SIAM Conference abstract in -% LaTeX. -% -% If you have any questions regarding these macros contact: -% Lillian Hunt -% SIAM -% 3600 University City Center Center -% Philadelphia, PA 19104-2688 -% USA -% (215) 382-9800 -% e-mail:meetings@siam.org - - -\hsize=25.5pc -\vsize=50pc -\textheight 50pc -\textwidth 25.5pc -\parskip 0pt -\parindent 0pt -\pagestyle{plain} - -\def\title#1{\bf{#1}\vspace{6pt}} -\def\abstract#1{\rm {#1}\vspace{6pt}} -\def\author#1{\rm {#1}\vfill\eject} - -% end of style file - -% This is ltexconf.tex. Use this file as an example file for doing an SIAM -% Conference abstract in LaTeX. - - -\documentstyle[ltexconf]{report} -\begin{document} - -\title{Numerical Analysis of a 1-Dimensional -Immersed-Boundary\\ Method} - -\abstract{We present the numerical analysis of a simplified, -one-dimensional version -of Peskin's immersed boundary method, which has been used to -solve -the two- and three-dimensional Navier-Stokes equations in the -presence of immersed boundaries. We consider the heat -equation - in a finite domain with a moving source term. -We denote the solution as $u(x,t)$ and the location of the -source - term as $X(t)$. The source term is a moving delta function -whose strength is a function of u at the location of the -delta function. -The p.d.e. is coupled to an ordinary differential equation -whose -solution gives the location of the source term. - The o.d.e. is $X'(t) = u(X(t),t)$, which can be interpreted as -saying the source term moves at the local velocity. -The accuracy the numerical method of solution depends on how -the -delta function is discretized when the delta function is not -at -a grid point and on how the solution, u, is represented - at locations between grid points. We present results showing -the effect of different choices of spreading the source to -the grid and -of restricting the solution to the source location. -The problem we analyze is also similar to the Stefan problem -and -the immersed-boundary method has features in common with -particle-in-cell - methods.} - \author{\underbar{Richard P. Beyer, Jr.}\\ -University of Washington, Seattle, WA\\ -Randall J. LeVeque\\ -University of Washington, Seattle, WA} - -\end{document} - -% end of example file. - - - -Please furnish complete addresses all co-authors. - -PLEASE INDICATE WHAT CONFERENCE ABSTRACT IS FOR. diff --git a/Master/texmf-dist/source/latex/siam/ltexnec.all b/Master/texmf-dist/source/latex/siam/ltexnec.all deleted file mode 100644 index 9b22936a18c..00000000000 --- a/Master/texmf-dist/source/latex/siam/ltexnec.all +++ /dev/null @@ -1,1923 +0,0 @@ - -This file (ltexnec.all) constitutes the full distribution for NEC Proceedings -Series LaTeX version macros. The files included here are: - -ltexnec.tex (An example file, also containing documentation) - -ltexnec.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 ltexnec.tex, an example file for use with the NEC -% 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 siam.bst has been -%% included for use with BiBTeX. Please be sure to include the appropriate -%% .bib file with BiBTeX submissions. You may also submit the .bbl file -%% instead of the .bib file. -%% -%% 3. Unless otherwise stated by your editor, do your chapter as if it -%% is Chapter 1. The appropriate chapter number will be included during -%% the production of the proceedings. -%% -%% 4. This macro is set up for three levels of headings (\section, -%% \subsection, and \subsubsection). The macro will automatically number -%% the headings for you. -%% -%% 5. The running heads are indicated by the \markboth command. Please -%% define the running heads by placing the authors last names in the -%% first field and the title of the paper in the second field. -%% They should be typed initial cap and lower case. Please see the example. -%% Neither field can contain more than 50 characters including spaces, -%% so please use a shortened version of the title if necessary. For -%% papers with multiple authors please follow these rules; for -%% two authors type {Author 1 and Author 2}; for more that two authors type -%% {Author 1 et al.}. -%% -%% 6. 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. -%% -%% 7. 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. -%% -%% 8. 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. SIAM supports the use of -%% psfig for including Postscript figures. All Postscript figures should be -%% sent as separate files. A hardcopy version of all Postscript figures -%% is also required. See note regarding this under How to Submit Your Paper. -%% -%% 9. 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. -%% -%% 10. Special fonts. -%% SIAM supports the use of AMS-TeX fonts version 2.0 and later. As -%% described in the manual for these fonts, they can be included by -%% \input{amssym.def} and \input{amssym.tex}. These macros are not yet -%% updated to make use of the New Font Selection Scheme (NFSS) of -%% Mittelbach and Schopf. To make these macros compatible with NFSS, use -%% the oldlfont style option. -%% -%% 11. How to Submit Your Paper. -%% The electronic version of your paper should be sent to proceed@siam.org. -%% A hardcopy version must also be submitted. Instructions are included -%% in your acceptance letter. Please be sure to send hardcopy -%% versions of any Postscript figures you have submitted electronically. -%% Be sure to return your signed Copyright Transfer Agreement. We cannot -%% publish your paper without it. -%% -%% -%% -%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%- -%%% - - -\documentstyle[leqno,twoside,11pt,ltexnec]{article} %You must set up your - %\documentstyle line like this. - - -\begin{document} -\cleardoublepage -\pagestyle{myheadings} - -\title{Chapter 1\\ -NEC 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 -\markboth{Gray et al.}{SIAM Proceedings Series Macros} % See section 5 above - % for explanation. -\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.~Schrieber, {\em A new implementation of sparse gaussian elimination}, - ACM TOMS, 8 (1982), pp.~256--276. - -\end{thebibliography} - -\end{document} - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%CUT HERE%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -% -% -% 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 NEC Proceedings series using LaTeX. - -% Report the version. -\message{*** NEC LaTeX Proceedings Series macro package, version 1.0, -July 10, 1992 ***} -%\input proceed.sty - -\pretolerance=800 -\tolerance=10000 -\sloppy - - -\vsize=49pc -\hsize=30pc -\baselineskip=13pt -\hoffset -.5in -\voffset -.5in -\footskip=18pt -\topmargin 24pt -\headheight 12pt -\headsep 17pt -\textheight 49pc \advance\textheight by \topskip -\textwidth 30pc -\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\@evenfoot{{\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}{\small\leftmark}\hfil}% - -\def\@oddhead{\hfil{\noindent\small\rightmark}\hspace*{2pc}{\rm\thepage}}% - -% \def\chaptermark##1{\markboth{\uppercase{% - % {\protect\small\@chapapp}\ -%{\protect\small\thechapter}}}% - % {\uppercase{##1}}}% - } - - -\def\ps@myheadings{\let\@mkboth\@gobbletwo - \def\@oddfoot{}\def\@evenfoot{}% - -\def\@oddhead{\hfil{\small\rightmark}\hspace*{2pc}{\normalsize\rm\thepage}} -% - -\def\@evenhead{{\normalsize\rm\thepage}\hspace*{2pc}{\small\leftmark}\hfil} -% -% \def\chaptermark##1{}% - % \def\sectionmark##1{}\def\subsectionmark##1{}} -} - - - -\def\theequation{\arabic{equation}} -%\def\theequation{\arabic{chapter}.\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\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{Corollary}{Corollary}[section] -\newtheorem{Definition}{Definition}[section] -\newtheorem{Lemma}{Lemma}[section] -\newtheorem{Remark}{Remark}[section] - -\newproof{Example}{Example} -\newproof{Method}{Method} -\newproof{Exercise}{Exercise} - -\def\qed{{\qquad \vbox{\hrule\hbox{% - \vrule height1.3ex\hskip0.8ex\vrule}\hrule - }}\par} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -% % -% 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} - - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -% % -% CHAPTER % -% % -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%\def\@chapapp{Chapter} - -%\def\@makechapterhead#1{% - % \vspace*{8pt} - % \vtop to 11pc{\leftskip=0pc \parindent 0pt - % \begin{center}{\large \@chapapp}%\end{flushright}%%% - % {\large \baselineskip=26pt\ \thechapter}\end{center}\vskip-8pt -% \vrule width 31pc height .5pt\par % - % \vspace*{6pt}% - % \baselineskip=18pt\begin{center}{\Large#1 }\end{center}\par - % \vfil}} - -%\def\@makeschapterhead#1{% - % \vspace*{8pt} - % \vtop to 11pc{\leftskip=0pc \parindent 0pt - % \vtop to 26pt{\vfill}\vskip-8pt - % \vrule width 31pc height .5pt\par % -% % \vspace*{6pt}% - % {\Large #1}\par - % \vfil}} - - -%\def\chapter{\cleardoublepage \thispagestyle{plain} \global\@topnum\z@ - % \@afterindentfalse \secdef\@chapter\@schapter} - -%\def\author#1{\vspace*{-6.25pc}\begin{center}{#1}\end{center} - % \par\vspace*{4pc}} -%\def\chaptermark#1{} - -%\def\@chapter[#1]#2{% - % \refstepcounter{chapter} - % \typeout{Chapter\space\thechapter.} -% % \addcontentsline{toc}{chapter}{CHAPTER\ \thechapter. #1} - % \protect\addtocontents{lof}{\protect\addvspace{10pt}} - % \protect\addtocontents{lot}{\protect\addvspace{10pt}} - % \chaptermark{#1} - % \@makechapterhead{#2} - % \@afterheading} - - - -%\def\@schapter#1{\@makeschapterhead{#1} - % \@afterheading} - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -% % -% SECTIONS % -% % -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -\def\section{\@startsection {section}{1}{\z@}{-3.5ex plus -1ex minus - -.2ex}{2.3ex plus .2ex}{\large\bf}} -\def\subsection{\@startsection{subsection}{2}{\z@}{-3.25ex plus -1ex minus - -.2ex}{1.5ex plus .2ex}{\large\bf}} -\def\subsubsection{\@startsection{subsubsection}{3}{\z@}{-3.25ex plus - -1ex minus -.2ex}{1.5ex plus .2ex}{\large\bf}} -%\renewcommand{\section}{\@startsection {section}{1}{\z@}{-3.5ex plus -1ex -%minus -% -.2ex}{2.3ex plus .2ex}{\large\bf}} - -%\def\@sect#1#2#3#4#5#6[#7]#8{\ifnum #2>\c@secnumdepth -% \def\@svsec{}\else -% \refstepcounter{#1}\edef\@svsec{\csname the#1\endcsname.\hskip .75em -%}\fi% -% - % \@tempskipa #5\relax - % \ifdim \@tempskipa>\z@ - % \begingroup #6\relax - % \@hangfrom{\hskip #3\relax\@svsec}{\interlinepenalty \@M #8\par} - % \endgroup -% \csname #1mark\endcsname{#7}\addcontentsline - %{toc}{#1}{\ifnum #2>\c@secnumdepth \else - % \protect\numberline{\csname the#1\endcsname}\fi - % #7}\else - % \def\@svsechd{#6\hskip #3\@svsec #8\hskip1em\csname #1mark\endcsname - - % {#7}\addcontentsline - % {toc}{#1}{\ifnum #2>\c@secnumdepth \else - % \protect\numberline{\csname the#1\endcsname}\fi - % #7}}\fi - % \@xsect{#5}} - - - %\@startsection {NAME}{LEVEL}{INDENT}{BEFORESKIP}{AFTERSKIP}{STYLE} -%\def\section{\@startsection{section}{1}{0pt}{-12pt}{3pt}{\hyphenpenalty=\@ -%M -%\exhyphenpenalty=\@M\normalsize\bf}} -%\def\subsection{\@startsection{subsection}{2}{0pt}{-12pt}{0pt}{\normalsize -%\bf} -%} -%\def\subsubsection{\@startsection -% {subsubsection}{3}{0pt}{-12pt}{0pt}{\normalsize\bf}} -%\def\paragraph{\@startsection -% {paragraph}{4}{\parindent}{0pt}{0pt}{\normalsize\bf}} -%\def\subparagraph{\@startsection -% {subparagraph}{4}{\parindent}{0pt}{0pt}{\normalsize\bf}} -%\def\thepart{\Roman{part}} -%\def\thesection {\arabic{section}.} -%\def\thesubsection {\thesection\arabic{subsection}.} -%\def\thesubsubsection {\thesubsection .\arabic{subsubsection}.} -%\def\theparagraph {\thesubsubsection.\arabic{paragraph}.} -%\def\thesubparagraph {\theparagraph.\arabic{subparagraph}.} - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -% % -% TOC % -% % -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%% sets chapter in toc -%\def\l@chapter#1#2{\pagebreak[3] -% \hbox to \hsize{\null\hskip2pc -% \llap{\hbox to\@pnumwidth{\hss#2}\hskip2pc}% -% #1\hfill}\vskip1pc} - - -%%% set so only chapters print in TOC -%\def\@dottedtocline#1#2#3#4#5{\relax} - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% %% -%% 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=12pt - \advance\leftmargin\labelsep - \usecounter{enumi}\@bibsetup} -\def\newblock{\hskip .11em plus .33em minus -.07em} - \sloppy\clubpenalty4000\widowpenalty4000 - \sfcode`\.=1000\relax} - -%\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} -%%{}{\settowidth\labelwidth{mm} -%\leftmargin\labelwidth -%\advance -%\leftmargin 0pt \itemindent -16pt -% \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 original style file - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%CUT HERE%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - -% 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}
\ No newline at end of file diff --git a/Master/texmf-dist/source/latex/siam/ltexpprt.all b/Master/texmf-dist/source/latex/siam/ltexpprt.all deleted file mode 100644 index 907e77cfeec..00000000000 --- a/Master/texmf-dist/source/latex/siam/ltexpprt.all +++ /dev/null @@ -1,702 +0,0 @@ -%% This is ltexpprt.all. This file is to be used for creating a paper -%% in the ACM/SIAM Preprint series with LaTeX. It consists of the following -%% two files: -%% -%% ltexpprt.tex ---- an example and documentation file -%% ltexpprt.sty ---- the macro file -%% -%% To use, cut this file apart at the appropriate places. You can run the -%% example file with the macros to get sample output. -%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%% CUT HERE %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -% -% -%%%%%%%%%%%%%%%%%%%%%%%%%% ltexpprt.tex %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -% -% This is ltexpprt.tex, an example file for use with the SIAM LaTeX -% Preprint Series macros. It is designed to provide double-column output. -% Please take the time to read the following comments, as they document -% 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 Preprint 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. If you are using BibTeX, please -%% supply the bst file with the manuscript file. -%% -%% 3. Unless otherwise stated by your editor, do your chapter as if it -%% is Chapter 1. -%% If you know which number your chapter is, you must do the following: -%% -%% Use the \setcounter command to set the counters for chapter, -%% section, and page number to the appropriate number. The counter -%% for chapter is incremental, so it should be set one less than -%% the actual chapter number. The section counter is not -%% incremental. Set the page counter to 1. The following example -%% is set up as if it were chapter 3. Please note the placement of -%% the three \setcounter commands and follow it exactly. -%% -%% 4. This macro is set up for two levels of headings (\section and -%% \subsection). The macro will automatically number the headings for you. -%% -%% 5. The running heads are defined by the \markboth command. The left running -%% head (the first field of the \markboth command) should be defined with -%% the authors names. The right running head (the second field of the -%% \markboth command) should be defined with the title (or shortened title) -%% of your chapter. Neither running head may be more than 40 characters. -%% -%% 6. Theorems, Lemmas, Definitions, etc. are to be triple numbered, -%% indicating the chapter, section, and the occurence of that element -%% within that section. (For example, the first theorem in the second -%% section of chapter three would be numbered 3.2.1. The macro will -%% automatically do the numbering for you. -%% -%% 7. Figures, equations, and tables must be double-numbered indicating -%% chapter and occurence. Use existing LaTeX tags for these elements. -%% Numbering will be done automatically. -%% -%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - - -\documentstyle[twoside,leqno,twocolumn,ltexpprt]{article} - -\begin{document} - - -%\setcounter{chapter}{2} % If you are doing your chapter as chapter one, -%\setcounter{section}{3} % comment these two lines out. - -\title{\large\bf Chapter 1 \\ -\Large SIAM/ACM Preprint Series Macros for -Use With LaTeX\thanks{Supported by GSF grants ABC123, DEF456, and GHI789.}} -\author{Corey Gray\thanks{Society for Industrial and Applied Mathematics.} \\ -\and -Tricia Manning\thanks{Society for Industrial and Applied Mathematics.}} -\date{} - -\maketitle - -\pagestyle{myheadings} -\markboth{AUTHORS NAMES}{CHAPTER TITLE} - -%\pagenumbering{arabic} -%\setcounter{page}{1}%Leave this line commented out. - -\begin{abstract} \small\baselineskip=9pt This is the text of my abstract. It is a brief -description of my -paper, outlining the purposes and goals I am trying to address.\end{abstract} - -\section{Problem Specification.}In this paper, we consider the solution of the $N \times -N$ linear -system -\begin{equation} \label{e1.1} -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} - -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. -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. -\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} - -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. -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. - -\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} - -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 -[4] - [10], [5], [6]. In \S 1.3., we analyze the complexity of the old and new -approaches to the intersection problem for the special case of -an $n \times n$ grid ordered by nested dissection. The special -structure of this problem allows us to make exact estimates of -the complexity. 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 -[4] - [10], [5], [6]. - -In \S 1.2, we review the bordering algorithm, and introduce -the sorting and intersection problems that arise in the -sparse formulation of the algorithm. -In \S 1.3., we analyze the complexity of the old and new -approaches to the intersection problem for the special case of -an $n \times n$ grid ordered by nested dissection. The special -structure of this problem allows us to make exact estimates of -the complexity. 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 -[4] - [10], [5], [6]. - - -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. For the -new approach, the complexity of the second part is reduced to -$O(n^{2} (\log n)^{2})$. - -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 -[4] - [10], [5], [6]. In \S 1.3., we analyze the complexity of the old and new -approaches to the intersection problem for the special case of -an $n \times n$ grid ordered by nested dissection. The special -structure of this problem allows us to make exact estimates of -the complexity. 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 -[4] - [10], [5], [6]. -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} - -\begin{figure} -\vspace{14pc} -\caption{This is a figure 1.1.} -\end{figure} - -\section{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. - -\subsection{Versatility.}\ 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})$. - -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 -[4] - [10], [5], [6]. In \S 1.3., we analyze the complexity of the old and new -approaches to the intersection problem for the special case of -an $n \times n$ grid ordered by nested dissection. The special -structure of this problem allows us to make exact estimates of -the complexity. 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 -[4] - [10], [5], [6]. - -In \S 1.2, we review the bordering algorithm, and introduce -the sorting and intersection problems that arise in the -sparse formulation of the algorithm. -In \S 1.3., we analyze the complexity of the old and new -approaches to the intersection problem for the special case of -an $n \times n$ grid ordered by nested dissection. The special -structure of this problem allows us to make exact estimates of -the complexity. 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 -[4] - [10], [5], [6]. - - -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. For the -new approach, the complexity of the second part is reduced to -$O(n^{2} (\log n)^{2})$. - -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 -[4] - [10], [5], [6]. In \S 1.3., we analyze the complexity of the old and new -approaches to the intersection problem for the special case of -an $n \times n$ grid ordered by nested dissection. The special -structure of this problem allows us to make exact estimates of -the complexity. 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 -[4] - [10], [5], [6]. -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}. - -\begin{thebibliography}{99} - -%\bibitem{GUIDE} -%R.~E. Bank, {\em PLTMG users' guide, edition 5.0}, tech. report, -% Department of Mathematics, University of California, San Diego, CA, 1988. - -%\bibitem{HBMG} -%R.~E. Bank, T.~F. Dupont, and H.~Yserentant, {\em The hierarchical basis -% multigrid method}, Numer. Math., 52 (1988), pp.~427--458. - -\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.~Schrieber, {\em A new implementation of sparse gaussian elimination}, - ACM TOMS, 8 (1982), pp.~256--276. - -\end{thebibliography} -\end{document} - -% End of ltexpprt.tex -% -% -% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% CUT HERE %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -% -% -% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% ltexpprt.sty %%%%%%%%%%%%%%%%%%%%%%%%%%%%% -% -% This is ltexpprt.sty, a file of macros and definitions for creating a -% chapter for publication in the ACM/SIAM Preprint series using LaTeX. -% It is designed to produce double-column output. -% 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 - - -% Report the version. -\message{*** ACM/SIAM LaTeX Preprint Series macro package, version 1.0, -September 24,1990 ***} - - -\pretolerance=800 -\tolerance=10000 -\sloppy - -\voffset=-.5in -\hoffset=-.5in -\vsize=55pc -\hsize=41pc -\baselineskip=14pt -\footskip=18pt -\topmargin 24pt -\headheight 12pt -\headsep 17pt -\textheight 52.5pc \advance\textheight by \topskip -\textwidth 41pc -\parskip 0pt -\parindent 18pt - -\font\tensmc=cmcsc10 -\def\smc{\tensmc} - -%% footnotes to be set 8/10 -\def\footnotesize{\@setsize\footnotesize{10pt}\viiipt\@viiipt - % \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} % 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}\hfil{\small\leftmark}}% - \def\@oddhead{{\noindent\small\rightmark}\hfil{\rm\thepage}}% - - - -\def\ps@myheadings{\let\@mkboth\@gobbletwo - \def\@oddfoot{}\def\@evenfoot{}% - \def\@oddhead{\rlap{\normalsize\rm\rightmark}\hfil{small\thepage}}% - \def\@evenhead%{\hfil{\small\@chapapp}\ - {\small\thepage}\hfil\llap{\normalsize\rm\leftmark}}% - \def\chaptermark##1{}% - \def\sectionmark##1{}\def\subsectionmark##1{}} - - -\def\theequation{\arabic{section}.\arabic{equation}} - - -\def\section{\@startsection{section}{1}{0pt}{-12pt}{3pt}{\hyphenpenalty=\@M -\exhyphenpenalty=\@M\normalsize\bf}} -\def\subsection{\@startsection{subsection}{2}{0pt}{-12pt}{0pt}{\normalsize\bf} -} -\def\subsubsection{\@startsection - {subsubsection}{3}{0pt}{-12pt}{0pt}{\normalsize\bf}} -\def\paragraph{\@startsection - {paragraph}{4}{\parindent}{0pt}{0pt}{\normalsize\bf}} -\def\subparagraph{\@startsection - {subparagraph}{4}{\parindent}{0pt}{0pt}{\normalsize\bf}} - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -% % -% THEOREMS, PROOFS, ALGORITHMS % -% % -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%% defined proof environment by theorem model (took out counter) - -\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 \trivlist \item[\hskip \labelsep{\it #1.\/}]} -\def\@endproof{\outerparskip 0pt\endtrivlist} - -\def\@begintheorem#1#2{\it \trivlist \item[\hskip \labelsep{\sc #1\ #2.}]} -\def\@opargbegintheorem#1#2#3{\it \trivlist - \item[\hskip \labelsep{\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{Corollary}[Theorem]{Corollary} -\newtheorem{Definition}{Definition}[section] -\newtheorem{Lemma}{Lemma}[section] -\newtheorem{Remark}{Remark}[section] - -\newproof{Example}{Example} -\newproof{Method}{Method} -\newproof{Exercise}{Exercise} - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% %% -%% BIBLIOGRAPHY %% -%% %% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - -\def\thebibliography#1{% -%\cleardoublepage -\parindent 0em -\vspace{6pt} -\begin{flushleft}\normalsize\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 - \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} - -% -%% End of ltexpprt.sty -% -%%%%%%%%%%%%%%%%%%%%%%%%% End of ltexpprt.all %%%%%%%%%%%%%%%%%%%%%%% -
\ No newline at end of file diff --git a/Master/texmf-dist/source/latex/siam/ltexproc.all b/Master/texmf-dist/source/latex/siam/ltexproc.all deleted file mode 100644 index 61283eec0aa..00000000000 --- a/Master/texmf-dist/source/latex/siam/ltexproc.all +++ /dev/null @@ -1,1784 +0,0 @@ - - -This file constitutes the full distribution for SIAM Proceedings -Series LaTeX version macros. The files included here are: - -ltexproc.tex (An example file, also containing documentation) - -ltexproc.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 ltexproc.tex, an example file for use with the SIAM LaTeX -% 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. Please be sure to include the appropriate -%% .bib file with BiBTeX submissions. You may also submit the .bbl file -%% instead of the .bib file. -%% -%% 3. Unless otherwise stated by your editor, do your chapter as if it -%% is Chapter 1. The appropriate chapter number will be included during -%% the production of the proceedings. -%% -%% 4. This macro is set up for three levels of headings (\section, -%% \subsection, and \subsubsection). The macro will automatically number -%% the headings for you. -%% -%% 5. The running heads are indicated by the \markboth command. Please -%% define the running heads by placing the authors last names in the -%% first field and the title of the paper in the second field. -%% They should be typed initial cap and lower case. Please see the example. -%% Neither field can contain more than 50 characters including spaces, -%% so please use a shortened version of the title if necessary. For -%% papers with multiple authors please follow these rules; for -%% two authors type {Author 1 and Author 2}; for more that two authors type -%% {Author 1 et al.}. -%% -%% 6. 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. -%% -%% 7. 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. -%% -%% 8. 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. SIAM supports the use of -%% psfig for including Postscript figures. All Postscript figures should be -%% sent as separate files. A hardcopy version of all Postscript figures -%% is also required. See note regarding this under How to Submit Your Paper. -%% -%% 9. 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. -%% -%% 10. Special fonts. -%% SIAM supports the use of AMS-TeX fonts version 2.0 and later. As -%% described in the manual for these fonts, they can be included by -%% \input{amssym.def} and \input{amssym.tex}. These macros are not yet -%% updated to make use of the New Font Selection Scheme (NFSS) of -%% Mittelbach and Schopf. To make these macros compatible with NFSS, use -%% the oldlfont style option. -%% -%% 11. How to Submit Your Paper. -%% The electronic version of your paper should be sent to proceed@siam.org. -%% A hardcopy version should also be submitted. Instructions are included -%% in your acceptance letter. Please be sure to send hardcopy -%% versions of any Postscript figures you have submitted electronically. -%% Be sure to return your signed Copyright Transfer Agreement. We cannot -%% publish your paper without it. -%% -%% -%% -%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%- -%%% - - -\documentstyle[leqno,twoside,11pt,ltexproc]{article} %You must set up your - %\documentstyle line like this. - - -\begin{document} -\cleardoublepage -\pagestyle{myheadings} - -\title{Chapter 1\\ -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 -\markboth{Gray et al.}{SIAM Proceedings Series Macros} % See section 5 above - % for explanation. -\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 ltexproc.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 LaTeX. - -% Report the version. -\message{*** SIAM LaTeX Proceedings Series macro package, version 1.0, -November 6, 1992 ***} - -\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} - diff --git a/Master/texmf-dist/source/latex/siam/ptexconf.all b/Master/texmf-dist/source/latex/siam/ptexconf.all deleted file mode 100644 index 06e2a7f38ae..00000000000 --- a/Master/texmf-dist/source/latex/siam/ptexconf.all +++ /dev/null @@ -1,102 +0,0 @@ - -Please answer the following: - -1. Name of conference -2. Type of Presentation - Contributed: Lecture form or Poster form - Minisymposium: - -3. Equipment for Visual Support - Lecture form/Minisymposium: Overhead Projector or - 2" x 2" Slide Projector (35mm) - - Poster form: Easel or Poster Board - -4. If you are a speaker in a minisymposium, who is the organizer? - -5. What is the minisymposium title? - -6. If more than one author, who will present the paper? - - -%This is a macro file for creating a SIAM Conference abstract in -% Plain Tex. -% -% If you have any questions regarding these macros contact: -% Lillian Hunt -% SIAM -% 3600 University City Center Center -% Philadelphia, PA 19104-2688 -% USA -% (215) 382-9800 -% e-mail:meetings@siam.org - - -\hsize=25.5pc -\vsize=50pc -\parskip=3pt -\parindent=0pt -\overfullrule=0pt -\nopagenumbers - -\def\title#1\\{\bf{#1}\vskip6pt} -\def\abstract#1\\{\rm {#1}} -\def\author#1\\{\vskip6pt\rm {#1}\vfill\eject} -\def\eol{\hfill\break} - -% end of style file - -% This is ptexconf.tex. Use this file as an example of a SIAM -% Conference abstract in plain TeX. - -\input ptexconf.sty - -\title Numerical Analysis of a 1-Dimensional -Immersed-Boundary Method\\ - -\abstract We present the numerical analysis of a simplified, -one-dimensional version -of Peskin's immersed boundary method, which has been used to -solve -the two- and three-dimensional Navier-Stokes equations in the -presence of immersed boundaries. We consider the heat -equation - in a finite domain with a moving source term. -We denote the solution as $u(x,t)$ and the location of the -source - term as $X(t)$. The source term is a moving delta function -whose strength is a function of u at the location of the -delta function. -The p.d.e. is coupled to an ordinary differential equation -whose -solution gives the location of the source term. - The o.d.e. is $X'(t) = u(X(t),t)$, which can be interpreted as -saying the source term moves at the local velocity. -The accuracy the numerical method of solution depends on how -the -delta function is discretized when the delta function is not -at -a grid point and on how the solution, u, is represented - at locations between grid points. We present results showing -the effect of different choices of spreading the source to -the grid and -of restricting the solution to the source location. -The problem we analyze is also similar to the Stefan problem -and -the immersed-boundary method has features in common with -particle-in-cell - methods.\\ - \author\underbar{Richard P. Beyer, Jr.}\eol -University of Washington, Seattle, WA\eol -%\vskip3pt -Randall J. LeVeque\eol -University of Washington, Seattle, WA\\ -\bye - -% end of example file - - -Please furnish complete addresses for all co-authors. - - -PLEASE BE SURE TO INDICATE WHAT CONFERENCE THE ABSTRACT IS FOR.
\ No newline at end of file diff --git a/Master/texmf-dist/source/latex/siam/ptexnec.all b/Master/texmf-dist/source/latex/siam/ptexnec.all deleted file mode 100644 index 2da4cfce16f..00000000000 --- a/Master/texmf-dist/source/latex/siam/ptexnec.all +++ /dev/null @@ -1,707 +0,0 @@ - - -This file (ptexnec.all) constitutes the full distribution of NEC Proceedings Series -Plain TeX macros. The files are: - -ptexnec.tex (An example file, also containing documentation) - -ptexnec.sty (the style file) - -To use these macros, separate at the indicated cut lines. - -%%%%%%%%%%%%%%%%%%%%%%%%%CUT HERE%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -% This is ptexnec.tex, an example file for use with the NEC Plain TeX -% Proceedings Series macros. Comments are placed at the beginning and -% throughout this file. Please take the time to read them as they document -% how to use these macros. This file can be composed and printed out for -% use as sample output. Please ignore the underfull \vbox on page 3. - -% 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. You must use the numbered reference style([1],[2]), listing the -%% references at the end of the chapter either by order of citation -%% or alphabetically. -%% -%% 2. This macro is set up for three levels of headings. Use the commands -%% \headone, \headtwo, and \headthree. The macro will automatically -%% number the headings. -%% -%% 3. The running heads are defined by the commands \def\leftrh{} and -%% \def\rightrh{}. You must fill in the empty field of these commands -%% with the appropriate information. The left running head should be the -%% authors names. For papers with multiple authors, please follow these -%% rules; for two authors type {Author 1 and Author 2}; for more than two -%% authors type {Author 1 et al.}. The right running head is the title of -%% the paper. If the title is more than 50 characters, including spaces, -%% please provide a shortened version. All information should be typed -%% initial cap and lower case. -%% -%% 5. 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.) This numbering must -%% be done manually. -%% -%% 6. Proofs are handled by \prf\endprf. If you want to use an end-of-proof -%% box, insert \qed right before the \endprf command. -%% -%% 7. Figures and equations must be manually single-numbered. Use \leqno -%% for equation numbering. The macro provides the \fig for including -%% figures. This command consists of three fields. The first field is -%% used for inserting the appropriate space for the figure. The second -%% field is the figure number. The third field is the caption. See the -%% example included in this file. SIAM supports the use of psfig for -%% including Postscript figures. All Postscript figures should be sent -%% as separate files. A hardcopy version of all Postscript figures is -%% also required. See note regarding this under How to Submit Your Paper. -%% -%% 8. Use of \title\endtitle and \lasttitle\endlastitle. -%% This macro package provides two possible commands for handling the -%% title of your paper. The commands \title\endtitle should be used for -%% all lines except the last line of multiple line titles. The commands -%% \lasttitle\endlasttitle should be used for the last line of multiple -%% line titles. In the case of a single line title, \lasttitle\endlasttitle -%% should be used. -%% -%% 9. Use of \author\endauthor and \lastauthor\endlastauthor. -%% As in the title macro, two possible commands are provided for the -%% author. The commands \author\endauthor should be used for the first -%% line of authors if there are more than one line. The commands -%% \lastauthor\endlastauthor should be used for the last line -%% of multiple lines of authors. In the case of a single line of authors, -%% \lastauthor\endlastauthor should be used. A maximum of four authors -%% should be placed on any one line. The appropriate space must also be -%% hard coded between authors on the same line. The spacing is as follows: -%% -%% If 2 authors; \hskip4pc between -%% If 3 authors; \hskip3pc between -%% If 4 authors; \hskip2pc between -%% -%% 10. Grant information and author affiliations. -%% This information is included by using the \footnote command and the -%% appropriate footnote symbol. SIAM uses footnote symbols in a -%% particular order. Below is a list of these symbols: -%% -%% asterisk -%% single-dagger -%% double-dagger -%% section sign -%% paragraph -%% parallel -%% double asterisk -%% double single-dagger -%% double double-dagger -%% -%% For illustrative purposes, all footnote symbols have been used in the -%% example file. -%% -%% A note regarding \footnote. This command seems to leave extra white -%% space between footnotes. This is quite evident in the example file. If -%% any user of these macros has a solution to this problem, I would -%% appreciate hearing from you. Send your comments to: gray@siam.org. -%% -%% The following general rules apply for including grants and affiliations: -%% 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, included the grant information -%% with each authors 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. -%% -%% -%% 11. Special fonts. -%% SIAM supports the use of AMS-TeX fonts version 2.0 and later. As -%% described in the manual for these fonts, they can be included by -%% \input{amssym.def} and \input{amssym.tex}. -%% -%% 12. How to Submit Your Paper. -%% The electronic version of your paper should be sent to proceed@siam.org. -%% A hardcopy version should also be submitted. Instructions are included -%% in your acceptance letter. Please be sure to send hardcopy -%% versions of any Postscript figures you have submitted electronically. -%% Be sure to return your signed Copyright Transfer Agreement. We cannot -%% publish your paper without one.%% -%% -%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -\input ptexnec.sty - -\def\leftrh{Gray et al.} -\def\rightrh{NEC Proceedings Series Macros} - -\startchapter %Place this command at the beginning of the file immediately - %after the \input command. - - - -\title Chapter 1\endtitle -\title NEC Proceedings Series Macros\endtitle -\lasttitle for Use with Plain TeX\footnote*{Any information -regarding grants should be placed here.}\endlasttitle - -\author J. Corey Gray\footnote{$^{\dag}$}{Production Manager, Society for -Industrial and Applied Mathematics, Philadelphia, PA.} -\hskip2truepc Tricia Manning\footnote{$^{\ddag}$}{Publications -Specialist, Society for Industrial and Applied Mathematics, Philadelphia, -PA.} -\hskip2truepc Vickie Kearn\footnote{$^{\S}$}{Publisher, Society for Industrial -and Applied Mathematics, Philadelphia, PA.} -\hskip2truepc Nancy Abbott\footnote{$^{\P}$}{Design Supervisor, Society for -Industrial and Applied Mathematics, Philadelphia, PA.} -\endauthor -\lastauthor Sue Ciambrano\footnote{$^{\parallel}$}{Acquisition Editor, Society for -Industrial and Applied Mathematics, Philadelphia, PA.} -\hskip2truepc Paul Duggan\footnote{$^{**}$}{Composition -Specialist, Society for Industrial and Applied Mathematics, Philadelphia, -PA.} -\hskip2truepc Robbi Anne Albert\footnote{$^{\dagger\dagger}$}{Production, -Assistant, Society for Industrial -and Applied Mathematics, Philadelphia, PA.} -\hskip2truepc Jean Anderson\footnote{$^{\ddag\ddag}$}{Composition Coordinator, Society for -Industrial and Applied Mathematics, Philadelphia, PA.} -\endlastauthor - -% Use \headone for the first level headings. The macro will automatically -% number the headings. - -\centerline{\bf Abstract} -\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.\endabstract - - -\headone{Problem Specification} -In this paper, we consider the solution of the $N \times N$ linear -system -$$A x = b\leqno (1)$$ -where $A$ is large, sparse, symmetric, and positive definite. We consider -the direct solution of 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} -\leqno (2)$$ - -\noindent where $L$ is unit lower triangular and $D$ is diagonal. - - -\headone{Design Considerations} -Several good ordering algorithms (nested dissection and minimum degree) -are available for computing $P$ [1], [2]. -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$. - -% Use \thm and \endthm for theorems. They must be numbered manually. -% Lemmas (\lem \endlem), corollaries (\cor \endcor), and -% propositions (\prop \endprop) are coded the same as theorems and must -% also be numbered manually. - -\thm{Theorem 2.1.} 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.\endthm - -Several good ordering algorithms (nested dissection and minimum degree) -are available for computing $P$ [1], [2]. -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$. -Several good ordering algorithms (nested dissection and minimum degree) -are available for computing $P$ [1], [2]. -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$. - -% Use \prf and \endprf to begin and end a proof. -% The use of \qed will produce an end-of-proof box. - -\prf{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 each.\qed\endprf - -% Use \dfn and \enddfn to begin and end definitions. - -\dfn{Definition 2.1.}We describe the two methods in \S\ 1.2. This is a -definition in the plain tex macro.\enddfn - -This is accomplished by exploiting the m-tree, -a particular spanning tree for the graph of the filled-in matrix. -Our purpose here is to examine the nonnumerical complexity of the -sparse elimination algorithm given in [3]. -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. - - -Our purpose here is to examine the nonnumerical complexity of the -sparse elimination algorithm given in [3]. -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. -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$. - -% Use \lem and \endlem to begin and end lemmas. - -\lem{Lemma 2.1.}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$. -\endlem - -% Use \fig to insert space for figures . - -\fig{10pc}{Fig. 1}{This is the caption for figure one.} - -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 -[4] - [10], [5], [6]. In \S 1.3., we analyze the complexity of the old and new -approaches to the intersection problem for the special case of -an $n \times n$ grid ordered by nested dissection. The special -structure of this problem allows us to make exact estimates of -the complexity. 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 -[4] - [10], [5], [6]. - -% Use \headtwo for second level headings. They will be numbered automatically. - -\headtwo{Robustness}In \S 1.2, we review the bordering algorithm, and introduce -the sorting and intersection problems that arise in the -sparse formulation of the algorithm. - -\headtwo{Versatility} In \S 1.3., we analyze the complexity of the old and new -approaches to the intersection problem for the special case of -an $n \times n$ grid ordered by nested dissection. The special -structure of this problem allows us to make exact estimates of -the complexity. 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 -[4] - [10], [5], [6]. - - -% Use \headthree for third level headings. - -\headthree{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. For the -new approach, the complexity of the second part is reduced to -$O(n^{2} (\log n)^{2})$. - -% The command \Refs sets the word Reference as a heading and allows the proper -% amount of space before the start of the references. Each reference must -% begin with \ref\\. The article or title of the reference should be in -% italic. Use the \it command within brackets. End each reference with -% \endref and allow two returns between references. Use the command -% \sameauthor (see reference 8) when the same author or group of authors -% is listed consecutively. - -\Refs - -\ref 1\\R.~E. Bank, {\it PLTMG users' guide, edition 5.0}, tech. report, - Department of Mathematics, University of California, San Diego, CA, 1988.\endref - -\ref 2\\R.~E. Bank, T.~F. Dupont, and H.~Yserentant, {\it The hierarchical basis - multigrid method}, Numer. Math., 52 (1988), pp.~427--458.\endref - -\ref 3\\R.~E. Bank and R.~K. Smith, {\it General sparse elimination requires no - permanent integer storage}, SIAM J. Sci. Stat. Comput., 8 (1987), - pp.~574--584.\endref - -\ref 4\\S.~C. Eisenstat, M.~C. Gursky, M.~Schultz, and A.~Sherman, {\it - Algorithms and data structures for sparse symmetric gaussian elimination}, - SIAM J. Sci. Stat. Comput., 2 (1982), pp.~225--237.\endref - -\ref 5\\A.~George and J.~Liu, {\it Computer Solution of Large Sparse Positive - Definite Systems}, Prentice Hall, Englewood Cliffs, NJ, 1981.\endref - -\ref 6\\K.~H. Law and S.~J. Fenves, {\it A node addition model for symbolic - factorization}, ACM TOMS, 12 (1986), pp.~37--50.\endref - -\ref 7\\J.~W.~H. Liu, {\it A compact row storage scheme for cholesky factors - using elimination trees}, ACM TOMS, 12 (1986), pp.~127--148.\endref - -\ref 8\\\sameauthor , {\it The role of - elimination trees in sparse factorization}, Tech. Report CS-87-12,Department - of Computer Science, York University, Ontario, Canada, 1987.\endref - -\ref 9\\D.~J. Rose, {\it A graph theoretic study of the numeric solution of - sparse positive definite systems}, in Graph Theory and Computing, - Academic Press, New York, 1972.\endref - -\ref 10\\D.~J. Rose, R.~E. Tarjan, and G.~S. Lueker, {\it Algorithmic aspects of - vertex elimination on graphs}, SIAM J. Comput., 5 (1976), pp.~226--283.\endref - -\vfill\eject - -Extra page. -\vfill -\bye -%%% End of example file - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%CUT HERE%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -% 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 NEC Proceedings Series using Plain TeX. - -% Report the version. -\message{*** NEC Plain TeX Proceedings Series macro package, version 1.0, -November 6, 1992.***} - -% Make the @ sign a letter for internal control sequences. -\catcode`\@=11 -% -% -% - - -\baselineskip=14truept - - -%%% DIMENSIONS %%% - -\hsize=30truepc -\vsize=49truepc -%\hoffset=.5in -\parindent=18truept -\def\firstpar{\parindent=0pt\global\everypar{\parindent=18truept}} -\parskip=0pt - - -%%% FONTS %%% - -\font\tenrm=cmr10 -\font\tenbf=cmbx10 -\font\tenit=cmti10 -\font\tensmc=cmcsc10 -\def\tenpoint{% - \def\rm{\tenrm}\def\bf{\tenbf}% - \def\it{\tenit}\def\smc{\tensmc} - \textfont0=\tenrm \scriptfont0=\sevenrm - \textfont1=\teni \scriptfont1=\seveni - \textfont2=\tensy \scriptfont2=\sevensy - \textfont3=\tenex \scriptfont3=\tenex -\baselineskip=12pt\rm}% - -\font\ninerm=cmr9 -\font\ninebf=cmbx9 -\font\nineit=cmti9 -\def\ninepoint{% - \def\rm{\ninerm}\def\bf{\ninebf}% - \def\it{\nineit}\baselineskip=11pt\rm}% - -\font\eightrm=cmr8 -\font\eightbf=cmbx8 -\font\eightit=cmti8 -\font\eighti=cmmi8 -\font\eightsy=cmsy8 -\def\eightpoint{% - \def\rm{\eightrm}\def\bf{\eightbf}% - \def\it{\eightit}\def\smc{\eightrm}\baselineskip=10pt\rm% - \textfont0=\eightrm \scriptfont0=\sixrm - \textfont1=\eighti \scriptfont1=\sixi - \textfont2=\eightsy \scriptfont2=\sixsy - \textfont3=\tenex \scriptfont3=\tenex -} - -\font\sixrm=cmr6 -\font\sixbf=cmbx6 -\font\sixi=cmmi6 -\font\sixsmc=cmr5 -\font\sixsy=cmsy6 -\def\sixpoint{% - \def\rm{\sixrm}\def\bf{\sixbf}% - \def\smc{\sixsmc}\baselineskip=8pt\rm}% - -\fontdimen13\tensy=2.6pt -\fontdimen14\tensy=2.6pt -\fontdimen15\tensy=2.6pt -\fontdimen16\tensy=1.2pt -\fontdimen17\tensy=1.2pt -\fontdimen18\tensy=1.2pt - -\font\eightrm=cmr8 -\font\ninerm=cmr9 -\font\elevenrm=cmr10 scaled\magstephalf -\font\fourteenrm=cmr10 scaled\magstep 1 -\font\eighteenrm=cmr10 scaled\magstep 3 -\font\twelvebf=cmbx10 scaled\magstep 1 -\font\elevenbf=cmbx10 scaled\magstephalf -\font\elevenit=cmti10 scaled\magstephalf -\font\elevensc=cmcsc10 scaled\magstephalf - -\def\theoremfont{\elevensc} -\def\textfont{\elevenrm} -\def\itfont{\elevenit} -\def\headfont{\twelvebf} -\def\smallheadfont{\elevenbf} -\def\titlefont{\eighteenrm} -\def\chapterfont{\fourteenrm} -\def\authorfont{\fourteenrm} -\def\rheadfont{\tenrm} -\def\abstractfont{\tenrm} -\def\smc{\tensmc} -\font\eightsmc=cmcsc8 - -\def\footnote#1{\baselineskip=11truept\edef\@sf{\spacefactor\the\spacefactor}#1\@sf - \insert\footins\bgroup\ninepoint\hsize=36pc - \interlinepenalty10000 \let\par=\endgraf - \leftskip=0pt \rightskip=0pt - \splittopskip=10pt plus 1pt minus 1pt \floatingpenalty=20000 -\smallskip -\item{#1}\bgroup\baselineskip=10pt\strut -\aftergroup\@foot\let\next} -\skip\footins=12pt plus 2pt minus 4pt -\dimen\footins=36pc - - - -%%% CHAPTER OPENING MACROS %%% - -\def\startchapter{\topinsert\vglue54pt\endinsert} - -\def\title#1\endtitle{\titlefont\centerline{#1}\vglue5pt}%\vskip40truept\tenrm} -\def\lasttitle#1\endlasttitle{\titlefont\centerline{#1}\vskip1.32truepc} -\def\author#1\endauthor{\authorfont\centerline{#1}\vglue8pt\textfont} -\def\lastauthor#1\endlastauthor{\authorfont\centerline{#1}\vglue2.56pc\textfont} -\def\abstract#1\endabstract{\baselineskip=12pt\leftskip=2.25pc - \rightskip=2.25pc\abstractfont{#1}\textfont} - -%%% COUNTERS FOR HEADINGS %%% - -\newcount\headcount -\headcount=1 -\newcount\seccount -\seccount=1 -\newcount\subseccount -\subseccount=1 -\def\secreset{\global\seccount=1} - \def\subsecreset{\global\subseccount=1} - -%%% HEADINGS %%% - -\def\headone#1{\baselineskip=14pt\leftskip=0pt\rightskip=0pt\vskip17truept\parindent=0pt -{\headfont\the\headcount\hskip14truept #1} -\par\nobreak\firstpar\global\advance\headcount by 0 - \global\advance\headcount by 1\secreset\vskip2truept\textfont} - -\def\headtwo#1{\advance\headcount by -1% - \vskip17truept\parindent=0pt{\headfont\the\headcount.% - \the\seccount\hskip14truept #1}%\enspace\ignorespaces\firstpar - \global\advance\headcount by 1\global\advance\seccount by 1 - \global\advance\subseccount by 1\subsecreset\vskip2pt\textfont} - - \def\headthree#1{\advance\headcount by -1\advance\seccount by -1 -% \advance\subseccount by -1% - \vskip17truept\parindent=0pt{\smallheadfont\the\headcount.% - \the\seccount.\the\subseccount\hskip11truept #1}\hskip6pt\ignorespaces - \firstpar\global\advance\headcount by 1\global\advance\seccount by 1 - \global\advance\subseccount by 1\textfont} - -%%% THEOREMS, PROOFS, DEFINITIONS, etc. %%% - -\def\thm#1{{\theoremfont -#1\enspace} -\hskip-5pt\begingroup\itfont\ignorespaces} - -\let\lem=\thm -\let\cor=\thm -\let\prop=\thm - -\def\endthm{\endgroup\textfont} -\let\endlem=\endthm -\let\endcor=\endthm -\let\endprop=\endthm - -\def\prf#1{{\itfont #1.}\textfont\enspace\ignorespaces} -\let\rem=\prf -\let\case=\prf - -\def\endprf{\textfont} -\let\endrem=\endprf -\let\endcase=\endprf - -\def\qed{{\qquad \vbox{\hrule\hbox{% - \vrule height1.3ex\hskip0.8ex\vrule}\hrule - }}\par} - -\def\dfn#1{{\theoremfont -#1\enspace} -\textfont\ignorespaces} - -\let\fact=\dfn - -\def\enddfn{\textfont} - -\let\endfact=\enddfn - -%%% FIGURES AND CAPTIONS %%% - - -\newcount\figcount -\figcount=1 - - -%\newcount\tablenumber -%\tablenumber=1 - -\def\\{\hfill\break} - -\newbox\TestBox -\newdimen\setwd -\newskip\belowcaptionskip -\belowcaptionskip=6pt plus 1pt - -\def\endinsert{\egroup % finish the \vbox - \if@mid \dimen@\ht\z@ \advance\dimen@\dp\z@ - \advance\dimen@12\p@ \advance\dimen@\pagetotal - \ifdim\dimen@>\pagegoal\@midfalse\p@gefalse\fi\fi - \if@mid\vskip\belowcaptionskip\box\z@\par \penalty-200\vskip\belowcaptionskip - \else\insert\topins{\penalty100 % floating insertion - \splittopskip\z@skip - \splitmaxdepth\maxdimen \floatingpenalty\z@ - \ifp@ge \dimen@\dp\z@ - \vbox to\vsize{\unvbox\z@\kern-\dimen@}% depth is zero - \else \box\z@\nobreak\vskip\belowcaptionskip\fi}\fi\endgroup} - - - - -\def\fig#1#2#3{% - \setbox\TestBox=\hbox{\tenpoint #3.}\setwd=\wd\TestBox - \topinsert - \vskip #1 - \vskip 12pt - \ifdim\setwd > 23pc - {\tenit{\smc #2.}\ \ #3} - \else - \centerline{\tenit\noindent - {\smc #2.}\ \ #3}\fi% - % \global\advance\figcount by 1 - \endinsert} - - - -%%% REFERENCES %%% - -\newdimen\refindent@ -\newdimen\refhangindent@ -\newbox\refbox@ -\setbox\refbox@=\hbox{\tenrm\baselineskip=11pt [00]}% Default 2 digits -\refindent@=\wd\refbox@ - -\def\resetrefindent#1{% - \setbox\refbox@=\hbox{\tenrm\baselineskip=11pt [#1]}% - \refindent@=\wd\refbox@} - -\def\Refs{% - \unskip\vskip1pc - \leftline{\noindent\headfont References}% - \penalty10000 - \vskip4pt - \penalty10000 - \refhangindent@=\refindent@ - \global\advance\refhangindent@ by .5em - \global\everypar{\hangindent\refhangindent@}% - \parindent=0pt\baselineskip=12pt\tenrm} - -\def\sameauthor{\leavevmode\vbox to 1ex{\vskip 0pt plus 100pt - \hbox to 2em{\leaders\hrule\hfil}\vskip 0pt plus 300pt}} - -\def\ref#1\\#2\endref{\leavevmode\hbox to \refindent@{\hfil[#1]}\enspace #2\par} - - -%%% OUTPUT %%% - -\def\rightheadline{\hfill\tenrm\rightrh\hskip2pc\tenrm\folio} -\def\leftheadline{\tenrm\folio\hskip2pc\tenrm\leftrh\hfill} - -\global\footline={\hss\tenrm\folio\hss}% first page - -\output{\plainoutput} -\def\plainoutput{\shipout\vbox{\makeheadline\pagebody\makefootline}% - \advancepageno - \ifnum\pageno>1 - \global\footline={\hfill}% - \fi - \ifodd\pageno - \global\headline={\rightheadline}% - \else - \global\headline={\leftheadline}% - \fi - \ifnum\outputpenalty>-\@MM \else\dosupereject\fi} -\def\pagebody{\vbox to\vsize{\boxmaxdepth\maxdepth \pagecontents}} -\def\makeheadline{\vbox to\z@{\vskip-22.5\p@ - \line{\vbox to8.5\p@{}\rheadfont\the\headline}\vss}% - \nointerlineskip} -\def\makefootline{\baselineskip24\p@\vskip-6\p@\line{\the\footline}} -\def\dosupereject{\ifnum\insertpenalties>\z@ % something is being held over - \line{}\kern-\topskip\nobreak\vfill\supereject\fi} - -\def\footnoterule{\vskip11pt\kern -4\p@\hrule width 3pc \kern 3.6\p@ } % rule = .4 pt high - -% Turn off @ as being a letter. -% -\catcode`\@=13 - -%end of style file - diff --git a/Master/texmf-dist/source/latex/siam/ptexpprt.all b/Master/texmf-dist/source/latex/siam/ptexpprt.all deleted file mode 100644 index fb644d0fdf3..00000000000 --- a/Master/texmf-dist/source/latex/siam/ptexpprt.all +++ /dev/null @@ -1,724 +0,0 @@ -%% This is ptexpprt.all. This file is to be used for creating a paper -%% in the ACM/SIAM Preprint series with Plain TeX. It consists of the following -%% two files: -%% -%% ptexpprt.tex ---- an example and documentation file -%% ptexpprt.sty ---- the macro file -%% -%% To use, cut this file apart at the appropriate places. You can run the -%% example file with the macros to get sample output. -%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%% CUT HERE %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -% -% -%%%%%%%%%%%%%%%%%%%%%%%%%% ptexpprt.tex %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -% -% This is ptexpprt.tex, an example file for use with the ACM/SIAM Plain TeX -% Preprint Series macros. It is designed to produce double-column output. -% Comments are placed at the beginning and throughout this file. Please -% take the time to read them as they document 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: siampubs@wharton.upenn.edu - - -% 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. You must use the numbered reference style([1],[2]), listing the -%% references at the end of the chapter either by order of citation -%% or alphabetically. -%% -%% 2. Unless otherwise stated by your editor, do your chapter as if it -%% is Chapter 1. -%% If you know which number your chapter is, you must do the following: -%% -%% Go into the style file (ptexfrnt.sty) and search for the -%% \def\chapter#1 definition. At the end of this definition -%% there is a command \headcount=1. Change the 1 to -%% the appropriate number. This change will cause the headings -%% in your chapter to match the chapter number. -%% -%% 3. This macro is set up for two levels of headings. The macro will -%% automatically number the headings for you. -%% -%% 4. The running heads are defined in the output routine. It will be -%% necessary for you to alter the information currently included. -%% To do this, go into the style file and search for OUTPUT. Once there, -%% scroll through the file until you see the command \def\rhead. Replace -%% CHAPTER TITLE with the title (or shortened title) of your paper. -%% Replace AUTHORS NAMES with the appropriate names. -%% Neither running head may be longer than 50 characters. -%% -%% 5. Theorems, Lemmas, Definitions, etc. are to be triple numbered, -%% indicating the chapter, section, and the occurence of that element -%% within that section. (For example, the first theorem in the second -%% section of chapter three would be numbered 3.2.1. This numbering must -%% be done manually. -%% -%% 6. Figures and equations must be manually double-numbered, indicating -%% chapter and occurence. Use \leqno for equation numbering. See the -%% example of \caption for figure numbering. -%% Note. Although not shown, tables must also be double-numbered. The -%% command \caption can also be used for table captions. -%% -%% 7. At the first occurence of each new element there is a description -%% of how to use the coding. -%% -%%%%%%% PLEASE NOTE THE FOLLOWING POTENTIAL PROBLEMS: -% -%% 1. A bug exists that prevents a page number from printing on the first -%% page of the paper. Please ignore this problem. It will be handled -%% after you submit your paper. -%% -%% 2. The use of \topinsert and \midinsert to allow space for figures can -%% result in unusual page breaks, or unusual looking pages in general. -%% If you encounter such a situation, contact the SIAM office at the -%% address listed above for instructions. -%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -\input ptexpprt.sty -\voffset=.25in -\titlepage - -% It will be necessary to hard code the chapter title and chapter authors. -% You must decide where to break the lines. For the authors, please follow -% the following conventions: -% 1. If 2 authors are on a line, use \hskip4pc between them. If 3 authors, -% use \hskip2pc. Do not put more than 3 authors on the same line. -% 2. Use the following notation: asterisk, dagger, double-dagger, section -% symbol, paragraph symbol, double asterisk. If more are needed, contact -% the SIAM office. - -\centerline{\chapterfont Chapter 1} -\vskip2pt -\centerline{\titlefont SIAM/ACM Preprint Series Macros for -Plain TeX\footnote*{Supported by GSF grants ABC123, DEF456, and GHI 789.}} -\vskip15pt -\centerline{\authorfont J. Corey Gray\footnote\dag{Society for Industrial and -Applied Mathematics.}\hskip2pc Tricia Manning\footnote\ddag{Society for -Industrial and Applied Mathematics.}\hskip2pc Vickie Kearn\footnote\S{Society -for Industrial and Applied Mathematics.}} -\vskip2pc - -\begindoublecolumns - -% Use \headone for the first level headings. The macro will automatically -% number the headings. - -\headone{Problem Specification} -In this paper, we consider the solution of the $N \times N$ linear -system -$$A x = b\leqno(1.1)$$ -where $A$ is large, sparse, symmetric, and positive definite. We consider -the direct solution of 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. - -\headone{Design Considerations} -Several good ordering algorithms (nested dissection and minimum degree) -are available for computing $P$ [1], [2]. -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$. - -% Use \headtwo for second level headings. They will be numbered automatically. - -\headtwo{Robustness}In \S 1.2, we review the bordering algorithm, and introduce -the sorting and intersection problems that arise in the -sparse formulation of the algorithm. - -\headtwo{Versatility} In \S 1.3., we analyze the complexity of the old and new -approaches to the intersection problem for the special case of -an $n \times n$ grid ordered by nested dissection. The special -structure of this problem allows us to make exact estimates of -the complexity. 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 -[4] - [10], [5], [6]. -This is accomplished by exploiting the m-tree, -a particular spanning tree for the graph of the filled-in matrix. -Our purpose here is to examine the nonnumerical complexity of the -sparse elimination algorithm given in [3]. -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. - - -% Use \thm and \endthm for theorems. They must be numbered manually. -% Lemmas (\lem \endlem), corollaries (\cor \endcor), and -% propositions (\prop \endprop) are coded the same as theorems and must -% also be numbered manually. - -\thm{Theorem 2.1.} 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.\endthm - -Several good ordering algorithms (nested dissection and minimum degree) -are available for computing $P$ [1], [2]. -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$. -Several good ordering algorithms (nested dissection and minimum degree) -are available for computing $P$ [1], [2]. -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$. - -% Use \prf to begin a proof. - -\prf{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 each. - -% Use \dfn to begin definitions. - -\dfn{Definition 1.2.1.}We describe the two methods in \S\ 1.2. This is a -definition in the plain tex macro. - -This is accomplished by exploiting the m-tree, -a particular spanning tree for the graph of the filled-in matrix. -Our purpose here is to examine the nonnumerical complexity of the -sparse elimination algorithm given in [3]. -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. -Our purpose here is to examine the nonnumerical complexity of the -sparse elimination algorithm given in [3]. -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. -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$. - - -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 -[4] - [10], [5], [6]. In \S 1.3., we analyze the complexity of the old and new -approaches to the intersection problem for the special case of -an $n \times n$ grid ordered by nested dissection. The special -structure of this problem allows us to make exact estimates of -the complexity. 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 -[4] - [10], [5], [6]. -Several good ordering algorithms (nested dissection and minimum degree) -are available for computing $P$ [1], [2]. -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$. -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. For the -new approach, the complexity of the second part is reduced to -$O(n^{2} (\log n)^{2})$. - -% Use \midinsert along with \caption to allow space for -% figures. See note above in problem section. -%\midinsert\vskip15.5pc\caption{Fig. 1.1. {\nineit This is figure 1.}} -% \endcaption\endinsert - -In this paper, we consider the solution of the $N \times N$ linear -system -where $A$ is large, sparse, symmetric, and positive definite. We consider -the direct solution of by means of general sparse Gaussian -elimination. In such a procedure, we find a permutation matrix $P$, and -compute the decomposition -where $L$ is unit lower triangular and $D$ is diagonal. - -\headone{Design Considerations} -Several good ordering algorithms (nested dissection and minimum degree) -are available for computing $P$ [1], [2]. -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$. - -Several good ordering algorithms (nested dissection and minimum degree) -are available for computing $P$ [1], [2]. -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$. -Several good ordering algorithms (nested dissection and minimum degree) -are available for computing $P$ [1], [2]. -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 [3]. -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. -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$. - -% Use \lem and \endlem to begin and end lemmas. - -\lem{Lemma 2.1.}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$. -\endlem - -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 -[4] - [10], [5], [6]. In \S 1.3., we analyze the complexity of the old and new -approaches to the intersection problem for the special case of -an $n \times n$ grid ordered by nested dissection. The special -structure of this problem allows us to make exact estimates of -the complexity. 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 -[4] - [10], [5], [6]. - -% Use \headtwo for second level headings. They will be numbered automatically. - -\headone{Problem Solving}In \S 1.2, we review the bordering algorithm, and -introduce -the sorting and intersection problems that arise in the -sparse formulation of the algorithm. - -\headtwo{Versatility} In \S 1.3., we analyze the complexity of the old and new -approaches to the intersection problem for the special case of -an $n \times n$ grid ordered by nested dissection. The special -structure of this problem allows us to make exact estimates of -the complexity. 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 -[4] - [10], [5], [6]. - - -\headtwo{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. For the -new approach, the complexity of the second part is reduced to -$O(n^{2} (\log n)^{2})$. - -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 -[4] - [10], [5], [6]. In \S 1.3., we analyze the complexity of the old and new -approaches to the intersection problem for the special case of -an $n \times n$ grid ordered by nested dissection. The special -structure of this problem allows us to make exact estimates of -the complexity. 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 -[4] - [10], [5], [6]. - -% The command \Refs sets the word Reference as a heading and allows the proper -% amount of space before the start of the references. Each reference must -% begin with \ref\\. The article or title of the reference should be in -% italic. Use the \it command within brackets. End each reference with -% \endref and allow two returns between references. Use the command -% \sameauthor (see reference 8) when the same author or group of authors -% is listed consecutively. - -\Refs - -\ref 1\\R.~E. Bank, {\it PLTMG users' guide, edition 5.0}, tech. report, - Department of Mathematics, University of California, San Diego, CA, -1988.\endref - -\ref 2\\R.~E. Bank, T.~F. Dupont, and H.~Yserentant, {\it The hierarchical basis - multigrid method}, Numer. Math., 52 (1988), pp.~427--458.\endref - -\ref 3\\R.~E. Bank and R.~K. Smith, {\it General sparse elimination requires no - permanent integer storage}, SIAM J. Sci. Stat. Comput., 8 (1987), - pp.~574--584.\endref - -\ref 4\\S.~C. Eisenstat, M.~C. Gursky, M.~Schultz, and A.~Sherman, {\it - Algorithms and data structures for sparse symmetric gaussian elimination}, - SIAM J. Sci. Stat. Comput., 2 (1982), pp.~225--237.\endref - -\ref 5\\A.~George and J.~Liu, {\it Computer Solution of Large Positive - Definite Systems}, Prentice Hall, Englewood Cliffs, NJ, 1981.\endref - -\ref 6\\K.~H. Law and S.~J. Fenves, {\it A node addition model for symbolic - factorization}, ACM TOMS, 12 (1986), pp.~37--50.\endref - -\ref 7\\J.~W.~H. Liu, {\it A compact row storage scheme for factors - using elimination trees}, ACM TOMS, 12 (1986), pp.~127--148.\endref - -\ref 8\\\sameauthor , {\it The role of - elimination trees in sparse factorization}, Tech. Report CS-87-12,Department - of Computer Science, York University, Ontario, Canada, 1987.\endref - -\ref 9\\D.~J. Rose, {\it A graph theoretic study of the numeric solution of - sparse positive definite systems}, in Graph Theory and Computing, - Academic Press, New York, 1972.\endref - -\ref 10\\D.~J. Rose, R.~E. Tarjan, and G.~S. Lueker, {\it Algorithmic aspects of - vertex elimination on graphs}, SIAM J. Comput., 5 (1976), pp.~226--283.\endref -\enddoublecolumns - -\bye -%% -%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%% CUT HERE %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -% -% -%%%%%%%%%%%%%%%%%%%%%%%%%% ptexpprt.sty %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -% -% This is a file of macros and definitions for creating a chapter -% for publication in the ACM/SIAM Preprint Series using Plain TeX. -% 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: siampubs@wharton.upenn.edu - -% - -% Report the version. -\message{*** ACM/SIAM Plain TeX Preprint Series macro package, version 1.0, -September 24, 1990.***} - -% Make the @ sign a letter for internal control sequences. -\catcode`\@=11 -% -% -% - - - -%%% DIMENSIONS %%% - -\newdimen\pagewidth -\hsize=41pc -\pagewidth=\hsize -\newdimen\pageheight -\vsize=50pc -\pageheight=\vsize -\newdimen\ruleht -\ruleht=.5pt -\maxdepth=2.2pt - -\parindent=18truept -\def\firstpar{\parindent=0pt\global\everypar{\parindent=18truept}} -\parskip=0pt plus 1pt - - -%%% FONTS %%% - -\font\tenrm=cmr10 -\font\tenbf=cmbx10 -\font\tenit=cmti10 -\font\tensmc=cmcsc10 -\def\tenpoint{% - \def\rm{\tenrm}\def\bf{\tenbf}% - \def\it{\tenit}\def\smc{\tensmc} - \textfont0=\tenrm \scriptfont0=\sevenrm - \textfont1=\teni \scriptfont1=\seveni - \textfont2=\tensy \scriptfont2=\sevensy - \textfont3=\tenex \scriptfont3=\tenex -\baselineskip=12pt\rm}% - -\font\ninerm=cmr9 -\font\ninebf=cmbx9 -\font\nineit=cmti9 -\def\ninepoint{% - \def\rm{\ninerm}\def\bf{\ninebf}% - \def\it{\nineit}\baselineskip=11pt\rm}% - -\font\eightrm=cmr8 -\font\eightbf=cmbx8 -\font\eightit=cmti8 -\font\eighti=cmmi8 -\font\eightsy=cmsy8 -\def\eightpoint{% - \def\rm{\eightrm}\def\bf{\eightbf}% - \def\it{\eightit}\def\smc{\eightrm}\baselineskip=10pt\rm% - \textfont0=\eightrm \scriptfont0=\sixrm - \textfont1=\eighti \scriptfont1=\sixi - \textfont2=\eightsy \scriptfont2=\sixsy - \textfont3=\tenex \scriptfont3=\tenex -} - -\font\sixrm=cmr6 -\font\sixbf=cmbx6 -\font\sixi=cmmi6 -\font\sixsmc=cmr5 -\font\sixsy=cmsy6 -\def\sixpoint{% - \def\rm{\sixrm}\def\bf{\sixbf}% - \def\smc{\sixsmc}\baselineskip=8pt\rm}% - -\fontdimen13\tensy=2.6pt -\fontdimen14\tensy=2.6pt -\fontdimen15\tensy=2.6pt -\fontdimen16\tensy=1.2pt -\fontdimen17\tensy=1.2pt -\fontdimen18\tensy=1.2pt - -\font\eightrm=cmr8 -\font\ninerm=cmr9 -\font\twelverm=cmr10 scaled\magstep1 -\font\twelvebf=cmbx10 scaled\magstep 1 -\font\sixteenrm=cmr10 scaled\magstep2 -\def\titlefont{\sixteenrm} -\def\chapterfont{\twelvebf} -\def\authorfont{\twelverm} -\def\rheadfont{\tenrm} -\def\smc{\tensmc} - - - - -%%% COUNTERS FOR HEADINGS %%% - -\newcount\headcount -\headcount=1 -\newcount\seccount -\seccount=1 -\newcount\subseccount -\subseccount=1 -\def\reset{\global\seccount=1} -\global\headcount=0 - -%%% HEADINGS %%% - -\def\headone#1{\global\advance\headcount by 1 -\vskip12truept\parindent=0pt{\tenpoint\bf\the\headcount -\hskip11truept #1.}\par\nobreak\firstpar\global\advance\headcount by 0 - %\global\advance\seccount by 1 -\reset\vskip2truept} - -\def\headtwo#1{%\advance\seccount by -1% - \vskip12truept\parindent=0pt{\tenpoint\bf\the\headcount.% - \the\seccount\hskip11truept #1.}\enspace\ignorespaces\firstpar - \global\advance\headcount by 0\global\advance\seccount by 1} -% \global\advance\subseccount by 1} - - -%%% THEOREMS, PROOFS, DEFINITIONS, etc. %%% - -\def\thm#1{{\smc -#1\enspace} -\begingroup\it\ignorespaces\firstpar} - -\let\lem=\thm -\let\cor=\thm -\let\prop=\thm - -\def\endthm{\endgroup} -\let\endlem=\endthm -\let\endcor=\endthm -\let\endprop=\endthm - -\def\prf#1{{\it #1.}\rm\enspace\ignorespaces} -\let\rem=\prf -\let\case=\prf - - -\def\dfn#1{{\smc -#1\enspace} -\rm\ignorespaces} - - - -%%% FIGURES AND CAPTIONS %%% - -\def\caption#1\endcaption{\vskip18pt\ninerm\centerline{#1}\vskip18pt\tenrm} - -\newinsert\topins \newif\ifp@ge \newif\if@mid -\def\topinsert{\@midfalse\p@gefalse\@ins} -\def\midinsert{\@midtrue\@ins} -\def\pageinsert{\@midfalse\p@getrue\@ins} -\skip\topins=0pt %no space added when a topinsert is present -\count\topins=1000 %magnification factor (1 to 1) -\dimen\topins=\maxdimen -\def\@ins{\par\begingroup\setbox0=\vbox\bgroup} -\def\endinsert{\egroup - \if@mid \dimen@=\ht0 \advance\dimen@ by\dp0 - \advance\dimen@ by12\p@ \advance\dimen@ by\pagetotal - \ifdim\dimen@>\pagegoal \@midfalse\p@gefalse\fi\fi - \if@mid \bigskip \box0 \bigbreak - \else\insert\topins{\penalty100 - \splittopskip=0pt \splitmaxdepth=\maxdimen \floatingpenalty=0 - \ifp@ge \dimen@=\dp0 - \vbox to\vsize{\unvbox0 \kern-\dimen@} - \else \box0 \nobreak\bigskip\fi}\fi\endgroup} - - -%%% REFERENCES %%% - -\newdimen\refindent@ -\newdimen\refhangindent@ -\newbox\refbox@ -\setbox\refbox@=\hbox{\ninepoint\rm\baselineskip=11pt [00]}% Default 2 digits -\refindent@=\wd\refbox@ - -\def\resetrefindent#1{% - \setbox\refbox@=\hbox{\ninepoint\rm\baselineskip=11pt [#1]}% - \refindent@=\wd\refbox@} - -\def\Refs{% - \unskip\vskip1pc - \leftline{\noindent\tenpoint\bf References}% - \penalty10000 - \vskip4pt - \penalty10000 - \refhangindent@=\refindent@ - \global\advance\refhangindent@ by .5em - \global\everypar{\hangindent\refhangindent@}% - \parindent=0pt\ninepoint\rm} - -\def\sameauthor{\leavevmode\vbox to 1ex{\vskip 0pt plus 100pt - \hbox to 2em{\leaders\hrule\hfil}\vskip 0pt plus 300pt}} - -\def\ref#1\\#2\endref{\leavevmode\hbox to \refindent@{\hfil[#1]}\enspace #2\par} - - -%%% OUTPUT %%% - -\newinsert\margin -\dimen\margin=\maxdimen -\count\margin=0 \skip\margin=0pt - - -\def\footnote#1{\edef\@sf{\spacefactor\the\spacefactor}#1\@sf - \insert\footins\bgroup\eightpoint\hsize=30pc - \interlinepenalty100 \let\par=\endgraf - \leftskip=0pt \rightskip=0pt - \splittopskip=10pt plus 1pt minus 1pt \floatingpenalty=20000 -\smallskip -\item{#1}\bgroup\strut\aftergroup\@foot\let\next} -\skip\footins=6pt plus 2pt minus 4pt -\dimen\footins=30pc - -\newif\iftitle - - -\def\titlepage{\global\titletrue\footline={\hss\ninepoint\rm\folio\hss}} -\def\rhead{\ifodd\pageno CHAPTER TITLE - \else AUTHORS NAMES\fi} - -\def\makefootline{\ifnum\pageno>1\global\footline={\hfill}\fi - \baselineskip24\p@\vskip12\p@\fullline{\the\footline}} -\def\leftheadline{\hbox to \pagewidth{ - \vbox to 10pt{} - {\kern-8pt\tenrm\folio\hfill\ninerm\rhead}}} -\def\rightheadline{\hbox to \pagewidth{ - \vbox to 10pt{} - \kern-8pt\ninerm\rhead\hfil - {\kern-1pc\tenrm\folio}}} - -\def\onepageout#1{\shipout\vbox{ -\offinterlineskip - \vbox to 2.25pc{% - \iftitle \global\titlefalse -% \setcornerrules - \else\ifodd\pageno\rightheadline\else\leftheadline\fi\fi \vfill} -\vbox to \pageheight{ - \ifvoid\margin\else - \rlap{\kern31pc\vbox to0pt{\kern4pt\box\margin \vss}}\fi - #1 % -\ifvoid\footins\else - \vskip\skip\footins \kern 0pt - \hrule height\ruleht width 2.5pc \kern-\ruleht \kern 0pt - \unvbox\footins\fi -\boxmaxdepth=\maxdepth}} -\advancepageno} - -\def\setcornerrules{\hbox to \pagewidth{ - \vrule width 1pc height\ruleht \hfil \vrule width 1pc} - \hbox to \pagewidth{\llap{\sevenrm(page \folio)\kern1pc} - \vrule height1pc width\ruleht depth0pt - \hfil \vrule width\ruleht depth0pt}} -\output{\onepageout{\unvbox255}} - -\newbox\partialpage -\def\begindoublecolumns{\begingroup - \output={\global\setbox\partialpage=\vbox{\unvbox255\bigskip}}\eject - \output={\doublecolumnout} \hsize=20pc \vsize=101pc} -\def\enddoublecolumns{\output={\balancecolumns}\eject - \endgroup \pagegoal=\vsize} - -\def\doublecolumnout{\splittopskip=\topskip \splitmaxdepth=\maxdepth - \dimen@=50pc \advance\dimen@ by-\ht\partialpage - \setbox0=\vsplit255 to\dimen@ \setbox2=\vsplit255 to\dimen@ - \onepageout\pagesofar \unvbox255 \penalty\outputpenalty} -\def\pagesofar{\unvbox\partialpage - \wd0=\hsize \wd2=\hsize \hbox to\pagewidth{\box0\hfil\box2}} -\def\balancecolumns{\setbox0=\vbox{\unvbox255} \dimen@=\ht0 - \advance\dimen@ by\topskip \advance\dimen@ by-\baselineskip - \divide\dimen@ by2 \splittopskip=\topskip -{\vbadness=10000 \loop \global\setbox3=\copy0 - \global\setbox1=\vsplit3 to\dimen@ - \ifdim\ht3>\dimen@ \global\advance\dimen@ by1pt \repeat} - \setbox0=\vbox to\dimen@{\unvbox1} \setbox2=\vbox to\dimen@{\unvbox 3} -\pagesofar} - - - - -% Turn off @ as being a letter. -% -\catcode`\@=13 - -% End of ptexpprt.sty - - -CUT HERE............ diff --git a/Master/texmf-dist/source/latex/siam/ptexproc.all b/Master/texmf-dist/source/latex/siam/ptexproc.all deleted file mode 100644 index 728b5da243d..00000000000 --- a/Master/texmf-dist/source/latex/siam/ptexproc.all +++ /dev/null @@ -1,704 +0,0 @@ - - -This file constitutes the full distribution of SIAM Proceedings Series -Plain TeX macros. The files are: - -ptexproc.tex (An example file, also containing documentation) - -ptexproc.sty (the style file) - -To use these macros, separate at the indicated cut lines. - -%%%%%%%%%%%%%%%%%%%%%%%%%CUT HERE%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -% This is ptexproc.tex, an example file for use with the SIAM Plain TeX -% Proceedings Series macros. Comments are placed at the beginning and -% throughout this file. Please take the time to read them as they document -% how to use these macros. This file can be composed and printed out for -% use as sample output. Please ignore the underfull \vbox on page 3. - -% 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. You must use the numbered reference style([1],[2]), listing the -%% references at the end of the chapter either by order of citation -%% or alphabetically. -%% -%% 2. This macro is set up for three levels of headings. Use the commands -%% \headone, \headtwo, and \headthree. The macro will automatically -%% number the headings. -%% -%% 3. The running heads are defined by the commands \def\leftrh{} and -%% \def\rightrh{}. You must fill in the empty field of these commands -%% with the appropriate information. The left running head should be the -%% authors names. For papers with multiple authors, please follow these -%% rules; for two authors type {Author 1 and Author 2}; for more than two -%% authors type {Author 1 et al.}. The right running head is the title of -%% the paper. If the title is more than 50 characters, including spaces, -%% please provide a shortened version. All information should be typed -%% initial cap and lower case. -%% -%% 5. 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.) This numbering must -%% be done manually. -%% -%% 6. Proofs are handled by \prf\endprf. If you want to use an end-of-proof -%% box, insert \qed right before the \endprf command. -%% -%% 7. Figures and equations must be manually single-numbered. Use \leqno -%% for equation numbering. The macro provides the \fig for including -%% figures. This command consists of three fields. The first field is -%% used for inserting the appropriate space for the figure. The second -%% field is the figure number. The third field is the caption. See the -%% example included in this file. SIAM supports the use of psfig for -%% including Postscript figures. All Postscript figures should be sent -%% as separate files. A hardcopy version of all Postscript figures is -%% also required. See note regarding this under How to Submit Your Paper. -%% -%% 8. Use of \title\endtitle and \lasttitle\endlastitle. -%% This macro package provides two possible commands for handling the -%% title of your paper. The commands \title\endtitle should be used for -%% all lines except the last line of multiple line titles. The commands -%% \lasttitle\endlasttitle should be used for the last line of multiple -%% line titles. In the case of a single line title, \lasttitle\endlasttitle -%% should be used. -%% -%% 9. Use of \author\endauthor and \lastauthor\endlastauthor. -%% As in the title macro, two possible commands are provided for the -%% author. The commands \author\endauthor should be used for the first -%% line of authors if there are more than one line. The commands -%% \lastauthor\endlastauthor should be used for the last line -%% of multiple lines of authors. In the case of a single line of authors, -%% \lastauthor\endlastauthor should be used. A maximum of four authors -%% should be placed on any one line. The appropriate space must also be -%% hard coded between authors on the same line. The spacing is as follows: -%% -%% If 2 authors; \hskip4pc between -%% If 3 authors; \hskip3pc between -%% If 4 authors; \hskip2pc between -%% -%% 10. Grant information and author affiliations. -%% This information is included by using the \footnote command and the -%% appropriate footnote symbol. SIAM uses footnote symbols in a -%% particular order. Below is a list of these symbols: -%% -%% asterisk -%% single-dagger -%% double-dagger -%% section sign -%% paragraph -%% parallel -%% double asterisk -%% double single-dagger -%% double double-dagger -%% -%% For illustrative purposes, all footnote symbols have been used in the -%% example file. -%% -%% A note regarding \footnote. This command seems to leave extra white -%% space between footnotes. This is quite evident in the example file. If -%% any user of these macros has a solution to this problem, I would -%% appreciate hearing from you. Send your comments to: gray@siam.org. -%% -%% The following general rules apply for including grants and affiliations: -%% 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, included the grant information -%% with each authors 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. -%% -%% -%% 11. Special fonts. -%% SIAM supports the use of AMS-TeX fonts version 2.0 and later. As -%% described in the manual for these fonts, they can be included by -%% \input{amssym.def} and \input{amssym.tex}. -%% -%% 12. How to Submit Your Paper. -%% The electronic version of your paper should be sent to proceed@siam.org. -%% A hardcopy version should also be submitted. Instructions are included -%% in your acceptance letter. Please be sure to send hardcopy -%% versions of any Postscript figures you have submitted electronically. -%% Be sure to return your signed Copyright Transfer Agreement. We cannot -%% publish your paper without one.%% -%% -%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -\input ptexproc.sty - -\def\leftrh{Gray et al.} -\def\rightrh{SIAM Proceedings Series Macros} - -\startchapter %Place this command at the beginning of the file immediately - %after the \input command. - - - -\title Chapter 1\endtitle -\title SIAM Proceedings Series Macros\endtitle -\lasttitle for Use with Plain TeX\footnote*{Any information -regarding grants should be placed here.}\endlasttitle - -\author J. Corey Gray\footnote{$^{\dag}$}{Production Manager, Society for -Industrial and Applied Mathematics, Philadelphia, PA.} -\hskip2truepc Tricia Manning\footnote{$^{\ddag}$}{Publications -Specialist, Society for Industrial and Applied Mathematics, Philadelphia, -PA.} -\hskip2truepc Vickie Kearn\footnote{$^{\S}$}{Publisher, Society for Industrial -and Applied Mathematics, Philadelphia, PA.} -\hskip2truepc Nancy Abbott\footnote{$^{\P}$}{Design Supervisor, Society for -Industrial and Applied Mathematics, Philadelphia, PA.} -\endauthor -\lastauthor Sue Ciambrano\footnote{$^{\parallel}$}{Acquisition Editor, Society for -Industrial and Applied Mathematics, Philadelphia, PA.} -\hskip2truepc Paul Duggan\footnote{$^{**}$}{Composition -Specialist, Society for Industrial and Applied Mathematics, Philadelphia, -PA.} -\hskip2truepc Robbi Anne Albert\footnote{$^{\dagger\dagger}$}{Production, -Assistant, Society for Industrial -and Applied Mathematics, Philadelphia, PA.} -\hskip2truepc Jean Anderson\footnote{$^{\ddag\ddag}$}{Composition Coordinator, Society for -Industrial and Applied Mathematics, Philadelphia, PA.} -\endlastauthor - -% Use \headone for the first level headings. The macro will automatically -% number the headings. - -\centerline{\bf Abstract} -\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.\endabstract - - -\headone{Problem Specification} -In this paper, we consider the solution of the $N \times N$ linear -system -$$A x = b\leqno (1)$$ -where $A$ is large, sparse, symmetric, and positive definite. We consider -the direct solution of 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} -\leqno (2)$$ - -\noindent where $L$ is unit lower triangular and $D$ is diagonal. - - -\headone{Design Considerations} -Several good ordering algorithms (nested dissection and minimum degree) -are available for computing $P$ [1], [2]. -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$. - -% Use \thm and \endthm for theorems. They must be numbered manually. -% Lemmas (\lem \endlem), corollaries (\cor \endcor), and -% propositions (\prop \endprop) are coded the same as theorems and must -% also be numbered manually. - -\thm{Theorem 2.1.} 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.\endthm - -Several good ordering algorithms (nested dissection and minimum degree) -are available for computing $P$ [1], [2]. -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$. -Several good ordering algorithms (nested dissection and minimum degree) -are available for computing $P$ [1], [2]. -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$. - -% Use \prf and \endprf to begin and end a proof. -% The use of \qed will produce an end-of-proof box. - -\prf{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 each.\qed\endprf - -% Use \dfn and \enddfn to begin and end definitions. - -\dfn{Definition 2.1.}We describe the two methods in \S\ 1.2. This is a -definition in the plain tex macro.\enddfn - -This is accomplished by exploiting the m-tree, -a particular spanning tree for the graph of the filled-in matrix. -Our purpose here is to examine the nonnumerical complexity of the -sparse elimination algorithm given in [3]. -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. - - -Our purpose here is to examine the nonnumerical complexity of the -sparse elimination algorithm given in [3]. -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. -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$. - -% Use \lem and \endlem to begin and end lemmas. - -\lem{Lemma 2.1.}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$. -\endlem - -% Use \fig to insert space for figures . - -\fig{10pc}{Fig. 1}{This is the caption for figure one.} - -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 -[4] - [10], [5], [6]. In \S 1.3., we analyze the complexity of the old and new -approaches to the intersection problem for the special case of -an $n \times n$ grid ordered by nested dissection. The special -structure of this problem allows us to make exact estimates of -the complexity. 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 -[4] - [10], [5], [6]. - -% Use \headtwo for second level headings. They will be numbered automatically. - -\headtwo{Robustness}In \S 1.2, we review the bordering algorithm, and introduce -the sorting and intersection problems that arise in the -sparse formulation of the algorithm. - -\headtwo{Versatility} In \S 1.3., we analyze the complexity of the old and new -approaches to the intersection problem for the special case of -an $n \times n$ grid ordered by nested dissection. The special -structure of this problem allows us to make exact estimates of -the complexity. 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 -[4] - [10], [5], [6]. - - -% Use \headthree for third level headings. - -\headthree{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. For the -new approach, the complexity of the second part is reduced to -$O(n^{2} (\log n)^{2})$. - -% The command \Refs sets the word Reference as a heading and allows the proper -% amount of space before the start of the references. Each reference must -% begin with \ref\\. The article or title of the reference should be in -% italic. Use the \it command within brackets. End each reference with -% \endref and allow two returns between references. Use the command -% \sameauthor (see reference 8) when the same author or group of authors -% is listed consecutively. - -\Refs - -\ref 1\\R.~E. Bank, {\it PLTMG users' guide, edition 5.0}, tech. report, - Department of Mathematics, University of California, San Diego, CA, 1988.\endref - -\ref 2\\R.~E. Bank, T.~F. Dupont, and H.~Yserentant, {\it The hierarchical basis - multigrid method}, Numer. Math., 52 (1988), pp.~427--458.\endref - -\ref 3\\R.~E. Bank and R.~K. Smith, {\it General sparse elimination requires no - permanent integer storage}, SIAM J. Sci. Stat. Comput., 8 (1987), - pp.~574--584.\endref - -\ref 4\\S.~C. Eisenstat, M.~C. Gursky, M.~Schultz, and A.~Sherman, {\it - Algorithms and data structures for sparse symmetric gaussian elimination}, - SIAM J. Sci. Stat. Comput., 2 (1982), pp.~225--237.\endref - -\ref 5\\A.~George and J.~Liu, {\it Computer Solution of Large Sparse Positive - Definite Systems}, Prentice Hall, Englewood Cliffs, NJ, 1981.\endref - -\ref 6\\K.~H. Law and S.~J. Fenves, {\it A node addition model for symbolic - factorization}, ACM TOMS, 12 (1986), pp.~37--50.\endref - -\ref 7\\J.~W.~H. Liu, {\it A compact row storage scheme for cholesky factors - using elimination trees}, ACM TOMS, 12 (1986), pp.~127--148.\endref - -\ref 8\\\sameauthor , {\it The role of - elimination trees in sparse factorization}, Tech. Report CS-87-12,Department - of Computer Science, York University, Ontario, Canada, 1987.\endref - -\ref 9\\D.~J. Rose, {\it A graph theoretic study of the numeric solution of - sparse positive definite systems}, in Graph Theory and Computing, - Academic Press, New York, 1972.\endref - -\ref 10\\D.~J. Rose, R.~E. Tarjan, and G.~S. Lueker, {\it Algorithmic aspects of - vertex elimination on graphs}, SIAM J. Comput., 5 (1976), pp.~226--283.\endref - - -\bye - -%end of example file -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%CUT HERE%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -% This is ptexproc.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 Plain TeX. - -% Report the version. -\message{*** SIAM Plain TeX Proceedings Series macro package, version 1.0, -November 6, 1992.***} - -% Make the @ sign a letter for internal control sequences. -\catcode`\@=11 -% -% -% - -\overfullrule=0pt -\baselineskip=14truept - - -%%% DIMENSIONS %%% - -\hsize=36truepc -\vsize=55truepc -%\hoffset=.5in -\parindent=18truept -\def\firstpar{\parindent=0pt\global\everypar{\parindent=18truept}} -\parskip=0pt - - -%%% FONTS %%% - -\font\tenrm=cmr10 -\font\tenbf=cmbx10 -\font\tenit=cmti10 -\font\tensmc=cmcsc10 -\def\tenpoint{% - \def\rm{\tenrm}\def\bf{\tenbf}% - \def\it{\tenit}\def\smc{\tensmc} - \textfont0=\tenrm \scriptfont0=\sevenrm - \textfont1=\teni \scriptfont1=\seveni - \textfont2=\tensy \scriptfont2=\sevensy - \textfont3=\tenex \scriptfont3=\tenex -\baselineskip=12pt\rm}% - -\font\ninerm=cmr9 -\font\ninebf=cmbx9 -\font\nineit=cmti9 -\def\ninepoint{% - \def\rm{\ninerm}\def\bf{\ninebf}% - \def\it{\nineit}\baselineskip=11pt\rm}% - -\font\eightrm=cmr8 -\font\eightbf=cmbx8 -\font\eightit=cmti8 -\font\eighti=cmmi8 -\font\eightsy=cmsy8 -\def\eightpoint{% - \def\rm{\eightrm}\def\bf{\eightbf}% - \def\it{\eightit}\def\smc{\eightrm}\baselineskip=10pt\rm% - \textfont0=\eightrm \scriptfont0=\sixrm - \textfont1=\eighti \scriptfont1=\sixi - \textfont2=\eightsy \scriptfont2=\sixsy - \textfont3=\tenex \scriptfont3=\tenex -} - -\font\sixrm=cmr6 -\font\sixbf=cmbx6 -\font\sixi=cmmi6 -\font\sixsmc=cmr5 -\font\sixsy=cmsy6 -\def\sixpoint{% - \def\rm{\sixrm}\def\bf{\sixbf}% - \def\smc{\sixsmc}\baselineskip=8pt\rm}% - -\fontdimen13\tensy=2.6pt -\fontdimen14\tensy=2.6pt -\fontdimen15\tensy=2.6pt -\fontdimen16\tensy=1.2pt -\fontdimen17\tensy=1.2pt -\fontdimen18\tensy=1.2pt - -\font\eightrm=cmr8 -\font\ninerm=cmr9 -\font\elevenrm=cmr10 scaled\magstephalf -\font\fourteenrm=cmr10 scaled\magstep 1 -\font\eighteenrm=cmr10 scaled\magstep 3 -\font\twelvebf=cmbx10 scaled\magstep 1 -\font\elevenbf=cmbx10 scaled\magstephalf -\font\elevenit=cmti10 scaled\magstephalf -\font\elevensc=cmcsc10 scaled\magstephalf - -\def\theoremfont{\elevensc} -\def\textfont{\elevenrm} -\def\itfont{\elevenit} -\def\headfont{\twelvebf} -\def\smallheadfont{\elevenbf} -\def\titlefont{\eighteenrm} -\def\chapterfont{\fourteenrm} -\def\authorfont{\fourteenrm} -\def\rheadfont{\tenrm} -\def\abstractfont{\tenrm} -\def\smc{\tensmc} -\font\eightsmc=cmcsc8 - -\def\footnote#1{\baselineskip=11truept\edef\@sf{\spacefactor\the\spacefactor}#1\@sf - \insert\footins\bgroup\ninepoint\hsize=36pc - \interlinepenalty10000 \let\par=\endgraf - \leftskip=0pt \rightskip=0pt - \splittopskip=10pt plus 1pt minus 1pt \floatingpenalty=20000 -\smallskip -\item{#1}\bgroup\baselineskip=10pt\strut -\aftergroup\@foot\let\next} -\skip\footins=12pt plus 2pt minus 4pt -\dimen\footins=36pc - - - -%%% CHAPTER OPENING MACROS %%% - -\def\startchapter{\topinsert\vglue54pt\endinsert} - -\def\title#1\endtitle{\titlefont\centerline{#1}\vglue5pt}%\vskip40truept\tenrm} -\def\lasttitle#1\endlasttitle{\titlefont\centerline{#1}\vskip1.32truepc} -\def\author#1\endauthor{\authorfont\centerline{#1}\vglue8pt\textfont} -\def\lastauthor#1\endlastauthor{\authorfont\centerline{#1}\vglue2.56pc\textfont} -\def\abstract#1\endabstract{\baselineskip=12pt\leftskip=2.25pc - \rightskip=2.25pc\abstractfont{#1}\textfont} - -%%% COUNTERS FOR HEADINGS %%% - -\newcount\headcount -\headcount=1 -\newcount\seccount -\seccount=1 -\newcount\subseccount -\subseccount=1 -\def\secreset{\global\seccount=1} - \def\subsecreset{\global\subseccount=1} - -%%% HEADINGS %%% - -\def\headone#1{\baselineskip=14pt\leftskip=0pt\rightskip=0pt\vskip17truept\parindent=0pt -{\headfont\the\headcount\hskip14truept #1} -\par\nobreak\firstpar\global\advance\headcount by 0 - \global\advance\headcount by 1\secreset\vskip2truept\textfont} - -\def\headtwo#1{\advance\headcount by -1% - \vskip17truept\parindent=0pt{\headfont\the\headcount.% - \the\seccount\hskip14truept #1}%\enspace\ignorespaces\firstpar - \global\advance\headcount by 1\global\advance\seccount by 1 - \global\advance\subseccount by 1\subsecreset\vskip2pt\textfont} - - \def\headthree#1{\advance\headcount by -1\advance\seccount by -1 -% \advance\subseccount by -1% - \vskip17truept\parindent=0pt{\smallheadfont\the\headcount.% - \the\seccount.\the\subseccount\hskip11truept #1}\hskip6pt\ignorespaces - \firstpar\global\advance\headcount by 1\global\advance\seccount by 1 - \global\advance\subseccount by 1\textfont} - -%%% THEOREMS, PROOFS, DEFINITIONS, etc. %%% - -\def\thm#1{{\theoremfont -#1\enspace} -\hskip-5pt\begingroup\itfont\ignorespaces} - -\let\lem=\thm -\let\cor=\thm -\let\prop=\thm - -\def\endthm{\endgroup\textfont} -\let\endlem=\endthm -\let\endcor=\endthm -\let\endprop=\endthm - -\def\prf#1{{\itfont #1.}\textfont\enspace\ignorespaces} -\let\rem=\prf -\let\case=\prf - -\def\endprf{\textfont} -\let\endrem=\endprf -\let\endcase=\endprf - -\def\qed{{\qquad \vbox{\hrule\hbox{% - \vrule height1.3ex\hskip0.8ex\vrule}\hrule - }}\par} - -\def\dfn#1{{\theoremfont -#1\enspace} -\textfont\ignorespaces} - -\let\fact=\dfn - -\def\enddfn{\textfont} - -\let\endfact=\enddfn - -%%% FIGURES AND CAPTIONS %%% - - -\newcount\figcount -\figcount=1 - - -%\newcount\tablenumber -%\tablenumber=1 - -\def\\{\hfill\break} - -\newbox\TestBox -\newdimen\setwd -\newskip\belowcaptionskip -\belowcaptionskip=6pt plus 1pt - -\def\endinsert{\egroup % finish the \vbox - \if@mid \dimen@\ht\z@ \advance\dimen@\dp\z@ - \advance\dimen@12\p@ \advance\dimen@\pagetotal - \ifdim\dimen@>\pagegoal\@midfalse\p@gefalse\fi\fi - \if@mid\vskip\belowcaptionskip\box\z@\par \penalty-200\vskip\belowcaptionskip - \else\insert\topins{\penalty100 % floating insertion - \splittopskip\z@skip - \splitmaxdepth\maxdimen \floatingpenalty\z@ - \ifp@ge \dimen@\dp\z@ - \vbox to\vsize{\unvbox\z@\kern-\dimen@}% depth is zero - \else \box\z@\nobreak\vskip\belowcaptionskip\fi}\fi\endgroup} - - - - -\def\fig#1#2#3{% - \setbox\TestBox=\hbox{\tenpoint #3.}\setwd=\wd\TestBox - \topinsert - \vskip #1 - \vskip 12pt - \ifdim\setwd > 23pc - {\tenit{\smc #2.}\ \ #3} - \else - \centerline{\tenit\noindent - {\smc #2.}\ \ #3}\fi% - % \global\advance\figcount by 1 - \endinsert} - - - -%%% REFERENCES %%% - -\newdimen\refindent@ -\newdimen\refhangindent@ -\newbox\refbox@ -\setbox\refbox@=\hbox{\tenrm\baselineskip=11pt [00]}% Default 2 digits -\refindent@=\wd\refbox@ - -\def\resetrefindent#1{% - \setbox\refbox@=\hbox{\tenrm\baselineskip=11pt [#1]}% - \refindent@=\wd\refbox@} - -\def\Refs{% - \unskip\vskip1pc - \leftline{\noindent\headfont References}% - \penalty10000 - \vskip4pt - \penalty10000 - \refhangindent@=\refindent@ - \global\advance\refhangindent@ by .5em - \global\everypar{\hangindent\refhangindent@}% - \parindent=0pt\baselineskip=12pt\tenrm} - -\def\sameauthor{\leavevmode\vbox to 1ex{\vskip 0pt plus 100pt - \hbox to 2em{\leaders\hrule\hfil}\vskip 0pt plus 300pt}} - -\def\ref#1\\#2\endref{\leavevmode\hbox to \refindent@{\hfil[#1]}\enspace #2\par} - - -%%% OUTPUT %%% - -\def\rightheadline{\hfill\tensmc\rightrh\hskip2pc\tenrm\folio} -\def\leftheadline{\tenrm\folio\hskip2pc\tensmc\leftrh\hfill} - -\global\footline={\hss\tenrm\folio\hss}% first page - -\output{\plainoutput} -\def\plainoutput{\shipout\vbox{\makeheadline\pagebody\makefootline}% - \advancepageno - \ifnum\pageno>1 - \global\footline={\hfill}% - \fi - \ifodd\pageno - \global\headline={\rightheadline}% - \else - \global\headline={\leftheadline}% - \fi - \ifnum\outputpenalty>-\@MM \else\dosupereject\fi} -\def\pagebody{\vbox to\vsize{\boxmaxdepth\maxdepth \pagecontents}} -\def\makeheadline{\vbox to\z@{\vskip-22.5\p@ - \line{\vbox to8.5\p@{}\rheadfont\the\headline}\vss}% - \nointerlineskip} -\def\makefootline{\baselineskip24\p@\vskip-6\p@\line{\the\footline}} -\def\dosupereject{\ifnum\insertpenalties>\z@ % something is being held over - \line{}\kern-\topskip\nobreak\vfill\supereject\fi} - -\def\footnoterule{\vskip11pt\kern -4\p@\hrule width 3pc \kern 3.6\p@ } % rule = .4 pt high - -% Turn off @ as being a letter. -% -\catcode`\@=13 - -%end of style file diff --git a/Master/texmf-dist/source/latex/siam/soda209.all b/Master/texmf-dist/source/latex/siam/soda209.all deleted file mode 100644 index 862535ccfd3..00000000000 --- a/Master/texmf-dist/source/latex/siam/soda209.all +++ /dev/null @@ -1,682 +0,0 @@ -%% This is soda209.all. This file is to be used for creating a paper -%% in the ACM/SIAM Preprint series with LaTeX. It consists of the following -%% two files: -%% -%% ltexprt.tex ---- an example and documentation file -%% ltexprt.sty ---- the macro file -%% -%% To use, cut this file apart at the appropriate places. You can run the -%% example file with the macros to get sample output. -%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%% CUT HERE %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -% -% -%%%%%%%%%%%%%%%%%%%%%%%%%% ltexprt.tex %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -% -% This is ltexprt.tex, an example file for use with the SIAM LaTeX (version 2.09) -% Preprint Series macros. It is designed to provide double-column output. -% Please take the time to read the following comments, as they document -% 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 Preprint 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. If you are using BibTeX, please -%% supply the bst file with the manuscript file. -%% -%% -%% 3. This macro is set up for two levels of headings (\section and -%% \subsection). The macro will automatically number the headings for you. -%% -%% 4. No running heads are to be used in this volume. -%% -%% 5. Theorems, Lemmas, Definitions, etc. are to be double numbered, -%% indicating the section and the occurence 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. -%% -%% 6. Figures, equations, and tables must be single-numbered. -%% Use existing LaTeX tags for these elements. -%% Numbering will be done automatically. -%% -%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - - -\documentstyle[twoside,leqno,twocolumn,ltexprt]{article} - -\begin{document} - - -\title{\Large SIAM/ACM Preprint Series Macros for -Use With LaTeX\thanks{Supported by GSF grants ABC123, DEF456, and GHI789.}} -\author{Corey Gray\thanks{Society for Industrial and Applied Mathematics.} \\ -\and -Tricia Manning\thanks{Society for Industrial and Applied Mathematics.}} -\date{} - -\maketitle - -\pagestyle{myheadings} -\markboth{}{} - -%\pagenumbering{arabic} - - -\begin{abstract} \small\baselineskip=9pt This is the text of my abstract. It is a brief -description of my -paper, outlining the purposes and goals I am trying to address.\end{abstract} - -\section{Problem Specification.}In this paper, we consider the solution of the $N \times -N$ linear -system -\begin{equation} \label{e1.1} -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} - -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. -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. -\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} - -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. -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. - -\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} - -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 -[4] - [10], [5], [6]. In \S 1.3., we analyze the complexity of the old and new -approaches to the intersection problem for the special case of -an $n \times n$ grid ordered by nested dissection. The special -structure of this problem allows us to make exact estimates of -the complexity. 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 -[4] - [10], [5], [6]. - -In \S 1.2, we review the bordering algorithm, and introduce -the sorting and intersection problems that arise in the -sparse formulation of the algorithm. -In \S 1.3., we analyze the complexity of the old and new -approaches to the intersection problem for the special case of -an $n \times n$ grid ordered by nested dissection. The special -structure of this problem allows us to make exact estimates of -the complexity. 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 -[4] - [10], [5], [6]. - - -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. For the -new approach, the complexity of the second part is reduced to -$O(n^{2} (\log n)^{2})$. - -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 -[4] - [10], [5], [6]. In \S 1.3., we analyze the complexity of the old and new -approaches to the intersection problem for the special case of -an $n \times n$ grid ordered by nested dissection. The special -structure of this problem allows us to make exact estimates of -the complexity. 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 -[4] - [10], [5], [6]. -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} - -\begin{figure} -\vspace{14pc} -\caption{This is a figure 1.1.} -\end{figure} - -\section{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. - -\subsection{Versatility.}\ 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})$. - -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 -[4] - [10], [5], [6]. In \S 1.3., we analyze the complexity of the old and new -approaches to the intersection problem for the special case of -an $n \times n$ grid ordered by nested dissection. The special -structure of this problem allows us to make exact estimates of -the complexity. 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 -[4] - [10], [5], [6]. - -In \S 1.2, we review the bordering algorithm, and introduce -the sorting and intersection problems that arise in the -sparse formulation of the algorithm. -In \S 1.3., we analyze the complexity of the old and new -approaches to the intersection problem for the special case of -an $n \times n$ grid ordered by nested dissection. The special -structure of this problem allows us to make exact estimates of -the complexity. 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 -[4] - [10], [5], [6]. - - -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. For the -new approach, the complexity of the second part is reduced to -$O(n^{2} (\log n)^{2})$. - -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 -[4] - [10], [5], [6]. In \S 1.3., we analyze the complexity of the old and new -approaches to the intersection problem for the special case of -an $n \times n$ grid ordered by nested dissection. The special -structure of this problem allows us to make exact estimates of -the complexity. 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 -[4] - [10], [5], [6]. -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}. - -\begin{thebibliography}{99} - -%\bibitem{GUIDE} -%R.~E. Bank, {\em PLTMG users' guide, edition 5.0}, tech. report, -% Department of Mathematics, University of California, San Diego, CA, 1988. - -%\bibitem{HBMG} -%R.~E. Bank, T.~F. Dupont, and H.~Yserentant, {\em The hierarchical basis -% multigrid method}, Numer. Math., 52 (1988), pp.~427--458. - -\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.~Schrieber, {\em A new implementation of sparse gaussian elimination}, - ACM TOMS, 8 (1982), pp.~256--276. - -\end{thebibliography} -\end{document} - -% End of ltexprt.tex -% -% -% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% CUT HERE %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -% -% -% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% ltexprt.sty %%%%%%%%%%%%%%%%%%%%%%%%%%%%% -% -% This is ltexprt.sty, a file of macros and definitions for creating a -% chapter for publication in the ACM/SIAM Preprint series using LaTeX (version 2.09). -% It is designed to produce double-column output. -% 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 - - -% Report the version. -\message{*** ACM/SIAM LaTeX 2.09 Preprint Series macro package, version 1.0, -September 24,1990 ***} - - -\pretolerance=800 -\tolerance=10000 -\sloppy - -\voffset=-.5in -\hoffset=-.5in -\vsize=55pc -\hsize=41pc -\baselineskip=14pt -\footskip=18pt -\topmargin 24pt -\headheight 12pt -\headsep 17pt -\textheight 52.5pc \advance\textheight by \topskip -\textwidth 41pc -\parskip 0pt -\parindent 18pt - -\font\tensmc=cmcsc10 -\def\smc{\tensmc} - -%% footnotes to be set 8/10 -\def\footnotesize{\@setsize\footnotesize{10pt}\viiipt\@viiipt - % \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} % 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}\hfil{\small\leftmark}}% - \def\@oddhead{{\noindent\small\rightmark}\hfil{\rm\thepage}}% - - - -\def\ps@myheadings{\let\@mkboth\@gobbletwo - \def\@oddfoot{}\def\@evenfoot{}% - \def\@oddhead{\rlap{\normalsize\rm\rightmark}\hfil{small\thepage}}% - \def\@evenhead%{\hfil{\small\@chapapp}\ - {\small\thepage}\hfil\llap{\normalsize\rm\leftmark}}% - \def\chaptermark##1{}% - \def\sectionmark##1{}\def\subsectionmark##1{}} - - -\def\theequation{\arabic{section}.\arabic{equation}} - - -\def\section{\@startsection{section}{1}{0pt}{-12pt}{3pt}{\hyphenpenalty=\@M -\exhyphenpenalty=\@M\normalsize\bf}} -\def\subsection{\@startsection{subsection}{2}{0pt}{-12pt}{0pt}{\normalsize\bf} -} -\def\subsubsection{\@startsection - {subsubsection}{3}{0pt}{-12pt}{0pt}{\normalsize\bf}} -\def\paragraph{\@startsection - {paragraph}{4}{\parindent}{0pt}{0pt}{\normalsize\bf}} -\def\subparagraph{\@startsection - {subparagraph}{4}{\parindent}{0pt}{0pt}{\normalsize\bf}} - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -% % -% THEOREMS, PROOFS, ALGORITHMS % -% % -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%% defined proof environment by theorem model (took out counter) - -\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 \trivlist \item[\hskip \labelsep{\it #1.\/}]} -\def\@endproof{\outerparskip 0pt\endtrivlist} - -\def\@begintheorem#1#2{\it \trivlist \item[\hskip \labelsep{\sc #1\ #2.}]} -\def\@opargbegintheorem#1#2#3{\it \trivlist - \item[\hskip \labelsep{\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{Corollary}[Theorem]{Corollary} -\newtheorem{Definition}{Definition}[section] -\newtheorem{Lemma}{Lemma}[section] -\newtheorem{Remark}{Remark}[section] - -\newproof{Example}{Example} -\newproof{Method}{Method} -\newproof{Exercise}{Exercise} - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% %% -%% BIBLIOGRAPHY %% -%% %% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - -\def\thebibliography#1{% -%\cleardoublepage -\parindent 0em -\vspace{6pt} -\begin{flushleft}\normalsize\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 - \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} - -% -%% End of ltexprt.sty -% -%%%%%%%%%%%%%%%%%%%%%%%%% End of soda209.all %%%%%%%%%%%%%%%%%%%%%%% diff --git a/Master/texmf-dist/source/latex/siam/soda2e.all b/Master/texmf-dist/source/latex/siam/soda2e.all deleted file mode 100644 index 17f570966fa..00000000000 --- a/Master/texmf-dist/source/latex/siam/soda2e.all +++ /dev/null @@ -1,688 +0,0 @@ -%% This is soda2e.all. This file is to be used for creating a paper -%% in the ACM/SIAM Preprint series with LaTeX2E. It consists of the following -%% two files: -%% -%% ltexpprt.tex ---- an example and documentation file -%% ltexpprt.sty ---- the macro file -%% -%% To use, cut this file apart at the appropriate places. You can run the -%% example file with the macros to get sample output. -%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%% CUT HERE %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -% -% -%%%%%%%%%%%%%%%%%%%%%%%%%% ltexpprt.tex %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -% -% This is ltexpprt.tex, an example file for use with the SIAM LaTeX2E -% Preprint Series macros. It is designed to provide double-column output. -% Please take the time to read the following comments, as they document -% 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 Preprint 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. If you are using BibTeX, please -%% supply the bst file with the manuscript file. -%% -%% 3. This macro is set up for two levels of headings (\section and -%% \subsection). The macro will automatically number the headings for you. -%% -%% 5. No running heads are to be used for this volume. -%% -%% 6. Theorems, Lemmas, Definitions, etc. are to be double numbered, -%% indicating the section and the occurence 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. -%% -%% 7. Figures, equations, and tables must be single-numbered. -%% Use existing LaTeX tags for these elements. -%% Numbering will be done automatically. -%% -%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - - -\documentclass[twoside,leqno,twocolumn]{article} -\usepackage{ltexpprt} -\begin{document} - - -%\setcounter{chapter}{2} % If you are doing your chapter as chapter one, -%\setcounter{section}{3} % comment these two lines out. - -\title{\Large SIAM/ACM Preprint Series Macros for -Use With LaTeX\thanks{Supported by GSF grants ABC123, DEF456, and GHI789.}} -\author{Corey Gray\thanks{Society for Industrial and Applied Mathematics.} \\ -\and -Tricia Manning\thanks{Society for Industrial and Applied Mathematics.}} -\date{} - -\maketitle - -\pagestyle{myheadings} -\markboth{}{} - - -%\pagenumbering{arabic} -%\setcounter{page}{1}%Leave this line commented out. - -\begin{abstract} \small\baselineskip=9pt This is the text of my abstract. It is a brief -description of my -paper, outlining the purposes and goals I am trying to address.\end{abstract} - - - - -\section{Problem Specification.}In this paper, we consider the solution of the $N \times -N$ linear -system -\begin{equation} \label{e1.1} -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} - -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. -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. -\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} - -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. -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. - -\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} - -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 -[4] - [10], [5], [6]. In \S 1.3., we analyze the complexity of the old and new -approaches to the intersection problem for the special case of -an $n \times n$ grid ordered by nested dissection. The special -structure of this problem allows us to make exact estimates of -the complexity. 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 -[4] - [10], [5], [6]. - -In \S 1.2, we review the bordering algorithm, and introduce -the sorting and intersection problems that arise in the -sparse formulation of the algorithm. -In \S 1.3., we analyze the complexity of the old and new -approaches to the intersection problem for the special case of -an $n \times n$ grid ordered by nested dissection. The special -structure of this problem allows us to make exact estimates of -the complexity. 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 -[4] - [10], [5], [6]. - - -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. For the -new approach, the complexity of the second part is reduced to -$O(n^{2} (\log n)^{2})$. - -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 -[4] - [10], [5], [6]. In \S 1.3., we analyze the complexity of the old and new -approaches to the intersection problem for the special case of -an $n \times n$ grid ordered by nested dissection. The special -structure of this problem allows us to make exact estimates of -the complexity. 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 -[4] - [10], [5], [6]. -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} - -\begin{figure} -\vspace{14pc} -\caption{This is a figure 1.1.} -\end{figure} - -\section{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. - -\subsection{Versatility.}\ 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})$. - -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 -[4] - [10], [5], [6]. In \S 1.3., we analyze the complexity of the old and new -approaches to the intersection problem for the special case of -an $n \times n$ grid ordered by nested dissection. The special -structure of this problem allows us to make exact estimates of -the complexity. 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 -[4] - [10], [5], [6]. - -In \S 1.2, we review the bordering algorithm, and introduce -the sorting and intersection problems that arise in the -sparse formulation of the algorithm. -In \S 1.3., we analyze the complexity of the old and new -approaches to the intersection problem for the special case of -an $n \times n$ grid ordered by nested dissection. The special -structure of this problem allows us to make exact estimates of -the complexity. 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 -[4] - [10], [5], [6]. - - -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. For the -new approach, the complexity of the second part is reduced to -$O(n^{2} (\log n)^{2})$. - -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 -[4] - [10], [5], [6]. In \S 1.3., we analyze the complexity of the old and new -approaches to the intersection problem for the special case of -an $n \times n$ grid ordered by nested dissection. The special -structure of this problem allows us to make exact estimates of -the complexity. 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 -[4] - [10], [5], [6]. -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}. - -\begin{thebibliography}{99} - -%\bibitem{GUIDE} -%R.~E. Bank, {\em PLTMG users' guide, edition 5.0}, tech. report, -% Department of Mathematics, University of California, San Diego, CA, 1988. - -%\bibitem{HBMG} -%R.~E. Bank, T.~F. Dupont, and H.~Yserentant, {\em The hierarchical basis -% multigrid method}, Numer. Math., 52 (1988), pp.~427--458. - -\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.~Schrieber, {\em A new implementation of sparse gaussian elimination}, - ACM TOMS, 8 (1982), pp.~256--276. - -\end{thebibliography} -\end{document} - -% End of ltexpprt.tex -% - - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% ltexpprt.sty %%%%%%%%%%%%%%%%%%%%%%%%%%%%% -% -% This is ltexpprt.sty, a file of macros and definitions for creating a -% chapter for publication in the ACM/SIAM Preprint series using LaTeX2E. -% It is designed to produce double-column output. -% 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 - - -% Report the version. -\message{*** ACM/SIAM LaTeX2E Preprint Series macro package, version 1.0, -September 5, 1996 ***} - - -\pretolerance=800 -\tolerance=10000 -\sloppy - -%\voffset=-.5in -%\hoffset=-.5in -\vsize=55pc -\hsize=41pc -\baselineskip=14pt -\footskip=18pt -\topmargin 24pt -\headheight 12pt -\headsep 17pt -\textheight 52.5pc \advance\textheight by \topskip -\textwidth 41pc -\parskip 0pt -\parindent 18pt - -\font\tensmc=cmcsc10 -\def\smc{\tensmc} - -%% footnotes to be set 8/10 -\def\footnotesize{\@setsize\footnotesize{10pt}\viiipt\@viiipt - % \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} % 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}\hfil{\small\leftmark}}% - \def\@oddhead{{\noindent\small\rightmark}\hfil{\rm\thepage}}% - - - -\def\ps@myheadings{\let\@mkboth\@gobbletwo - \def\@oddfoot{}\def\@evenfoot{}% - \def\@oddhead{\rlap{\normalsize\rm\rightmark}\hfil{small\thepage}}% - \def\@evenhead%{\hfil{\small\@chapapp}\ - {\small\thepage}\hfil\llap{\normalsize\rm\leftmark}}% - \def\chaptermark##1{}% - \def\sectionmark##1{}\def\subsectionmark##1{}} - - -\def\theequation{\arabic{section}.\arabic{equation}} - - -\def\section{\@startsection{section}{1}{0pt}{-12pt}{3pt}{\hyphenpenalty=\@M -\exhyphenpenalty=\@M\normalsize\bf}} -\def\subsection{\@startsection{subsection}{2}{0pt}{-12pt}{0pt}{\normalsize\bf} -} -\def\subsubsection{\@startsection - {subsubsection}{3}{0pt}{-12pt}{0pt}{\normalsize\bf}} -\def\paragraph{\@startsection - {paragraph}{4}{\parindent}{0pt}{0pt}{\normalsize\bf}} -\def\subparagraph{\@startsection - {subparagraph}{4}{\parindent}{0pt}{0pt}{\normalsize\bf}} - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -% % -% THEOREMS, PROOFS, ALGORITHMS % -% % -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%% defined proof environment by theorem model (took out counter) - -\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 \trivlist \item[\hskip \labelsep{\it #1.\/}]} -\def\@endproof{\outerparskip 0pt\endtrivlist} - -\def\@begintheorem#1#2{\it \trivlist \item[\hskip \labelsep{\sc #1\ #2.}]} -\def\@opargbegintheorem#1#2#3{\it \trivlist - \item[\hskip \labelsep{\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{Corollary}[Theorem]{Corollary} -\newtheorem{Definition}{Definition}[section] -\newtheorem{Lemma}{Lemma}[section] -\newtheorem{Remark}{Remark}[section] - -\newproof{Example}{Example} -\newproof{Method}{Method} -\newproof{Exercise}{Exercise} - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% %% -%% BIBLIOGRAPHY %% -%% %% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - -\def\thebibliography#1{% -%\cleardoublepage -\parindent 0em -\vspace{6pt} -\begin{flushleft}\normalsize\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 - \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} - -% -% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% CUT HERE %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -% -% -% - diff --git a/Master/texmf-dist/source/latex/siam/sodaptex.all b/Master/texmf-dist/source/latex/siam/sodaptex.all deleted file mode 100644 index e4c99f08c2b..00000000000 --- a/Master/texmf-dist/source/latex/siam/sodaptex.all +++ /dev/null @@ -1,722 +0,0 @@ -%% This is sodaptex.all. This file is to be used for creating a paper -%% in the ACM/SIAM Preprint series with Plain TeX. It consists of the following -%% two files: -%% -%% ptexpprt.tex ---- an example and documentation file -%% ptexpprt.sty ---- the macro file -%% -%% To use, cut this file apart at the appropriate places. You can run the -%% example file with the macros to get sample output. -%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%% CUT HERE %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -% -% -%%%%%%%%%%%%%%%%%%%%%%%%%% ptexpprt.tex %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -% -% This is ptexpprt.tex, an example file for use with the ACM/SIAM Plain TeX -% Preprint Series macros. It is designed to produce double-column output. -% Comments are placed at the beginning and throughout this file. Please -% take the time to read them as they document 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. You must use the numbered reference style([1],[2]), listing the -%% references at the end of the chapter either by order of citation -%% or alphabetically. -%% -%% 2. Unless otherwise stated by your editor, do your chapter as if it -%% is Chapter 1. -%% If you know which number your chapter is, you must do the following: -%% -%% Go into the style file (ptexfrnt.sty) and search for the -%% \def\chapter#1 definition. At the end of this definition -%% there is a command \headcount=1. Change the 1 to -%% the appropriate number. This change will cause the headings -%% in your chapter to match the chapter number. -%% -%% 3. This macro is set up for two levels of headings. The macro will -%% automatically number the headings for you. -%% -%% 4. The running heads are defined in the output routine. It will be -%% necessary for you to alter the information currently included. -%% To do this, go into the style file and search for OUTPUT. Once there, -%% scroll through the file until you see the command \def\rhead. Replace -%% CHAPTER TITLE with the title (or shortened title) of your paper. -%% Replace AUTHORS NAMES with the appropriate names. -%% Neither running head may be longer than 50 characters. -%% -%% 5. Theorems, Lemmas, Definitions, etc. are to be triple numbered, -%% indicating the chapter, section, and the occurence of that element -%% within that section. (For example, the first theorem in the second -%% section of chapter three would be numbered 3.2.1. This numbering must -%% be done manually. -%% -%% 6. Figures and equations must be manually double-numbered, indicating -%% chapter and occurence. Use \leqno for equation numbering. See the -%% example of \caption for figure numbering. -%% Note. Although not shown, tables must also be double-numbered. The -%% command \caption can also be used for table captions. -%% -%% 7. At the first occurence of each new element there is a description -%% of how to use the coding. -%% -%%%%%%% PLEASE NOTE THE FOLLOWING POTENTIAL PROBLEMS: -% -%% 1. A bug exists that prevents a page number from printing on the first -%% page of the paper. Please ignore this problem. It will be handled -%% after you submit your paper. -%% -%% 2. The use of \topinsert and \midinsert to allow space for figures can -%% result in unusual page breaks, or unusual looking pages in general. -%% If you encounter such a situation, contact the SIAM office at the -%% address listed above for instructions. -%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -\input ptexpprt.sty -\voffset=.25in -\titlepage - -% It will be necessary to hard code the chapter title and chapter authors. -% You must decide where to break the lines. For the authors, please follow -% the following conventions: -% 1. If 2 authors are on a line, use \hskip4pc between them. If 3 authors, -% use \hskip2pc. Do not put more than 3 authors on the same line. -% 2. Use the following notation: asterisk, dagger, double-dagger, section -% symbol, paragraph symbol, double asterisk. If more are needed, contact -% the SIAM office. - -\centerline{\chapterfont Chapter 1} -\vskip2pt -\centerline{\titlefont SIAM/ACM Preprint Series Macros for -Plain TeX\footnote*{Supported by GSF grants ABC123, DEF456, and GHI 789.}} -\vskip15pt -\centerline{\authorfont J. Corey Gray\footnote\dag{Society for Industrial and -Applied Mathematics.}\hskip2pc Tricia Manning\footnote\ddag{Society for -Industrial and Applied Mathematics.}\hskip2pc Vickie Kearn\footnote\S{Society -for Industrial and Applied Mathematics.}} -\vskip2pc - -\begindoublecolumns - -% Use \headone for the first level headings. The macro will automatically -% number the headings. - -\headone{Problem Specification} -In this paper, we consider the solution of the $N \times N$ linear -system -$$A x = b\leqno(1.1)$$ -where $A$ is large, sparse, symmetric, and positive definite. We consider -the direct solution of 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. - -\headone{Design Considerations} -Several good ordering algorithms (nested dissection and minimum degree) -are available for computing $P$ [1], [2]. -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$. - -% Use \headtwo for second level headings. They will be numbered automatically. - -\headtwo{Robustness}In \S 1.2, we review the bordering algorithm, and introduce -the sorting and intersection problems that arise in the -sparse formulation of the algorithm. - -\headtwo{Versatility} In \S 1.3., we analyze the complexity of the old and new -approaches to the intersection problem for the special case of -an $n \times n$ grid ordered by nested dissection. The special -structure of this problem allows us to make exact estimates of -the complexity. 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 -[4] - [10], [5], [6]. -This is accomplished by exploiting the m-tree, -a particular spanning tree for the graph of the filled-in matrix. -Our purpose here is to examine the nonnumerical complexity of the -sparse elimination algorithm given in [3]. -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. - - -% Use \thm and \endthm for theorems. They must be numbered manually. -% Lemmas (\lem \endlem), corollaries (\cor \endcor), and -% propositions (\prop \endprop) are coded the same as theorems and must -% also be numbered manually. - -\thm{Theorem 2.1.} 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.\endthm - -Several good ordering algorithms (nested dissection and minimum degree) -are available for computing $P$ [1], [2]. -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$. -Several good ordering algorithms (nested dissection and minimum degree) -are available for computing $P$ [1], [2]. -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$. - -% Use \prf to begin a proof. - -\prf{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 each. - -% Use \dfn to begin definitions. - -\dfn{Definition 1.2.1.}We describe the two methods in \S\ 1.2. This is a -definition in the plain tex macro. - -This is accomplished by exploiting the m-tree, -a particular spanning tree for the graph of the filled-in matrix. -Our purpose here is to examine the nonnumerical complexity of the -sparse elimination algorithm given in [3]. -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. -Our purpose here is to examine the nonnumerical complexity of the -sparse elimination algorithm given in [3]. -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. -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$. - - -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 -[4] - [10], [5], [6]. In \S 1.3., we analyze the complexity of the old and new -approaches to the intersection problem for the special case of -an $n \times n$ grid ordered by nested dissection. The special -structure of this problem allows us to make exact estimates of -the complexity. 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 -[4] - [10], [5], [6]. -Several good ordering algorithms (nested dissection and minimum degree) -are available for computing $P$ [1], [2]. -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$. -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. For the -new approach, the complexity of the second part is reduced to -$O(n^{2} (\log n)^{2})$. - -% Use \midinsert along with \caption to allow space for -% figures. See note above in problem section. -%\midinsert\vskip15.5pc\caption{Fig. 1.1. {\nineit This is figure 1.}} -% \endcaption\endinsert - -In this paper, we consider the solution of the $N \times N$ linear -system -where $A$ is large, sparse, symmetric, and positive definite. We consider -the direct solution of by means of general sparse Gaussian -elimination. In such a procedure, we find a permutation matrix $P$, and -compute the decomposition -where $L$ is unit lower triangular and $D$ is diagonal. - -\headone{Design Considerations} -Several good ordering algorithms (nested dissection and minimum degree) -are available for computing $P$ [1], [2]. -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$. - -Several good ordering algorithms (nested dissection and minimum degree) -are available for computing $P$ [1], [2]. -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$. -Several good ordering algorithms (nested dissection and minimum degree) -are available for computing $P$ [1], [2]. -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 [3]. -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. -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$. - -% Use \lem and \endlem to begin and end lemmas. - -\lem{Lemma 2.1.}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$. -\endlem - -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 -[4] - [10], [5], [6]. In \S 1.3., we analyze the complexity of the old and new -approaches to the intersection problem for the special case of -an $n \times n$ grid ordered by nested dissection. The special -structure of this problem allows us to make exact estimates of -the complexity. 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 -[4] - [10], [5], [6]. - -% Use \headtwo for second level headings. They will be numbered automatically. - -\headone{Problem Solving}In \S 1.2, we review the bordering algorithm, and -introduce -the sorting and intersection problems that arise in the -sparse formulation of the algorithm. - -\headtwo{Versatility} In \S 1.3., we analyze the complexity of the old and new -approaches to the intersection problem for the special case of -an $n \times n$ grid ordered by nested dissection. The special -structure of this problem allows us to make exact estimates of -the complexity. 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 -[4] - [10], [5], [6]. - - -\headtwo{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. For the -new approach, the complexity of the second part is reduced to -$O(n^{2} (\log n)^{2})$. - -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 -[4] - [10], [5], [6]. In \S 1.3., we analyze the complexity of the old and new -approaches to the intersection problem for the special case of -an $n \times n$ grid ordered by nested dissection. The special -structure of this problem allows us to make exact estimates of -the complexity. 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 -[4] - [10], [5], [6]. - -% The command \Refs sets the word Reference as a heading and allows the proper -% amount of space before the start of the references. Each reference must -% begin with \ref\\. The article or title of the reference should be in -% italic. Use the \it command within brackets. End each reference with -% \endref and allow two returns between references. Use the command -% \sameauthor (see reference 8) when the same author or group of authors -% is listed consecutively. - -\Refs - -\ref 1\\R.~E. Bank, {\it PLTMG users' guide, edition 5.0}, tech. report, - Department of Mathematics, University of California, San Diego, CA, -1988.\endref - -\ref 2\\R.~E. Bank, T.~F. Dupont, and H.~Yserentant, {\it The hierarchical basis - multigrid method}, Numer. Math., 52 (1988), pp.~427--458.\endref - -\ref 3\\R.~E. Bank and R.~K. Smith, {\it General sparse elimination requires no - permanent integer storage}, SIAM J. Sci. Stat. Comput., 8 (1987), - pp.~574--584.\endref - -\ref 4\\S.~C. Eisenstat, M.~C. Gursky, M.~Schultz, and A.~Sherman, {\it - Algorithms and data structures for sparse symmetric gaussian elimination}, - SIAM J. Sci. Stat. Comput., 2 (1982), pp.~225--237.\endref - -\ref 5\\A.~George and J.~Liu, {\it Computer Solution of Large Positive - Definite Systems}, Prentice Hall, Englewood Cliffs, NJ, 1981.\endref - -\ref 6\\K.~H. Law and S.~J. Fenves, {\it A node addition model for symbolic - factorization}, ACM TOMS, 12 (1986), pp.~37--50.\endref - -\ref 7\\J.~W.~H. Liu, {\it A compact row storage scheme for factors - using elimination trees}, ACM TOMS, 12 (1986), pp.~127--148.\endref - -\ref 8\\\sameauthor , {\it The role of - elimination trees in sparse factorization}, Tech. Report CS-87-12,Department - of Computer Science, York University, Ontario, Canada, 1987.\endref - -\ref 9\\D.~J. Rose, {\it A graph theoretic study of the numeric solution of - sparse positive definite systems}, in Graph Theory and Computing, - Academic Press, New York, 1972.\endref - -\ref 10\\D.~J. Rose, R.~E. Tarjan, and G.~S. Lueker, {\it Algorithmic aspects of - vertex elimination on graphs}, SIAM J. Comput., 5 (1976), pp.~226--283.\endref -\enddoublecolumns - -\bye -%% -%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%% CUT HERE %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -% -% -%%%%%%%%%%%%%%%%%%%%%%%%%% ptexpprt.sty %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -% -% This is a file of macros and definitions for creating a chapter -% for publication in the ACM/SIAM Preprint Series using Plain TeX. -% 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 -% - -% Report the version. -\message{*** ACM/SIAM Plain TeX Preprint Series macro package, version 1.0, -September 24, 1990.***} - -% Make the @ sign a letter for internal control sequences. -\catcode`\@=11 -% -% -% - - - -%%% DIMENSIONS %%% - -\newdimen\pagewidth -\hsize=41pc -\pagewidth=\hsize -\newdimen\pageheight -\vsize=50pc -\pageheight=\vsize -\newdimen\ruleht -\ruleht=.5pt -\maxdepth=2.2pt - -\parindent=18truept -\def\firstpar{\parindent=0pt\global\everypar{\parindent=18truept}} -\parskip=0pt plus 1pt - - -%%% FONTS %%% - -\font\tenrm=cmr10 -\font\tenbf=cmbx10 -\font\tenit=cmti10 -\font\tensmc=cmcsc10 -\def\tenpoint{% - \def\rm{\tenrm}\def\bf{\tenbf}% - \def\it{\tenit}\def\smc{\tensmc} - \textfont0=\tenrm \scriptfont0=\sevenrm - \textfont1=\teni \scriptfont1=\seveni - \textfont2=\tensy \scriptfont2=\sevensy - \textfont3=\tenex \scriptfont3=\tenex -\baselineskip=12pt\rm}% - -\font\ninerm=cmr9 -\font\ninebf=cmbx9 -\font\nineit=cmti9 -\def\ninepoint{% - \def\rm{\ninerm}\def\bf{\ninebf}% - \def\it{\nineit}\baselineskip=11pt\rm}% - -\font\eightrm=cmr8 -\font\eightbf=cmbx8 -\font\eightit=cmti8 -\font\eighti=cmmi8 -\font\eightsy=cmsy8 -\def\eightpoint{% - \def\rm{\eightrm}\def\bf{\eightbf}% - \def\it{\eightit}\def\smc{\eightrm}\baselineskip=10pt\rm% - \textfont0=\eightrm \scriptfont0=\sixrm - \textfont1=\eighti \scriptfont1=\sixi - \textfont2=\eightsy \scriptfont2=\sixsy - \textfont3=\tenex \scriptfont3=\tenex -} - -\font\sixrm=cmr6 -\font\sixbf=cmbx6 -\font\sixi=cmmi6 -\font\sixsmc=cmr5 -\font\sixsy=cmsy6 -\def\sixpoint{% - \def\rm{\sixrm}\def\bf{\sixbf}% - \def\smc{\sixsmc}\baselineskip=8pt\rm}% - -\fontdimen13\tensy=2.6pt -\fontdimen14\tensy=2.6pt -\fontdimen15\tensy=2.6pt -\fontdimen16\tensy=1.2pt -\fontdimen17\tensy=1.2pt -\fontdimen18\tensy=1.2pt - -\font\eightrm=cmr8 -\font\ninerm=cmr9 -\font\twelverm=cmr10 scaled\magstep1 -\font\twelvebf=cmbx10 scaled\magstep 1 -\font\sixteenrm=cmr10 scaled\magstep2 -\def\titlefont{\sixteenrm} -\def\chapterfont{\twelvebf} -\def\authorfont{\twelverm} -\def\rheadfont{\tenrm} -\def\smc{\tensmc} - - - - -%%% COUNTERS FOR HEADINGS %%% - -\newcount\headcount -\headcount=1 -\newcount\seccount -\seccount=1 -\newcount\subseccount -\subseccount=1 -\def\reset{\global\seccount=1} -\global\headcount=0 - -%%% HEADINGS %%% - -\def\headone#1{\global\advance\headcount by 1 -\vskip12truept\parindent=0pt{\tenpoint\bf\the\headcount -\hskip11truept #1.}\par\nobreak\firstpar\global\advance\headcount by 0 - %\global\advance\seccount by 1 -\reset\vskip2truept} - -\def\headtwo#1{%\advance\seccount by -1% - \vskip12truept\parindent=0pt{\tenpoint\bf\the\headcount.% - \the\seccount\hskip11truept #1.}\enspace\ignorespaces\firstpar - \global\advance\headcount by 0\global\advance\seccount by 1} -% \global\advance\subseccount by 1} - - -%%% THEOREMS, PROOFS, DEFINITIONS, etc. %%% - -\def\thm#1{{\smc -#1\enspace} -\begingroup\it\ignorespaces\firstpar} - -\let\lem=\thm -\let\cor=\thm -\let\prop=\thm - -\def\endthm{\endgroup} -\let\endlem=\endthm -\let\endcor=\endthm -\let\endprop=\endthm - -\def\prf#1{{\it #1.}\rm\enspace\ignorespaces} -\let\rem=\prf -\let\case=\prf - - -\def\dfn#1{{\smc -#1\enspace} -\rm\ignorespaces} - - - -%%% FIGURES AND CAPTIONS %%% - -\def\caption#1\endcaption{\vskip18pt\ninerm\centerline{#1}\vskip18pt\tenrm} - -\newinsert\topins \newif\ifp@ge \newif\if@mid -\def\topinsert{\@midfalse\p@gefalse\@ins} -\def\midinsert{\@midtrue\@ins} -\def\pageinsert{\@midfalse\p@getrue\@ins} -\skip\topins=0pt %no space added when a topinsert is present -\count\topins=1000 %magnification factor (1 to 1) -\dimen\topins=\maxdimen -\def\@ins{\par\begingroup\setbox0=\vbox\bgroup} -\def\endinsert{\egroup - \if@mid \dimen@=\ht0 \advance\dimen@ by\dp0 - \advance\dimen@ by12\p@ \advance\dimen@ by\pagetotal - \ifdim\dimen@>\pagegoal \@midfalse\p@gefalse\fi\fi - \if@mid \bigskip \box0 \bigbreak - \else\insert\topins{\penalty100 - \splittopskip=0pt \splitmaxdepth=\maxdimen \floatingpenalty=0 - \ifp@ge \dimen@=\dp0 - \vbox to\vsize{\unvbox0 \kern-\dimen@} - \else \box0 \nobreak\bigskip\fi}\fi\endgroup} - - -%%% REFERENCES %%% - -\newdimen\refindent@ -\newdimen\refhangindent@ -\newbox\refbox@ -\setbox\refbox@=\hbox{\ninepoint\rm\baselineskip=11pt [00]}% Default 2 digits -\refindent@=\wd\refbox@ - -\def\resetrefindent#1{% - \setbox\refbox@=\hbox{\ninepoint\rm\baselineskip=11pt [#1]}% - \refindent@=\wd\refbox@} - -\def\Refs{% - \unskip\vskip1pc - \leftline{\noindent\tenpoint\bf References}% - \penalty10000 - \vskip4pt - \penalty10000 - \refhangindent@=\refindent@ - \global\advance\refhangindent@ by .5em - \global\everypar{\hangindent\refhangindent@}% - \parindent=0pt\ninepoint\rm} - -\def\sameauthor{\leavevmode\vbox to 1ex{\vskip 0pt plus 100pt - \hbox to 2em{\leaders\hrule\hfil}\vskip 0pt plus 300pt}} - -\def\ref#1\\#2\endref{\leavevmode\hbox to \refindent@{\hfil[#1]}\enspace #2\par} - - -%%% OUTPUT %%% - -\newinsert\margin -\dimen\margin=\maxdimen -\count\margin=0 \skip\margin=0pt - - -\def\footnote#1{\edef\@sf{\spacefactor\the\spacefactor}#1\@sf - \insert\footins\bgroup\eightpoint\hsize=30pc - \interlinepenalty100 \let\par=\endgraf - \leftskip=0pt \rightskip=0pt - \splittopskip=10pt plus 1pt minus 1pt \floatingpenalty=20000 -\smallskip -\item{#1}\bgroup\strut\aftergroup\@foot\let\next} -\skip\footins=6pt plus 2pt minus 4pt -\dimen\footins=30pc - -\newif\iftitle - - -\def\titlepage{\global\titletrue\footline={\hss\ninepoint\rm\folio\hss}} -\def\rhead{\ifodd\pageno CHAPTER TITLE - \else AUTHORS NAMES\fi} - -\def\makefootline{\ifnum\pageno>1\global\footline={\hfill}\fi - \baselineskip24\p@\vskip12\p@\fullline{\the\footline}} -\def\leftheadline{\hbox to \pagewidth{ - \vbox to 10pt{} - {\kern-8pt\tenrm\folio\hfill\ninerm\rhead}}} -\def\rightheadline{\hbox to \pagewidth{ - \vbox to 10pt{} - \kern-8pt\ninerm\rhead\hfil - {\kern-1pc\tenrm\folio}}} - -\def\onepageout#1{\shipout\vbox{ -\offinterlineskip - \vbox to 2.25pc{% - \iftitle \global\titlefalse -% \setcornerrules - \else\ifodd\pageno\rightheadline\else\leftheadline\fi\fi \vfill} -\vbox to \pageheight{ - \ifvoid\margin\else - \rlap{\kern31pc\vbox to0pt{\kern4pt\box\margin \vss}}\fi - #1 % -\ifvoid\footins\else - \vskip\skip\footins \kern 0pt - \hrule height\ruleht width 2.5pc \kern-\ruleht \kern 0pt - \unvbox\footins\fi -\boxmaxdepth=\maxdepth}} -\advancepageno} - -\def\setcornerrules{\hbox to \pagewidth{ - \vrule width 1pc height\ruleht \hfil \vrule width 1pc} - \hbox to \pagewidth{\llap{\sevenrm(page \folio)\kern1pc} - \vrule height1pc width\ruleht depth0pt - \hfil \vrule width\ruleht depth0pt}} -\output{\onepageout{\unvbox255}} - -\newbox\partialpage -\def\begindoublecolumns{\begingroup - \output={\global\setbox\partialpage=\vbox{\unvbox255\bigskip}}\eject - \output={\doublecolumnout} \hsize=20pc \vsize=101pc} -\def\enddoublecolumns{\output={\balancecolumns}\eject - \endgroup \pagegoal=\vsize} - -\def\doublecolumnout{\splittopskip=\topskip \splitmaxdepth=\maxdepth - \dimen@=50pc \advance\dimen@ by-\ht\partialpage - \setbox0=\vsplit255 to\dimen@ \setbox2=\vsplit255 to\dimen@ - \onepageout\pagesofar \unvbox255 \penalty\outputpenalty} -\def\pagesofar{\unvbox\partialpage - \wd0=\hsize \wd2=\hsize \hbox to\pagewidth{\box0\hfil\box2}} -\def\balancecolumns{\setbox0=\vbox{\unvbox255} \dimen@=\ht0 - \advance\dimen@ by\topskip \advance\dimen@ by-\baselineskip - \divide\dimen@ by2 \splittopskip=\topskip -{\vbadness=10000 \loop \global\setbox3=\copy0 - \global\setbox1=\vsplit3 to\dimen@ - \ifdim\ht3>\dimen@ \global\advance\dimen@ by1pt \repeat} - \setbox0=\vbox to\dimen@{\unvbox1} \setbox2=\vbox to\dimen@{\unvbox 3} -\pagesofar} - - - - -% Turn off @ as being a letter. -% -\catcode`\@=13 - -% End of ptexpprt.sty - - -CUT HERE............ |