%%%%%%%%%%%%%%%%%%%%%%%%%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