diff options
Diffstat (limited to 'texmf-dist/doc/latex/siam/ptexproc.tex')
-rw-r--r-- | texmf-dist/doc/latex/siam/ptexproc.tex | 354 |
1 files changed, 354 insertions, 0 deletions
diff --git a/texmf-dist/doc/latex/siam/ptexproc.tex b/texmf-dist/doc/latex/siam/ptexproc.tex new file mode 100644 index 00000000..b25d6560 --- /dev/null +++ b/texmf-dist/doc/latex/siam/ptexproc.tex @@ -0,0 +1,354 @@ +%%%%%%%%%%%%%%%%%%%%%%%%%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. 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. +%% +%% 4. Proofs are handled by \prf\endprf. If you want to use an end-of-proof +%% box, insert \qed right before the \endprf command. +%% +%% 5. 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. +%% +%% 6. 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. +%% +%% 7. 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 +%% +%% 8. 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. +%% +%% +%% 9. 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}. +%% +%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +\input ptexproc.sty + +\def\leftrh{} +\def\rightrh{} + +\startchapter %Place this command at the beginning of the file immediately + %after the \input command. + + + +\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 |