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