path: root/Master/texmf-dist/source/latex/siam/sodaptex.all

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