← Back to branch summary

~ubuntu-branches/debian/wheezy/texlive-extra/wheezy

« back to all changes in this revision

Viewing changes to texmf-dist/source/latex/siam/ltexproc.all

  • Committer: Bazaar Package Importer
  • Author(s): Norbert Preining
  • Date: 2007-01-12 19:08:37 UTC
  • mfrom: (1.2.1 upstream) (3.1.2 feisty)
  • Revision ID: james.westby@ubuntu.com-20070112190837-1cm7kyizrcdtk1ac
Tags: 2005.dfsg.3-1
http://bugs.debian.org/406426
blacklist siam.tpm and build new upstream, as the siam macros are not
DFSG free (no selling clause) (Closes: #406426)

Show diffs side-by-side

added added

removed removed

Lines of Context:
texmf-dist/source/latex/siam/ltexproc.all
1
 
 
2
 
 
3
 
This file constitutes the full distribution for SIAM Proceedings
4
 
Series LaTeX version macros. The files included here are:
5
 
 
6
 
ltexproc.tex    (An example file, also containing documentation)
7
 
 
8
 
ltexproc.sty    (The style file)
9
 
 
10
 
siamproc.bst    (for BiBTeX users)
11
 
 
12
 
To use these macros, separate the files at the indicated cut lines.
13
 
 
14
 
%%%%%%%%%%%%%%%%%%%%%%%%CUT HERE%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
15
 
 
16
 
% This is ltexproc.tex, an example file for use with the SIAM LaTeX
17
 
% Proceedings Series macros. 
18
 
% Please take the time to read the following comments, as they describe
19
 
% how to use these macros. This file can be composed and printed out for
20
 
% use as sample output.
21
 
 
22
 
% Any comments or questions regarding these macros should be directed to:
23
 
%
24
 
%                 Corey Gray
25
 
%                 SIAM
26
 
%                 3600 University City Science Center
27
 
%                 Philadelphia, PA 19104-2688
28
 
%                 USA
29
 
%                 Telephone: (215) 382-9800
30
 
%                 Fax: (215) 386-7999
31
 
%                 e-mail: gray@siam.org
32
 
 
33
 
 
34
 
% This file is to be used as an example for style only. It should not be read
35
 
% for content.
36
 
 
37
 
%%%%%%%%%%%%%%% PLEASE NOTE THE FOLLOWING STYLE RESTRICTIONS %%%%%%%%%%%%%%%
38
 
 
39
 
%%  1. There are no new tags.  Existing LaTeX tags have been formatted to
40
 
%%     match the Proceedings series style.    
41
 
%%
42
 
%%  2. You must use \cite in the text to mark your reference citations and 
43
 
%%     \bibitem in the listing of references at the end of your chapter. See
44
 
%%     the examples in the following file. The file siamproc.bst has been 
45
 
%%     included for use with BiBTeX. Please be sure to include the appropriate
46
 
%%     .bib file with BiBTeX submissions. You may also submit the .bbl file
47
 
%%     instead of the .bib file.
48
 
%% 
49
 
%%  3. Unless otherwise stated by your editor, do your chapter as if it
50
 
%%     is Chapter 1. The appropriate chapter number will be included during
51
 
%%     the production of the proceedings.
52
 
%%
53
 
%%  4. This macro is set up for three levels of headings (\section, 
54
 
%%     \subsection, and \subsubsection). The macro will automatically number 
55
 
%%     the headings for you.
56
 
%%
57
 
%%  5. The running heads are indicated by the \markboth command. Please 
58
 
%%     define the running heads by placing the authors last names in the 
59
 
%%     first field and the title of the paper in the second field.
60
 
%%     They should be typed initial cap and lower case. Please see the example.
61
 
%%     Neither field can contain more than 50 characters including spaces, 
62
 
%%     so please use a  shortened version of the title if necessary. For 
63
 
%%     papers with multiple authors please follow these rules; for 
64
 
%%     two authors type {Author 1 and Author 2}; for more that two authors type 
65
 
%%     {Author 1 et al.}.
66
 
%% 
67
 
%%  6. Theorems, Lemmas, Definitions, etc. are to be double-numbered, 
68
 
%%     indicating the section and the occurrence of that element
69
 
%%     within that section. (For example, the first theorem in the second
70
 
%%     section would be numbered 2.1. The macro will 
71
 
%%     automatically do the numbering for you.
72
 
%%
73
 
%%  7. Proofs are handled with the commands \begin{proof}\end{proof}.
74
 
%%     If you wish to use an end of proof box, use \qed preceding \end{proof}.
75
 
%%     The example uses one. It is not required.
76
 
%%
77
 
%%  8. Figures, equations, and tables must be single-numbered. All equation
78
 
%%     numbers are to be on the left. Figure captions should be placed under
79
 
%%     the figures they pertain to. Table captions should be placed above 
80
 
%%     the tables. Use existing LaTeX tags for these elements. Numbering of 
81
 
%%     these elements will be done automatically. SIAM supports the use of 
82
 
%%     psfig for including Postscript figures. All Postscript figures should be
83
 
%%     sent as separate files. A hardcopy version of all Postscript figures
84
 
%%     is also required. See note regarding this under How to Submit Your Paper.
85
 
%%   
86
 
%%  9. Grant information and author affiliations.
87
 
%%     This information is included in the file with the two commands,
88
 
%%     \thanks and \footnotemark []. (See example). The \thanks command 
89
 
%%     produces a footnote for the title or author, and places the 
90
 
%%     appropriate footnote symbol with the title or author and at the
91
 
%%     bottom of the page. The \footnotemark [] command allows the use of
92
 
%%     duplicate footnote symbols. This macro follows the normal LaTeX order 
93
 
%%     of footnote symbols. Below is a list of these symbols, and their 
94
 
%%     corresponding footnotemark:
95
 
%%
96
 
%%      asterisk                \footnotemark[1]
97
 
%%      single-dagger           \footnotemark[2]
98
 
%%      double-dagger           \footnotemark[3]
99
 
%%      section sign            \footnotemark[4]
100
 
%%      paragraph               \footnotemark[5]
101
 
%%      parallel                \footnotemark[6]
102
 
%%      double asterisk         \footnotemark[7]
103
 
%%      double single-dagger    \footnotemark[8]
104
 
%%      double double-dagger    \footnotemark[9]   
105
 
%%
106
 
%%    The following general rules for grants and affiliations apply:
107
 
%%      a) If there is a single grant for the paper, then the grant 
108
 
%%         information should be footnoted to the title.
109
 
%%      b) If there is more than one grant, include the grant information
110
 
%%         with each author's affiliation.
111
 
%%      c) If there are different grants for the paper but the authors share
112
 
%%         the same affiliation, footnote the grant information to the title.
113
 
%%         For example, The work of the first author was supported by xyz.
114
 
%%         The work of the second author was supported by abc. And so on.
115
 
%%      d) For authors sharing the same affiliation, use \thanks for the
116
 
%%         first author with that affiliation and the appropriate
117
 
%%         \footnotemark[] (from the list above) for all subsequent authors
118
 
%%         with that affiliation.
119
 
%%
120
 
%% 10. Special fonts.
121
 
%%     SIAM supports the use of AMS-TeX fonts version 2.0 and later. As 
122
 
%%     described in the manual for these fonts, they can be included by
123
 
%%     \input{amssym.def} and \input{amssym.tex}. These macros are not yet
124
 
%%     updated to make use of the New Font Selection Scheme (NFSS) of
125
 
%%     Mittelbach and Schopf. To make these macros compatible with NFSS, use 
126
 
%%     the oldlfont style option. 
127
 
%%
128
 
%% 11. How to Submit Your Paper.
129
 
%%     The electronic version of your paper should be sent to proceed@siam.org.
130
 
%%     A hardcopy version should also be submitted. Instructions are included
131
 
%%     in your acceptance letter. Please be sure to send hardcopy
132
 
%%     versions of any Postscript figures you have submitted electronically.
133
 
%%     Be sure to return your signed Copyright Transfer Agreement. We cannot
134
 
%%     publish your paper without it.
135
 
%%     
136
 
%%
137
 
%%
138
 
%%
139
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%-
140
 
%%%
141
 
 
142
 
 
143
 
\documentstyle[leqno,twoside,11pt,ltexproc]{article} %You must set up your
144
 
                                              %\documentstyle line like this.
145
 
 
146
 
 
147
 
\begin{document}
148
 
\cleardoublepage
149
 
\pagestyle{myheadings}
150
 
 
151
 
\title{Chapter 1\\
152
 
SIAM Proceedings Series Macros\\
153
 
 for Use With LaTeX\thanks{Any information regarding grants should be placed 
154
 
here.}}
155
 
\author{J. Corey Gray\thanks{Production Manager, Society for Industrial and Applied 
156
 
Mathematics, Philadelphia, PA.}
157
 
\and 
158
 
Tricia Manning\thanks{Publications Specialist, Society for Industrial and Applied
159
 
Mathematics, Philadelphia, PA.}
160
 
\and
161
 
Vickie Kearn\thanks{Publisher, Society for Industrial and Applied Mathematics,
162
 
Philadelphia, PA.}\\
163
 
\and
164
 
Nancy Abbott\thanks{Design Supervisor, Society for Industrial and Applied 
165
 
Mathematics, Philadelphia, PA}
166
 
\and 
167
 
Sue Ciambrano\thanks{Acquisitions Editor, Society for Industrial and Applied 
168
 
Mathematics, Philadelphia, PA}
169
 
\and
170
 
Paul Duggan\thanks{Composition Specialist, Society for Industrial and Applied 
171
 
Mathematics, Philadelphia, PA}
172
 
\and
173
 
Robbi Anne Albert\thanks{Production Assistant, Society for Industrial and Applied 
174
 
Mathematics, Philadelphia, PA}
175
 
\and 
176
 
Jean Anderson\thanks{Composition Coordinator, Society for Industrial and Applied 
177
 
Mathematics, Philadelphia, PA}
178
 
}
179
 
\date{}
180
 
\maketitle
181
 
\markboth{Gray et al.}{SIAM Proceedings Series Macros} % See section 5 above
182
 
                                                       % for explanation.
183
 
\pagenumbering{arabic}
184
 
 
185
 
\begin{abstract}An equivalence is shown between realizability of input/output (i/o) operators by
186
 
rational control systems and high-order algebraic differential equations for
187
 
i/o pairs.  This generalizes, to nonlinear systems, the equivalence
188
 
between autoregressive representations and finite dimensional linear
189
 
realizability. \end{abstract}
190
 
\section{Problem Specification}In this paper, we consider the solution of the $N \times
191
 
N$ linear
192
 
system
193
 
\begin{equation} \label{e1.1}
194
 
\cos \sin A x = b
195
 
\end{equation}
196
 
where $A$ is large, sparse, symmetric, and positive definite.  We consider
197
 
the direct solution of (\ref{e1.1}) by means of general sparse Gaussian
198
 
elimination.  In such a procedure, we find a permutation matrix $P$, and
199
 
compute the decomposition
200
 
\[
201
 
P A P^{t} = L D L^{t}
202
 
\]
203
 
where $L$ is unit lower triangular and $D$ is diagonal.  
204
 
 
205
 
 
206
 
\section{Design Considerations}Several good ordering algorithms (nested dissection and
207
 
minimum degree)
208
 
are available for computing $P$  \cite{GEORGELIU}, \cite{ROSE72}.
209
 
Since our interest here does not
210
 
focus directly on the ordering, we assume for convenience that $P=I$,
211
 
or that $A$ has been preordered to reflect an appropriate choice of $P$.
212
 
 
213
 
Our purpose here is to examine the nonnumerical complexity of the
214
 
sparse elimination algorithm given in  \cite{BANKSMITH}.
215
 
As was shown there, a general sparse elimination scheme based on the
216
 
bordering algorithm requires less storage for pointers and
217
 
row/column indices than more traditional implementations of general
218
 
sparse elimination.  This is accomplished by exploiting the m-tree,
219
 
a particular spanning tree for the graph of the filled-in matrix.
220
 
 
221
 
\begin{theorem} The method  was extended to three
222
 
dimensions. For the standard multigrid
223
 
coarsening
224
 
(in which, for a given grid, the next coarser grid has $1/8$
225
 
as many points), anisotropic problems require plane
226
 
relaxation to
227
 
obtain a good smoothing factor.\end{theorem} 
228
 
 
229
 
Several good ordering algorithms (nested dissection and minimum degree)
230
 
are available for computing $P$  \cite{GEORGELIU}, \cite{ROSE72}.
231
 
Since our interest here does not
232
 
focus directly on the ordering, we assume for convenience that $P=I$,
233
 
or that $A$ has been preordered to reflect an appropriate choice of $P$.
234
 
 
235
 
 
236
 
\begin{proof} In this paper we consider two methods. The first method
237
 
is
238
 
basically the method considered with two differences:
239
 
first, we perform plane relaxation by a two-dimensional
240
 
multigrid method, and second, we use a slightly different
241
 
choice of
242
 
interpolation operator, which improves performance
243
 
for nearly singular problems. In the second method coarsening
244
 
is done by successively coarsening in each of the three
245
 
independent variables and then ignoring the intermediate
246
 
grids; this artifice simplifies coding considerably.\qed
247
 
\end{proof}
248
 
 
249
 
Our purpose here is to examine the nonnumerical complexity of the
250
 
sparse elimination algorithm given in  \cite{BANKSMITH}.
251
 
As was shown there, a general sparse elimination scheme based on the
252
 
bordering algorithm requires less storage for pointers and
253
 
row/column indices than more traditional implementations of general
254
 
sparse elimination.  This is accomplished by exploiting the m-tree,
255
 
a particular spanning tree for the graph of the filled-in matrix.
256
 
 
257
 
\begin{Definition}{\rm We describe the two methods in \S 1.2. In \S\ 1.3. we
258
 
discuss
259
 
some remaining details.}
260
 
\end{Definition}
261
 
 
262
 
\begin{figure}
263
 
\vspace*{24pc}
264
 
\caption{This is  figure 1.}
265
 
\end{figure}
266
 
 
267
 
Our purpose here is to examine the nonnumerical complexity of the
268
 
sparse elimination algorithm given in  \cite{BANKSMITH}.
269
 
As was shown there, a general sparse elimination scheme based on the
270
 
bordering algorithm requires less storage for pointers and
271
 
row/column indices than more traditional implementations of general
272
 
sparse elimination.  
273
 
 
274
 
\begin{lemma} We discuss first the choice for $I_{k-1}^k$
275
 
which is a generalization. We assume that $G^{k-1}$ is
276
 
obtained
277
 
from $G^k$
278
 
by standard coarsening; that is, if $G^k$ is a tensor product
279
 
grid $G_{x}^k \times G_{y}^k \times G_{z}^k$,
280
 
$G^{k-1}=G_{x}^{k-1} \times G_{y}^{k-1} \times G_{z}^{k-1}$,
281
 
where $G_{x}^{k-1}$ is obtained by deleting every other grid
282
 
point of $G_x^k$ and similarly for $G_{y}^k$ and $G_{z}^k$.
283
 
\end{lemma}
284
 
 
285
 
This is accomplished by exploiting the m-tree,
286
 
a particular spanning tree for the graph of the filled-in matrix.
287
 
To our knowledge, the m-tree previously has not been applied in this
288
 
fashion to the numerical factorization, but it has been used,
289
 
directly or indirectly, in several optimal order algorithms for
290
 
computing the fill-in during the symbolic factorization phase
291
 
\cite{EISENSTAT} - \cite{LIU2}, \cite{ROSE76},  \cite{SCHREIBER}.
292
 
 
293
 
\subsection{Robustness} 
294
 
We do not
295
 
attempt to present an overview
296
 
here, but rather attempt to focus on those results that
297
 
are relevant to our particular algorithm.
298
 
This section assumes prior knowledge of the role of graph theory
299
 
in sparse Gaussian elimination; surveys of this role are
300
 
available in \cite{ROSE72} and \cite{GEORGELIU}. More general
301
 
discussions of elimination trees are given in
302
 
\cite{LAW} - \cite{LIU2}, \cite{SCHREIBER}.
303
 
Thus, at the $k$th stage, the bordering algorithm consists of
304
 
solving the lower triangular system
305
 
\begin{equation} \label{1.2}
306
 
 L_{k-1}v = c
307
 
\end{equation}
308
 
and setting
309
 
\begin{eqnarray} 
310
 
\ell &=& D^{-1}_{k-1}v , \\
311
 
\delta &=& \alpha - \ell^{t} v .
312
 
\end{eqnarray}
313
 
 
314
 
\subsubsection{Versatility.} We do not
315
 
attempt to present an overview
316
 
here, but rather attempt to focus on those results that
317
 
are relevant to our particular algorithm.
318
 
 
319
 
\section{Conclusions}  The special
320
 
structure of this problem allows us to make exact estimates of
321
 
the complexity.  For the old approach, we show that the
322
 
complexity of the intersection problem is $O(n^{3})$, the same
323
 
as the complexity of the numerical computations
324
 
\cite{GEORGELIU}, \cite{ROSEWHITTEN}.  For the
325
 
new approach, the complexity of the second part is reduced to
326
 
$O(n^{2} (\log n)^{2})$. 
327
 
 
328
 
\begin{thebibliography}{99}
329
 
 
330
 
 
331
 
\bibitem{BANKSMITH}
332
 
R.~E. Bank and R.~K. Smith, {\em General sparse elimination requires no
333
 
  permanent integer storage}, SIAM J. Sci. Stat. Comput., 8 (1987),
334
 
  pp.~574--584.
335
 
 
336
 
\bibitem{EISENSTAT}
337
 
S.~C. Eisenstat, M.~C. Gursky, M.~Schultz, and A.~Sherman, {\em
338
 
  Algorithms and data structures for sparse symmetric gaussian elimination},
339
 
  SIAM J. Sci. Stat. Comput., 2 (1982), pp.~225--237.
340
 
 
341
 
\bibitem{GEORGELIU}
342
 
A.~George and J.~Liu, {\em Computer Solution of Large Sparse Positive
343
 
  Definite Systems}, Prentice Hall, Englewood Cliffs, NJ, 1981.
344
 
 
345
 
\bibitem{LAW}
346
 
K.~H. Law and S.~J. Fenves, {\em A node addition model for symbolic
347
 
  factorization}, ACM TOMS, 12 (1986), pp.~37--50.
348
 
 
349
 
\bibitem{LIU}
350
 
J.~W.~H. Liu, {\em A compact row storage scheme for cholesky factors
351
 
  using elimination trees}, ACM TOMS, 12 (1986), pp.~127--148.
352
 
 
353
 
\bibitem{LIU2}
354
 
\sameauthor , {\em The role of
355
 
  elimination trees in sparse factorization}, Tech. Report CS-87-12,Department
356
 
  of Computer Science, York University, Ontario, Canada, 1987.
357
 
 
358
 
\bibitem{ROSE72}
359
 
D.~J. Rose, {\em A graph theoretic study of the numeric solution of
360
 
  sparse positive definite systems}, in Graph Theory and Computing, Academic   Press, New
361
 
York, 1972.
362
 
 
363
 
\bibitem{ROSE76}
364
 
D.~J. Rose, R.~E. Tarjan, and G.~S. Lueker, {\em Algorithmic aspects of
365
 
  vertex elimination on graphs}, SIAM J. Comput., 5 (1976), pp.~226--283.
366
 
 
367
 
\bibitem{ROSEWHITTEN}
368
 
D.~J. Rose and G.~F. Whitten, {\em A recursive analysis of disection
369
 
  strategies}, in Sparse Matrix Computations, Academic Press, New York, 1976.
370
 
 
371
 
\bibitem{SCHREIBER}
372
 
R.~Schreiber, {\em A new implementation of sparse gaussian elimination},
373
 
  ACM TOMS, 8 (1982), pp.~256--276.
374
 
 
375
 
\end{thebibliography}
376
 
 
377
 
\end{document}
378
 
 
379
 
%%%%%%%%%%%%%%%%%%%%%%%%%%CUT HERE%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
380
 
 
381
 
%   This is ltexproc.sty. 
382
 
%   This file may be freely distributed but may not be altered in any way.
383
 
%   Any comments or questions regarding these macros should be directed to:
384
 
 
385
 
%                 Corey Gray
386
 
%                 SIAM
387
 
%                 3600 University City Science Center
388
 
%                 Philadelphia, PA 19104-2688
389
 
%                 USA
390
 
%                 Telephone: (215) 382-9800
391
 
%                 Fax: (215) 386-7999
392
 
%                 e-mail: gray@siam.org
393
 
 
394
 
%   This is a file of macros and definitions for creating a chapter for 
395
 
%   publication in the SIAM Proceedings series using LaTeX.
396
 
 
397
 
%   Report the version.
398
 
\message{*** SIAM LaTeX Proceedings Series macro package, version 1.0,
399
 
November 6, 1992 ***} 
400
 
 
401
 
\pretolerance=800 
402
 
\tolerance=10000 
403
 
\sloppy 
404
 
 
405
 
 
406
 
\vsize=56pc 
407
 
\hsize=36pc 
408
 
\baselineskip=13pt 
409
 
\hoffset -.5in
410
 
\voffset -.5in
411
 
\footskip=18pt 
412
 
\topmargin 24pt  
413
 
\headheight 12pt  
414
 
\headsep 15pt  
415
 
\textheight 53.5pc  \advance\textheight by \topskip 
416
 
\textwidth 36pc  
417
 
\parskip 0pt
418
 
\parindent 18pt
419
 
\def\topfraction{.9}
420
 
\def\textfraction{.1}
421
 
\def\topnumber{2}
422
 
%% footnotes  to be set 8/10 
423
 
\def\footnotesize{\@setsize\footnotesize{11pt}\ixpt\@ixpt 
424
 
   %  \indent 
425
 
       \abovedisplayskip \z@ 
426
 
      \belowdisplayskip\z@ 
427
 
     \abovedisplayshortskip\abovedisplayskip 
428
 
    \belowdisplayshortskip\belowdisplayshortskip 
429
 
\def\@listi{\leftmargin\leftmargini \topsep 3pt plus 1pt minus 1pt 
430
 
     \parsep 2pt plus 1pt minus 1pt 
431
 
    \itemsep \parsep}} 
432
 
 
433
 
\let\referencesize\footnotesize 
434
 
 
435
 
\footnotesep 0pt  
436
 
 
437
 
\skip\footins 12pt plus 12pt  
438
 
 
439
 
\def\footnoterule{\kern3\p@  \hrule width 3em\vspace{3pt}} % the \hrule is .4pt high 
440
 
 
441
 
 
442
 
\def\ps@plain{\let\@mkboth\@gobbletwo 
443
 
     \def\@oddfoot{{\hfil\small\thepage\hfil}}% 
444
 
     \def\@oddhead{} 
445
 
      \def\@evenhead{}\def\@evenfoot{}} 
446
 
 
447
 
 
448
 
 
449
 
\def\ps@headings{\let\@mkboth\markboth 
450
 
        \def\@oddfoot{}\def\@evenfoot{}% 
451
 
        \def\@evenhead{{\rm\thepage}\hspace*{2pc}{\sc\leftmark}\hfil}%
452
 
        \def\@oddhead{\hfil{\noindent\sc\rightmark}\hspace*{2pc}{\rm\thepage}}%
453
 
 
454
 
 
455
 
 
456
 
\def\ps@myheadings{\let\@mkboth\@gobbletwo 
457
 
 \def\@oddfoot{}\def\@evenfoot{}% 
458
 
 \def\@oddhead{\hfil{\sc\rightmark}\hspace*{2pc}{\normalsize\rm\thepage}}% 
459
 
 \def\@evenhead{{\normalsize\rm\thepage}\hspace*{2pc}{\sc\leftmark}\hfil}% 
460
 
%        \def\chaptermark##1{}% 
461
 
 %       \def\sectionmark##1{}\def\subsectionmark##1{}} 
462
 
}} 
463
 
 
464
 
 
465
 
 
466
 
\def\theequation{\arabic{equation}} 
467
 
 
468
 
\def\abstract{\if@twocolumn
469
 
\section*{Abstract}
470
 
\else \small 
471
 
\begin{center}
472
 
{\bf Abstract\vspace{-.5em}\vspace{3pt}} 
473
 
\end{center}
474
 
\quotation 
475
 
\fi}
476
 
\def\endabstract{\if@twocolumn\else\endquotation\fi}
477
 
 
478
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
479
 
%                                         % 
480
 
%     THEOREMS, PROOFS, ALGORITHMS        % 
481
 
%                                         % 
482
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
483
 
 
484
 
%%% defined proof environment by theorem model (took out counter) 
485
 
 
486
 
\def\qed{{\qquad \vbox{\hrule\hbox{%
487
 
   \vrule height1.3ex\hskip0.8ex\vrule}\hrule
488
 
  }}\par}   
489
 
 
490
 
\def\newproof#1{\@nprf{#1}} 
491
 
 
492
 
\def\@nprf#1#2{\@xnprf{#1}{#2}} 
493
 
 
494
 
\def\@xnprf#1#2{\expandafter\@ifdefinable\csname #1\endcsname 
495
 
\global\@namedef{#1}{\@prf{#1}{#2}}\global\@namedef{end#1}{\@endproof}} 
496
 
 
497
 
\def\@prf#1#2{\@xprf{#1}{#2}} 
498
 
 
499
 
\def\@xprf#1#2{\@beginproof{#2}{\csname the#1\endcsname}\ignorespaces} 
500
 
 
501
 
 
502
 
 
503
 
%%% defined algorithm environment by theorem model 
504
 
 
505
 
\def\newalgorithm#1{\@ifnextchar[{\@oalg{#1}}{\@nalg{#1}}} 
506
 
 
507
 
\def\@nalg#1#2{% 
508
 
\@ifnextchar[{\@xnalg{#1}{#2}}{\@ynalg{#1}{#2}}} 
509
 
 
510
 
\def\@xnalg#1#2[#3]{\expandafter\@ifdefinable\csname #1\endcsname 
511
 
{\@definecounter{#1}\@addtoreset{#1}{#3}% 
512
 
\expandafter\xdef\csname the#1\endcsname{\expandafter\noexpand 
513
 
  \csname the#3\endcsname \@thmcountersep \@thmcounter{#1}}% 
514
 
\global\@namedef{#1}{\@alg{#1}{#2}}\global\@namedef{end#1}{\@endalgorithm}}} 
515
 
 
516
 
\def\@ynalg#1#2{\expandafter\@ifdefinable\csname #1\endcsname 
517
 
{\@definecounter{#1}% 
518
 
\expandafter\xdef\csname the#1\endcsname{\@thmcounter{#1}}% 
519
 
\global\@namedef{#1}{\@alg{#1}{#2}}\global\@namedef{end#1}{\@endalgorithm}}} 
520
 
 
521
 
\def\@oalg#1[#2]#3{\expandafter\@ifdefinable\csname #1\endcsname 
522
 
  {\global\@namedef{the#1}{\@nameuse{the#2}}% 
523
 
\global\@namedef{#1}{\@alg{#2}{#3}}% 
524
 
\global\@namedef{end#1}{\@endalgorithm}}} 
525
 
 
526
 
\def\@alg#1#2{\refstepcounter 
527
 
    {#1}\@ifnextchar[{\@yalg{#1}{#2}}{\@xalg{#1}{#2}}} 
528
 
 
529
 
\def\@xalg#1#2{\@beginalgorithm{#2}{\csname the#1\endcsname}\ignorespaces} 
530
 
\def\@yalg#1#2[#3]{\@opargbeginalgorithm{#2}{\csname 
531
 
       the#1\endcsname}{#3}\ignorespaces} 
532
 
 
533
 
 
534
 
 
535
 
 
536
 
\def\@beginproof#1{\rm {\it #1.\ }} 
537
 
\def\@endproof{\outerparskip 0pt\endtrivlist} 
538
 
 
539
 
\def\@begintheorem#1#2{\it {\sc #1\ #2.\ }} 
540
 
\def\@opargbegintheorem#1#2#3{\it 
541
 
      {\sc #1\ #2\ (#3).\ }} 
542
 
\def\@endtheorem{\outerparskip 0pt\endtrivlist} 
543
 
 
544
 
%\def\@begindefinition#1#2{\rm \trivlist \item[\hskip \labelsep{\sc #1\ #2.}]} 
545
 
%\def\@opargbegindefinition#1#2#3{\rm \trivlist 
546
 
%      \item[\hskip \labelsep{\sc #1\ #2.\ (#3)}]} 
547
 
%\def\@enddefinition{\outerparskip 0pt\endtrivlist} 
548
 
 
549
 
 
550
 
\def\@beginalgorithm#1#2{\rm \trivlist \item[\hskip \labelsep{\sc #1\ #2.}]} 
551
 
\def\@opargbeginalgorithm#1#2#3{\rm \trivlist 
552
 
      \item[\hskip \labelsep{\sc #1\ #2.\ (#3)}]} 
553
 
\def\@endalgorithm{\outerparskip 6pt\endtrivlist} 
554
 
 
555
 
 
556
 
\newskip\outerparskip 
557
 
 
558
 
\def\trivlist{\parsep\outerparskip 
559
 
  \@trivlist \labelwidth\z@ \leftmargin\z@ 
560
 
  \itemindent\parindent \def\makelabel##1{##1}} 
561
 
 
562
 
\def\@trivlist{\topsep=0pt\@topsepadd\topsep 
563
 
  \if@noskipsec \leavevmode \fi 
564
 
  \ifvmode \advance\@topsepadd\partopsep \else \unskip\par\fi 
565
 
  \if@inlabel \@noparitemtrue \@noparlisttrue  
566
 
    \else \@noparlistfalse \@topsep\@topsepadd \fi 
567
 
    \advance\@topsep \parskip 
568
 
  \leftskip\z@\rightskip\@rightskip \parfillskip\@flushglue 
569
 
  \@setpar{\if@newlist\else{\@@par}\fi}% 
570
 
  \global\@newlisttrue \@outerparskip\parskip} 
571
 
 
572
 
 
573
 
\def\endtrivlist{\if@newlist\@noitemerr\fi  
574
 
   \if@inlabel\indent\fi  
575
 
   \ifhmode\unskip \par\fi  
576
 
   \if@noparlist \else 
577
 
      \ifdim\lastskip >\z@ \@tempskipa\lastskip \vskip -\lastskip 
578
 
         \advance\@tempskipa\parskip \advance\@tempskipa -\@outerparskip  
579
 
         \vskip\@tempskipa 
580
 
   \fi\@endparenv\fi 
581
 
   \vskip\outerparskip} 
582
 
 
583
 
 
584
 
 
585
 
 \newproof{@proof}{Proof} 
586
 
 \newenvironment{proof}{\begin{@proof}}{\end{@proof}} 
587
 
 
588
 
 \newtheorem{@theorem}{Theorem}[section] 
589
 
 \newenvironment{theorem}{\begin{@theorem}}{\end{@theorem}} 
590
 
 
591
 
% \newalgorithm{@algorithm}{Algorithm}[section] 
592
 
% \newenvironment{algorithm}{\begin{@algorithm}}{\end{@algorithm}} 
593
 
 
594
 
 
595
 
 
596
 
\newtheorem{lemma}{Lemma}[section] 
597
 
\newtheorem{fact}{Fact}[section] 
598
 
\newtheorem{corollary}{Corollary}[section] 
599
 
\newtheorem{axiom}{Axiom}[section] 
600
 
\newtheorem{cond}{Condition}[section] 
601
 
\newtheorem{property}{Property}[section]  
602
 
\newtheorem{proposition}{Proposition}[section] 
603
 
 
604
 
\newtheorem{Conjecture}{Conjecture}[section] 
605
 
\newtheorem{Definition}{Definition}[section] 
606
 
\newtheorem{Lemma}{Lemma}[section] 
607
 
\newtheorem{Remark}{Remark}[section] 
608
 
 
609
 
\newproof{Example}{Example} 
610
 
\newproof{Method}{Method} 
611
 
\newproof{Exercise}{Exercise} 
612
 
 
613
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
614
 
%                                         % 
615
 
%        TABLE AND FIGURE CAPTIONS        % 
616
 
%                                         % 
617
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
618
 
 \def\@figtxt{figure}
619
 
\long\def\@makecaption#1#2{\small
620
 
\setlength{\parindent}{18pt}
621
 
\baselineskip 14pt
622
 
 \ifx\@captype\@figtxt
623
 
 \vskip 10pt 
624
 
 \setbox\@tempboxa\hbox{{\sc #1} {\it #2}}
625
 
 \ifdim \wd\@tempboxa >\hsize {\sc #1} {\it #2}\par \else \hbox
626
 
to\hsize{\hfil\box\@tempboxa\hfil}%
627
 
 \fi\else\hbox to\hsize{\hfil{\sc #1}\hfil}%
628
 
 \setbox\@tempboxa\hbox{{\it #2}}%
629
 
 \ifdim \wd\@tempboxa >\hsize {\it #2}\par \else
630
 
 \hbox to \hsize{\hfil\box\@tempboxa\hfil}\fi
631
 
 \vskip 10pt
632
 
 \fi}
633
 
 
634
 
 
635
 
%\newif\iftable  \global\tablefalse 
636
 
 
637
 
 
638
 
%\long\def\@makecaption#1#2{% 
639
 
%\setlength{\parindent}{18pt}
640
 
% \vskip 12pt  
641
 
%    \iftable 
642
 
 %              \hbox to \hsize{\hfil\sc #1\hfil} 
643
 
 %              \hbox to \hsize{\hfil\it #2\hfil} 
644
 
 %              \global\tablefalse 
645
 
 %    \else 
646
 
 %      \setbox\@tempboxa\hbox{{\small#1} {\small\it#2}} 
647
 
 %        \ifdim \wd\@tempboxa >\hsize  
648
 
 %           \indent{\small#1}{\small\it#2}\par  
649
 
 %               \else  
650
 
 %                \hbox to\hsize{\hfil\box\@tempboxa\hfil}\fi 
651
 
 % \fi} 
652
 
% \vskip 6pt} 
653
 
 
654
 
 
655
 
 
656
 
%\def\figure{\global\tablefalse\@float{figure}} 
657
 
\def\fnum@figure{\par\sc Fig. \thefigure.\ } 
658
 
%\def\fnum@figure{\par\sc Fig. \thefigure\ } 
659
 
 
660
 
%\def\table{\global\tabletrue\@float{table}} 
661
 
\def\fnum@table{\small \sc Table \thetable} 
662
 
 
663
 
 
664
 
 
665
 
 
666
 
 
667
 
 
668
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
669
 
%                                         % 
670
 
%             SECTIONS                    % 
671
 
%                                         % 
672
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
673
 
 
674
 
\def\section{\@startsection {section}{1}{\z@}{-3.5ex plus -1ex minus 
675
 
 -.2ex}%{2.3ex plus .2ex}
676
 
{2pt}{\large\bf}}
677
 
\def\subsection{\@startsection{subsection}{2}{\z@}{-3.25ex plus -1ex minus 
678
 
 -.2ex}%{1.5ex plus .2ex}
679
 
{2pt}{\large\bf}}
680
 
\def\subsubsection{\@startsection {subsubsection}{3}{\z@}{1.3ex plus .5ex minus 
681
 
    .2ex}{-.5em plus -.1em}{\normalsize\bf}}
682
 
 
683
 
 
684
 
 
685
 
 
686
 
 
687
 
 
688
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
689
 
%%                                          %% 
690
 
%%            BIBLIOGRAPHY                  %% 
691
 
%%                                          %% 
692
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
693
 
 
694
 
 
695
 
\def\thebibliography#1{% 
696
 
%\cleardoublepage 
697
 
\parindent 0em
698
 
\vspace{9pt}
699
 
\begin{flushleft}\large\bf {References}\end{flushleft}
700
 
\addvspace{3pt}\nopagebreak\list 
701
 
 %% default is no labels, for those not using \cite or BibTeX 
702
 
{[\arabic{enumi}]} {\settowidth\labelwidth{[#1]} 
703
 
%%{[\arabic{enumi}]}{\settowidth\labelwidth{mm} 
704
 
\leftmargin\labelwidth 
705
 
\leftmargin=17pt
706
 
 \advance\leftmargin\labelsep 
707
 
 \usecounter{enumi}\@bibsetup} 
708
 
\def\newblock{\hskip .11em plus .33em minus -.07em} 
709
 
 \sloppy\clubpenalty4000\widowpenalty4000 
710
 
 \sfcode`\.=1000\relax} 
711
 
 
712
 
 
713
 
 
714
 
%% setup 8/10 type 
715
 
\def\@bibsetup{%\itemindent=0pt
716
 
\itemsep=0pt \parsep=0pt
717
 
\small} 
718
 
 
719
 
\def\sameauthor{\leavevmode\vrule height 2pt depth -1.6pt width 23pt} 
720
 
 
721
 
  
722
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
723
 
%                                         % 
724
 
%                INDEX                    % 
725
 
%                                         % 
726
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
727
 
 
728
 
 
729
 
%makeindex.sty        official version 6.4  
730
 
%The second line came from /usr/misc/lib/tex82/report.sty. 
731
 
 
732
 
\def\theindex{\@restonecoltrue\if@twocolumn\@restonecolfalse\fi 
733
 
\columnseprule \z@ 
734
 
\columnsep 35pt\twocolumn[\chapter*{Index}] 
735
 
 \parskip\z@ plus .3pt\relax\let\item\@idxitem} 
736
 
 
737
 
 
738
 
\def\printindex{\cleardoublepage\markboth{INDEX}{INDEX} 
739
 
\addcontentsline{toc}{chapter}{Index}\@input{\jobname.ind}} 
740
 
 
741
 
\ps@headings  
742
 
 
743
 
 
744
 
%%% end of style file 
745
 
 
746
 
%%%%%%%%%%%%%%%%%%%%%%%%%%CUT HERE%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
747
 
 
748
 
% This is siamproc.bst
749
 
% SIAM bibliography style (29-Jan-88 version)
750
 
%    numeric labels, alphabetic order, Mathematical Reviews abbreviations,
751
 
%    names in \sc, titles in italics, book titles mixed upper-lower and article
752
 
%    titles lowercase, commas separate all fields except before "notes".
753
 
%
754
 
%   History
755
 
%    1/30/86    (HWT)   Original version, by Howard Trickey.
756
 
%    6/15/87    (HWT)   Fix format.editors---Martin Costabel.
757
 
%    1/29/88    (OP&HWT) Updated for BibTeX version 0.99a, Oren Patashnik;
758
 
%                       THIS `siam' VERSION DOES NOT WORK WITH BIBTEX 0.98i.
759
 
 
760
 
ENTRY
761
 
  { address
762
 
    author
763
 
    booktitle
764
 
    chapter
765
 
    edition
766
 
    editor
767
 
    howpublished
768
 
    institution
769
 
    journal
770
 
    key
771
 
    month
772
 
    note
773
 
    number
774
 
    organization
775
 
    pages
776
 
    publisher
777
 
    school
778
 
    series
779
 
    title
780
 
    type
781
 
    volume
782
 
    year
783
 
  }
784
 
  {}
785
 
  { label }
786
 
 
787
 
INTEGERS { output.state before.all mid.sentence after.block }
788
 
 
789
 
FUNCTION {init.state.consts}
790
 
{ #0 'before.all :=
791
 
  #1 'mid.sentence :=
792
 
  #2 'after.block :=
793
 
}
794
 
 
795
 
STRINGS { s t }
796
 
 
797
 
FUNCTION {output.nonnull}
798
 
{ 's :=
799
 
  output.state mid.sentence =
800
 
    { ", " * write$ }
801
 
    { output.state after.block =
802
 
        { add.period$ write$
803
 
          newline$
804
 
          "\newblock " write$
805
 
        }
806
 
        'write$
807
 
      if$
808
 
      mid.sentence 'output.state :=
809
 
    }
810
 
  if$
811
 
  s
812
 
}
813
 
 
814
 
FUNCTION {output}
815
 
{ duplicate$ empty$
816
 
    'pop$
817
 
    'output.nonnull
818
 
  if$
819
 
}
820
 
 
821
 
FUNCTION {output.check}
822
 
{ 't :=
823
 
  duplicate$ empty$
824
 
    { pop$ "empty " t * " in " * cite$ * warning$ }
825
 
    'output.nonnull
826
 
  if$
827
 
}
828
 
 
829
 
FUNCTION {output.bibitem}
830
 
{ newline$
831
 
  "\bibitem{" write$
832
 
  cite$ write$
833
 
  "}" write$
834
 
  newline$
835
 
  ""
836
 
  before.all 'output.state :=
837
 
}
838
 
 
839
 
FUNCTION {fin.entry}
840
 
{ add.period$
841
 
  write$
842
 
  newline$
843
 
}
844
 
 
845
 
FUNCTION {new.block}
846
 
{ output.state before.all =
847
 
    'skip$
848
 
    { after.block 'output.state := }
849
 
  if$
850
 
}
851
 
 
852
 
FUNCTION {not}
853
 
{   { #0 }
854
 
    { #1 }
855
 
  if$
856
 
}
857
 
 
858
 
FUNCTION {and}
859
 
{   'skip$
860
 
    { pop$ #0 }
861
 
  if$
862
 
}
863
 
 
864
 
FUNCTION {or}
865
 
{   { pop$ #1 }
866
 
    'skip$
867
 
  if$
868
 
}
869
 
 
870
 
FUNCTION {new.block.checka}
871
 
{ empty$
872
 
    'skip$
873
 
    'new.block
874
 
  if$
875
 
}
876
 
 
877
 
FUNCTION {field.or.null}
878
 
{ duplicate$ empty$
879
 
    { pop$ "" }
880
 
    'skip$
881
 
  if$
882
 
}
883
 
 
884
 
FUNCTION {emphasize}
885
 
{ duplicate$ empty$
886
 
    { pop$ "" }
887
 
    { "{\em " swap$ * "}" * }
888
 
  if$
889
 
}
890
 
 
891
 
FUNCTION {scapify}
892
 
{ duplicate$ empty$
893
 
    { pop$ "" }
894
 
    { "{\sc " swap$ * "}" * }
895
 
  if$
896
 
}
897
 
 
898
 
INTEGERS { nameptr namesleft numnames }
899
 
 
900
 
FUNCTION {format.names}
901
 
{ 's :=
902
 
  #1 'nameptr :=
903
 
  s num.names$ 'numnames :=
904
 
  numnames 'namesleft :=
905
 
    { namesleft #0 > }
906
 
    { s nameptr "{f.~}{vv~}{ll}{, jj}" format.name$ 't :=
907
 
      nameptr #1 >
908
 
        { namesleft #1 >
909
 
            { ", " * t * }
910
 
            { numnames #2 >
911
 
                { "," * }
912
 
                'skip$
913
 
              if$
914
 
              t "others" =
915
 
                { " et~al." * }
916
 
                { " and " * t * }
917
 
              if$
918
 
            }
919
 
          if$
920
 
        }
921
 
        't
922
 
      if$
923
 
      nameptr #1 + 'nameptr :=
924
 
      namesleft #1 - 'namesleft :=
925
 
    }
926
 
  while$
927
 
}
928
 
 
929
 
STRINGS { last.authors }
930
 
 
931
 
FUNCTION {init.last.authors}
932
 
{ "" 'last.authors :=
933
 
}
934
 
 
935
 
FUNCTION {format.authors}
936
 
{ author empty$
937
 
    { "" 'last.authors :=
938
 
      ""
939
 
    }
940
 
    { author last.authors =
941
 
        { "\leavevmode\vrule height 2pt depth -1.6pt width 23pt" }
942
 
        { author format.names }% scapify }
943
 
      if$
944
 
      author 'last.authors :=
945
 
    }
946
 
  if$
947
 
}
948
 
 
949
 
FUNCTION {format.organization}
950
 
{ organization empty$
951
 
    { "" 'last.authors :=
952
 
      ""
953
 
    }
954
 
    { organization last.authors =
955
 
        { "\leavevmode\vrule height 2pt depth -1.6pt width 23pt" }
956
 
        { organization scapify }
957
 
      if$
958
 
      organization 'last.authors :=
959
 
    }
960
 
  if$
961
 
}
962
 
 
963
 
FUNCTION {format.editors}
964
 
{ editor empty$
965
 
    { "" 'last.authors :=
966
 
      ""
967
 
    }
968
 
    { editor last.authors =
969
 
        { "\leavevmode\vrule height 2pt depth -1.6pt width 23pt" }
970
 
        { editor format.names scapify }
971
 
      if$
972
 
      editor num.names$ #1 >
973
 
        { ", eds." * }
974
 
        { ", ed." * }
975
 
      if$
976
 
      editor 'last.authors :=
977
 
    }
978
 
  if$
979
 
}
980
 
 
981
 
FUNCTION {format.ineditors}
982
 
{ editor empty$
983
 
    { "" }
984
 
    { editor format.names
985
 
      editor num.names$ #1 >
986
 
        { ", eds." * }
987
 
        { ", ed." * }
988
 
      if$
989
 
    }
990
 
  if$
991
 
}
992
 
 
993
 
FUNCTION {format.title}
994
 
{ title empty$
995
 
    { "" }
996
 
    { title "t" change.case$ emphasize }
997
 
  if$
998
 
}
999
 
 
1000
 
FUNCTION {n.dashify}
1001
 
{ 't :=
1002
 
  ""
1003
 
    { t empty$ not }
1004
 
    { t #1 #1 substring$ "-" =
1005
 
        { t #1 #2 substring$ "--" = not
1006
 
            { "--" *
1007
 
              t #2 global.max$ substring$ 't :=
1008
 
            }
1009
 
            {   { t #1 #1 substring$ "-" = }
1010
 
                { "-" *
1011
 
                  t #2 global.max$ substring$ 't :=
1012
 
                }
1013
 
              while$
1014
 
            }
1015
 
          if$
1016
 
        }
1017
 
        { t #1 #1 substring$ *
1018
 
          t #2 global.max$ substring$ 't :=
1019
 
        }
1020
 
      if$
1021
 
    }
1022
 
  while$
1023
 
}
1024
 
 
1025
 
FUNCTION {format.date}
1026
 
{ year empty$
1027
 
    { month empty$
1028
 
        { "" }
1029
 
        { "there's a month but no year in " cite$ * warning$
1030
 
          month
1031
 
        }
1032
 
      if$
1033
 
    }
1034
 
    { month empty$
1035
 
        'year
1036
 
        { month " " * year * }
1037
 
      if$
1038
 
    }
1039
 
  if$
1040
 
}
1041
 
 
1042
 
FUNCTION {format.btitle}
1043
 
{ title emphasize
1044
 
}
1045
 
 
1046
 
FUNCTION {tie.or.space.connect}
1047
 
{ duplicate$ text.length$ #3 <
1048
 
    { "~" }
1049
 
    { " " }
1050
 
  if$
1051
 
  swap$ * *
1052
 
}
1053
 
 
1054
 
FUNCTION {either.or.check}
1055
 
{ empty$
1056
 
    'pop$
1057
 
    { "can't use both " swap$ * " fields in " * cite$ * warning$ }
1058
 
  if$
1059
 
}
1060
 
 
1061
 
FUNCTION {format.bvolume}
1062
 
{ volume empty$
1063
 
    { "" }
1064
 
    { "vol.~" volume *
1065
 
      series empty$
1066
 
        'skip$
1067
 
        { " of " * series * }
1068
 
      if$
1069
 
      "volume and number" number either.or.check
1070
 
    }
1071
 
  if$
1072
 
}
1073
 
 
1074
 
FUNCTION {format.number.series}
1075
 
{ volume empty$
1076
 
    { number empty$
1077
 
        { series field.or.null }
1078
 
        { "no.~" number *
1079
 
          series empty$
1080
 
            { "there's a number but no series in " cite$ * warning$ }
1081
 
            { " in " * series * }
1082
 
          if$
1083
 
        }
1084
 
      if$
1085
 
    }
1086
 
    { "" }
1087
 
  if$
1088
 
}
1089
 
 
1090
 
FUNCTION {format.edition}
1091
 
{ edition empty$
1092
 
    { "" }
1093
 
    { edition "l" change.case$ "~ed." * }
1094
 
  if$
1095
 
}
1096
 
 
1097
 
INTEGERS { multiresult }
1098
 
 
1099
 
FUNCTION {multi.page.check}
1100
 
{ 't :=
1101
 
  #0 'multiresult :=
1102
 
    { multiresult not
1103
 
      t empty$ not
1104
 
      and
1105
 
    }
1106
 
    { t #1 #1 substring$
1107
 
      duplicate$ "-" =
1108
 
      swap$ duplicate$ "," =
1109
 
      swap$ "+" =
1110
 
      or or
1111
 
        { #1 'multiresult := }
1112
 
        { t #2 global.max$ substring$ 't := }
1113
 
      if$
1114
 
    }
1115
 
  while$
1116
 
  multiresult
1117
 
}
1118
 
 
1119
 
FUNCTION {format.pages}
1120
 
{ pages empty$
1121
 
    { "" }
1122
 
    { pages multi.page.check
1123
 
        { "pp.~" pages n.dashify * }
1124
 
        { "p.~" pages * }
1125
 
      if$
1126
 
    }
1127
 
  if$
1128
 
}
1129
 
 
1130
 
FUNCTION {format.vol.year}
1131
 
{ volume field.or.null
1132
 
  year empty$
1133
 
    { "empty year in " cite$ * warning$ }
1134
 
    { " (" year * ")" * * }
1135
 
  if$
1136
 
}
1137
 
 
1138
 
FUNCTION {format.chapter.pages}
1139
 
{ chapter empty$
1140
 
    'format.pages
1141
 
    { type empty$
1142
 
        { "ch.~" chapter * }
1143
 
        { type "l" change.case$ chapter tie.or.space.connect }
1144
 
      if$
1145
 
      pages empty$
1146
 
        'skip$
1147
 
        { ", " * format.pages * }
1148
 
      if$
1149
 
    }
1150
 
  if$
1151
 
}
1152
 
 
1153
 
FUNCTION {format.in.ed.booktitle}
1154
 
{ booktitle empty$
1155
 
    { "" }
1156
 
    { editor empty$
1157
 
        { "in " booktitle * }
1158
 
        { "in " booktitle * ", " * format.ineditors * }
1159
 
      if$
1160
 
    }
1161
 
  if$
1162
 
}
1163
 
 
1164
 
FUNCTION {empty.misc.check}
1165
 
{ author empty$ title empty$ howpublished empty$
1166
 
  month empty$ year empty$ note empty$
1167
 
  and and and and and
1168
 
  key empty$ not and
1169
 
    { "all relevant fields are empty in " cite$ * warning$ }
1170
 
    'skip$
1171
 
  if$
1172
 
}
1173
 
 
1174
 
FUNCTION {format.thesis.type}
1175
 
{ type empty$
1176
 
    'skip$
1177
 
    { pop$
1178
 
      type "l" change.case$
1179
 
    }
1180
 
  if$
1181
 
}
1182
 
 
1183
 
FUNCTION {format.tr.number}
1184
 
{ type empty$
1185
 
    { "Tech. Rep." }
1186
 
    'type
1187
 
  if$
1188
 
  number empty$
1189
 
    { "l" change.case$ }
1190
 
    { number tie.or.space.connect }
1191
 
  if$
1192
 
}
1193
 
 
1194
 
FUNCTION {format.article.crossref}
1195
 
{ key empty$
1196
 
    { journal empty$
1197
 
        { "need key or journal for " cite$ * " to crossref " * crossref *
1198
 
          warning$
1199
 
          ""
1200
 
        }
1201
 
        { "in " journal * }
1202
 
      if$
1203
 
    }
1204
 
    { "in " key * }
1205
 
  if$
1206
 
  " \cite{" * crossref * "}" *
1207
 
}
1208
 
 
1209
 
FUNCTION {format.crossref.editor}
1210
 
{ editor #1 "{vv~}{ll}" format.name$
1211
 
  editor num.names$ duplicate$
1212
 
  #2 >
1213
 
    { pop$ " et~al." * }
1214
 
    { #2 <
1215
 
        'skip$
1216
 
        { editor #2 "{ff }{vv }{ll}{ jj}" format.name$ "others" =
1217
 
            { " et~al." * }
1218
 
            { " and " * editor #2 "{vv~}{ll}" format.name$ * }
1219
 
          if$
1220
 
        }
1221
 
      if$
1222
 
    }
1223
 
  if$
1224
 
}
1225
 
 
1226
 
FUNCTION {format.book.crossref}
1227
 
{ volume empty$
1228
 
    { "empty volume in " cite$ * "'s crossref of " * crossref * warning$
1229
 
      "in "
1230
 
    }
1231
 
    { "vol.~" volume *
1232
 
      " of " *
1233
 
    }
1234
 
  if$
1235
 
  editor empty$
1236
 
  editor field.or.null author field.or.null =
1237
 
  or
1238
 
    { key empty$
1239
 
        { series empty$
1240
 
            { "need editor, key, or series for " cite$ * " to crossref " *
1241
 
              crossref * warning$
1242
 
              "" *
1243
 
            }
1244
 
            { series * }
1245
 
          if$
1246
 
        }
1247
 
        { key * }
1248
 
      if$
1249
 
    }
1250
 
    { format.crossref.editor * }
1251
 
  if$
1252
 
  " \cite{" * crossref * "}" *
1253
 
}
1254
 
 
1255
 
FUNCTION {format.incoll.inproc.crossref}
1256
 
{ editor empty$
1257
 
  editor field.or.null author field.or.null =
1258
 
  or
1259
 
    { key empty$
1260
 
        { booktitle empty$
1261
 
            { "need editor, key, or booktitle for " cite$ * " to crossref " *
1262
 
              crossref * warning$
1263
 
              ""
1264
 
            }
1265
 
            { "in " booktitle * }
1266
 
          if$
1267
 
        }
1268
 
        { "in " key * }
1269
 
      if$
1270
 
    }
1271
 
    { "in " format.crossref.editor * }
1272
 
  if$
1273
 
  " \cite{" * crossref * "}" *
1274
 
}
1275
 
 
1276
 
FUNCTION {article}
1277
 
{ output.bibitem
1278
 
  format.authors "author" output.check
1279
 
  format.title "title" output.check
1280
 
  crossref missing$
1281
 
    { journal "journal" output.check
1282
 
      format.vol.year output
1283
 
    }
1284
 
    { format.article.crossref output.nonnull }
1285
 
  if$
1286
 
  format.pages output
1287
 
  new.block
1288
 
  note output
1289
 
  fin.entry
1290
 
}
1291
 
 
1292
 
FUNCTION {book}
1293
 
{ output.bibitem
1294
 
  author empty$
1295
 
    { format.editors "author and editor" output.check }
1296
 
    { format.authors output.nonnull
1297
 
      crossref missing$
1298
 
        { "author and editor" editor either.or.check }
1299
 
        'skip$
1300
 
      if$
1301
 
    }
1302
 
  if$
1303
 
  format.btitle "title" output.check
1304
 
  crossref missing$
1305
 
    { format.bvolume output
1306
 
      format.number.series output
1307
 
      publisher "publisher" output.check
1308
 
      address output
1309
 
    }
1310
 
    { format.book.crossref output.nonnull }
1311
 
  if$
1312
 
  format.edition output
1313
 
  format.date "year" output.check
1314
 
  new.block
1315
 
  note output
1316
 
  fin.entry
1317
 
}
1318
 
 
1319
 
FUNCTION {booklet}
1320
 
{ output.bibitem
1321
 
  format.authors output
1322
 
  format.title "title" output.check
1323
 
  howpublished new.block.checka
1324
 
  howpublished output
1325
 
  address output
1326
 
  format.date output
1327
 
  new.block
1328
 
  note output
1329
 
  fin.entry
1330
 
}
1331
 
 
1332
 
FUNCTION {inbook}
1333
 
{ output.bibitem
1334
 
  author empty$
1335
 
    { format.editors "author and editor" output.check }
1336
 
    { format.authors output.nonnull
1337
 
      crossref missing$
1338
 
        { "author and editor" editor either.or.check }
1339
 
        'skip$
1340
 
      if$
1341
 
    }
1342
 
  if$
1343
 
  format.btitle "title" output.check
1344
 
  crossref missing$
1345
 
    { format.bvolume output
1346
 
      format.number.series output
1347
 
      publisher "publisher" output.check
1348
 
      address output
1349
 
    }
1350
 
    { format.book.crossref output.nonnull }
1351
 
  if$
1352
 
  format.edition output
1353
 
  format.date "year" output.check
1354
 
  format.chapter.pages "chapter and pages" output.check
1355
 
  new.block
1356
 
  note output
1357
 
  fin.entry
1358
 
}
1359
 
 
1360
 
FUNCTION {incollection}
1361
 
{ output.bibitem
1362
 
  format.authors "author" output.check
1363
 
  format.title "title" output.check
1364
 
  crossref missing$
1365
 
    { format.in.ed.booktitle "booktitle" output.check
1366
 
      format.bvolume output
1367
 
      format.number.series output
1368
 
      publisher "publisher" output.check
1369
 
      address output
1370
 
      format.edition output
1371
 
      format.date "year" output.check
1372
 
    }
1373
 
    { format.incoll.inproc.crossref output.nonnull }
1374
 
  if$
1375
 
  format.chapter.pages output
1376
 
  new.block
1377
 
  note output
1378
 
  fin.entry
1379
 
}
1380
 
 
1381
 
FUNCTION {inproceedings}
1382
 
{ output.bibitem
1383
 
  format.authors "author" output.check
1384
 
  format.title "title" output.check
1385
 
  crossref missing$
1386
 
    { format.in.ed.booktitle "booktitle" output.check
1387
 
      format.bvolume output
1388
 
      format.number.series output
1389
 
      address empty$
1390
 
        { organization output
1391
 
          publisher output
1392
 
          format.date "year" output.check
1393
 
        }
1394
 
        { address output.nonnull
1395
 
          format.date "year" output.check
1396
 
          organization output
1397
 
          publisher output
1398
 
        }
1399
 
      if$
1400
 
    }
1401
 
    { format.incoll.inproc.crossref output.nonnull }
1402
 
  if$
1403
 
  format.pages output
1404
 
  new.block
1405
 
  note output
1406
 
  fin.entry
1407
 
}
1408
 
 
1409
 
FUNCTION {conference} { inproceedings }
1410
 
 
1411
 
FUNCTION {manual}
1412
 
{ output.bibitem
1413
 
  author empty$
1414
 
    { format.organization output }
1415
 
    { format.authors output.nonnull }
1416
 
  if$
1417
 
  format.btitle "title" output.check
1418
 
  author empty$
1419
 
    'skip$
1420
 
    { organization output }
1421
 
  if$
1422
 
  address output
1423
 
  format.edition output
1424
 
  format.date output
1425
 
  new.block
1426
 
  note output
1427
 
  fin.entry
1428
 
}
1429
 
 
1430
 
FUNCTION {mastersthesis}
1431
 
{ output.bibitem
1432
 
  format.authors "author" output.check
1433
 
  format.title "title" output.check
1434
 
  "Master's thesis" format.thesis.type output.nonnull
1435
 
  school "school" output.check
1436
 
  address output
1437
 
  format.date "year" output.check
1438
 
  new.block
1439
 
  note output
1440
 
  fin.entry
1441
 
}
1442
 
 
1443
 
FUNCTION {misc}
1444
 
{ output.bibitem
1445
 
  format.authors output
1446
 
  format.title output
1447
 
  howpublished new.block.checka
1448
 
  howpublished output
1449
 
  format.date output
1450
 
  new.block
1451
 
  note output
1452
 
  fin.entry
1453
 
  empty.misc.check
1454
 
}
1455
 
 
1456
 
FUNCTION {phdthesis}
1457
 
{ output.bibitem
1458
 
  format.authors "author" output.check
1459
 
  format.btitle "title" output.check
1460
 
  "PhD thesis" format.thesis.type output.nonnull
1461
 
  school "school" output.check
1462
 
  address output
1463
 
  format.date "year" output.check
1464
 
  new.block
1465
 
  note output
1466
 
  fin.entry
1467
 
}
1468
 
 
1469
 
FUNCTION {proceedings}
1470
 
{ output.bibitem
1471
 
  editor empty$
1472
 
    { format.organization output }
1473
 
    { format.editors output.nonnull }
1474
 
  if$
1475
 
  format.btitle "title" output.check
1476
 
  format.bvolume output
1477
 
  format.number.series output
1478
 
  address empty$
1479
 
    { editor empty$
1480
 
        'skip$
1481
 
        { organization output }
1482
 
      if$
1483
 
      publisher output
1484
 
      format.date "year" output.check
1485
 
    }
1486
 
    { address output.nonnull
1487
 
      format.date "year" output.check
1488
 
      editor empty$
1489
 
        'skip$
1490
 
        { organization output }
1491
 
      if$
1492
 
      publisher output
1493
 
    }
1494
 
  if$
1495
 
  new.block
1496
 
  note output
1497
 
  fin.entry
1498
 
}
1499
 
 
1500
 
FUNCTION {techreport}
1501
 
{ output.bibitem
1502
 
  format.authors "author" output.check
1503
 
  format.title "title" output.check
1504
 
  format.tr.number output.nonnull
1505
 
  institution "institution" output.check
1506
 
  address output
1507
 
  format.date "year" output.check
1508
 
  new.block
1509
 
  note output
1510
 
  fin.entry
1511
 
}
1512
 
 
1513
 
FUNCTION {unpublished}
1514
 
{ output.bibitem
1515
 
  format.authors "author" output.check
1516
 
  format.title "title" output.check
1517
 
  new.block
1518
 
  note "note" output.check
1519
 
  format.date output
1520
 
  fin.entry
1521
 
}
1522
 
 
1523
 
FUNCTION {default.type} { misc }
1524
 
 
1525
 
MACRO {jan} {"Jan."}
1526
 
 
1527
 
MACRO {feb} {"Feb."}
1528
 
 
1529
 
MACRO {mar} {"Mar."}
1530
 
 
1531
 
MACRO {apr} {"Apr."}
1532
 
 
1533
 
MACRO {may} {"May"}
1534
 
 
1535
 
MACRO {jun} {"June"}
1536
 
 
1537
 
MACRO {jul} {"July"}
1538
 
 
1539
 
MACRO {aug} {"Aug."}
1540
 
 
1541
 
MACRO {sep} {"Sept."}
1542
 
 
1543
 
MACRO {oct} {"Oct."}
1544
 
 
1545
 
MACRO {nov} {"Nov."}
1546
 
 
1547
 
MACRO {dec} {"Dec."}
1548
 
 
1549
 
MACRO {acmcs} {"ACM Comput. Surveys"}
1550
 
 
1551
 
MACRO {acta} {"Acta Inf."}
1552
 
 
1553
 
MACRO {cacm} {"Comm. ACM"}
1554
 
 
1555
 
MACRO {ibmjrd} {"IBM J. Res. Dev."}
1556
 
 
1557
 
MACRO {ibmsj} {"IBM Syst.~J."}
1558
 
 
1559
 
MACRO {ieeese} {"IEEE Trans. Softw. Eng."}
1560
 
 
1561
 
MACRO {ieeetc} {"IEEE Trans. Comput."}
1562
 
 
1563
 
MACRO {ieeetcad}
1564
 
 {"IEEE Trans. Comput.-Aided Design Integrated Circuits"}
1565
 
 
1566
 
MACRO {ipl} {"Inf. Process. Lett."}
1567
 
 
1568
 
MACRO {jacm} {"J.~Assoc. Comput. Mach."}
1569
 
 
1570
 
MACRO {jcss} {"J.~Comput. System Sci."}
1571
 
 
1572
 
MACRO {scp} {"Sci. Comput. Programming"}
1573
 
 
1574
 
MACRO {sicomp} {"SIAM J. Comput."}
1575
 
 
1576
 
MACRO {tocs} {"ACM Trans. Comput. Syst."}
1577
 
 
1578
 
MACRO {tods} {"ACM Trans. Database Syst."}
1579
 
 
1580
 
MACRO {tog} {"ACM Trans. Gr."}
1581
 
 
1582
 
MACRO {toms} {"ACM Trans. Math. Softw."}
1583
 
 
1584
 
MACRO {toois} {"ACM Trans. Office Inf. Syst."}
1585
 
 
1586
 
MACRO {toplas} {"ACM Trans. Prog. Lang. Syst."}
1587
 
 
1588
 
MACRO {tcs} {"Theoretical Comput. Sci."}
1589
 
 
1590
 
READ
1591
 
 
1592
 
FUNCTION {sortify}
1593
 
{ purify$
1594
 
  "l" change.case$
1595
 
}
1596
 
 
1597
 
INTEGERS { len }
1598
 
 
1599
 
FUNCTION {chop.word}
1600
 
{ 's :=
1601
 
  'len :=
1602
 
  s #1 len substring$ =
1603
 
    { s len #1 + global.max$ substring$ }
1604
 
    's
1605
 
  if$
1606
 
}
1607
 
 
1608
 
FUNCTION {sort.format.names}
1609
 
{ 's :=
1610
 
  #1 'nameptr :=
1611
 
  ""
1612
 
  s num.names$ 'numnames :=
1613
 
  numnames 'namesleft :=
1614
 
    { namesleft #0 > }
1615
 
    { nameptr #1 >
1616
 
        { "   " * }
1617
 
        'skip$
1618
 
      if$
1619
 
      s nameptr "{vv{ } }{ll{ }}{  f{ }}{  jj{ }}" format.name$ 't :=
1620
 
      nameptr numnames = t "others" = and
1621
 
        { "et al" * }
1622
 
        { t sortify * }
1623
 
      if$
1624
 
      nameptr #1 + 'nameptr :=
1625
 
      namesleft #1 - 'namesleft :=
1626
 
    }
1627
 
  while$
1628
 
}
1629
 
 
1630
 
FUNCTION {sort.format.title}
1631
 
{ 't :=
1632
 
  "A " #2
1633
 
    "An " #3
1634
 
      "The " #4 t chop.word
1635
 
    chop.word
1636
 
  chop.word
1637
 
  sortify
1638
 
  #1 global.max$ substring$
1639
 
}
1640
 
 
1641
 
FUNCTION {author.sort}
1642
 
{ author empty$
1643
 
    { key empty$
1644
 
        { "to sort, need author or key in " cite$ * warning$
1645
 
          ""
1646
 
        }
1647
 
        { key sortify }
1648
 
      if$
1649
 
    }
1650
 
    { author sort.format.names }
1651
 
  if$
1652
 
}
1653
 
 
1654
 
FUNCTION {author.editor.sort}
1655
 
{ author empty$
1656
 
    { editor empty$
1657
 
        { key empty$
1658
 
            { "to sort, need author, editor, or key in " cite$ * warning$
1659
 
              ""
1660
 
            }
1661
 
            { key sortify }
1662
 
          if$
1663
 
        }
1664
 
        { editor sort.format.names }
1665
 
      if$
1666
 
    }
1667
 
    { author sort.format.names }
1668
 
  if$
1669
 
}
1670
 
 
1671
 
FUNCTION {author.organization.sort}
1672
 
{ author empty$
1673
 
    { organization empty$
1674
 
        { key empty$
1675
 
            { "to sort, need author, organization, or key in " cite$ * warning$
1676
 
              ""
1677
 
            }
1678
 
            { key sortify }
1679
 
          if$
1680
 
        }
1681
 
        { "The " #4 organization chop.word sortify }
1682
 
      if$
1683
 
    }
1684
 
    { author sort.format.names }
1685
 
  if$
1686
 
}
1687
 
 
1688
 
FUNCTION {editor.organization.sort}
1689
 
{ editor empty$
1690
 
    { organization empty$
1691
 
        { key empty$
1692
 
            { "to sort, need editor, organization, or key in " cite$ * warning$
1693
 
              ""
1694
 
            }
1695
 
            { key sortify }
1696
 
          if$
1697
 
        }
1698
 
        { "The " #4 organization chop.word sortify }
1699
 
      if$
1700
 
    }
1701
 
    { editor sort.format.names }
1702
 
  if$
1703
 
}
1704
 
 
1705
 
FUNCTION {presort}
1706
 
{ type$ "book" =
1707
 
  type$ "inbook" =
1708
 
  or
1709
 
    'author.editor.sort
1710
 
    { type$ "proceedings" =
1711
 
        'editor.organization.sort
1712
 
        { type$ "manual" =
1713
 
            'author.organization.sort
1714
 
            'author.sort
1715
 
          if$
1716
 
        }
1717
 
      if$
1718
 
    }
1719
 
  if$
1720
 
  "    "
1721
 
  *
1722
 
  year field.or.null sortify
1723
 
  *
1724
 
  "    "
1725
 
  *
1726
 
  title field.or.null
1727
 
  sort.format.title
1728
 
  *
1729
 
  #1 entry.max$ substring$
1730
 
  'sort.key$ :=
1731
 
}
1732
 
 
1733
 
ITERATE {presort}
1734
 
 
1735
 
SORT
1736
 
 
1737
 
STRINGS { longest.label }
1738
 
 
1739
 
INTEGERS { number.label longest.label.width }
1740
 
 
1741
 
FUNCTION {initialize.longest.label}
1742
 
{ "" 'longest.label :=
1743
 
  #1 'number.label :=
1744
 
  #0 'longest.label.width :=
1745
 
}
1746
 
 
1747
 
FUNCTION {longest.label.pass}
1748
 
{ number.label int.to.str$ 'label :=
1749
 
  number.label #1 + 'number.label :=
1750
 
  label width$ longest.label.width >
1751
 
    { label 'longest.label :=
1752
 
      label width$ 'longest.label.width :=
1753
 
    }
1754
 
    'skip$
1755
 
  if$
1756
 
}
1757
 
 
1758
 
EXECUTE {initialize.longest.label}
1759
 
 
1760
 
ITERATE {longest.label.pass}
1761
 
 
1762
 
FUNCTION {begin.bib}
1763
 
{ preamble$ empty$
1764
 
    'skip$
1765
 
    { preamble$ write$ newline$ }
1766
 
  if$
1767
 
  "\begin{thebibliography}{"  longest.label  * "}" * write$ newline$
1768
 
}
1769
 
 
1770
 
EXECUTE {begin.bib}
1771
 
 
1772
 
EXECUTE {init.state.consts}
1773
 
 
1774
 
EXECUTE {init.last.authors}
1775
 
 
1776
 
ITERATE {call.type$}
1777
 
 
1778
 
FUNCTION {end.bib}
1779
 
{ newline$
1780
 
  "\end{thebibliography}" write$ newline$
1781
 
}
1782
 
 
1783
 
EXECUTE {end.bib}
1784