%%%%%%%%%%%%%%%%%%%%%%%%%%  ltexpprt_doublecolumn.tex  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% This is ltexpprt_twocolumn.tex, an example file for use with the SIAM LaTeX2E
% Preprint Series macros. It is designed to provide two-column output.
% Please take the time to read the following comments, 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:
%
%                 Donna Witzleben
%                 SIAM
%                 3600 University City Science Center
%                 Philadelphia, PA 19104-2688
%                 USA
%                 Telephone: (215) 382-9800
%                 Fax: (215) 386-7999
%                 e-mail: witzleben@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. There are no new tags.  Existing LaTeX tags have been formatted to match
%%     the Preprint series style.
%%
%%  2. Do not change the margins or page size!  Do not change from the default
%%     text font!
%%
%%  3. You must use \cite in the text to mark your reference citations and
%%     \bibitem in the listing of references at the end of your chapter. See
%%     the examples in the following file. If you are using BibTeX, please
%%     supply the bst file with the manuscript file.
%%
%%  4. This macro is set up for two levels of headings (\section and
%%     \subsection). The macro will automatically number the headings for you.
%%
%%  5. No running heads are to be used for this volume.
%%
%%  6. Theorems, Lemmas, Definitions, Equations, etc. are to be double numbered,
%%     indicating the section and the occurrence of that element
%%     within that section. (For example, the first theorem in the second
%%     section would be numbered 2.1. The macro will
%%     automatically do the numbering for you.
%%
%%  7. Figures and Tables must be single-numbered.
%%     Use existing LaTeX tags for these elements.
%%     Numbering will be done automatically.
%%
%%  8. Page numbering is no longer included in this macro.
%%     Pagination will be set by the program committee.
%%
%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%% IMR 2027 SUBMISSION INSTRUCTIONS %%%%%%%%%%%%%%%%%%%%%%%
%%  1. Full papers are limited to 12 pages in length (US letter size),
%%     excluding references, and including figures, tables, and appendices. The
%%     paper must be submitted in PDF format.
%%  2. Do not include author names or affiliations in the initial submission.
%%     The review process is double-blind so avoid using terminology that might
%%     reveal your identity.
%%  3. Authors are welcome to submit supplementary material (e.g., code,
%%     datasets, animations, etc.) to the actual paper or research note.
%%     The paper or note must be complete even without the supplementary
%%     material. Note that the supplementary material must
%%     maintain the anonymity of the submission.
%%  4. OpenConf only keeps the last uploaded file so if you have supplementary
%%     material, zip it with the paper and upload that.
%%
%%     Please review https://www.internationalmeshingroundtable.com/imr35/call-for-papers/
%%     carefully to make sure your submission meets all the requirements.


\documentclass[twoside,leqno,twocolumn]{article}

\usepackage[letterpaper]{geometry}

\usepackage{ltexpprt}
% defines environments algorithm, theorem, proof
% defines newtheorems: lemma, fact, corollary, Axiom, cond (Condition), property, proposition, Conjecture, Definition, Lemma, Remark, Example, Method, Exercise

\usepackage{hyperref}

% https://www.siam.org/Portals/0/Macros/Online/docsiamonline.pdf
% SIAM journals currently encourage the use of \cref{myfig} and \cref{mysection} instead of e.g. Fig.~\ref{myfig}, \S 1.2 (for section 1.2)
% use \Cref{myref} to capitalize the first letter at the start of sentences
% Note: direct \ref references and other examples of poor style have been modified by Scott A. Mitchell for the IMR Template
\usepackage{cleveref}

%% pseudocode:
%% ltexpprt defines "algorithm" so don't \usepackage{algorithm} to overwrite it. SIAM wants it the way it is, inline and numbered like a theorem or definition, not floating figure-like.
%% Use one of the following four options
%   \usepackage[algo2e]{algorithm2e}   % algo2e parameter avoids name clash with "algorithm" from ltexpprt
%.   \usepackage{algorithmic}
%    \usepackage{algorithmicx} % with algpseudocode
\usepackage{algpseudocode} % with algorithmicx, or by itself

\begin{document}

%
\newcommand\relatedversion{}
\renewcommand\relatedversion{\thanks{The full version of the paper can be accessed at \anon{\protect\url{redacted-url}}{\protect\url{https://arxiv.org/abs/1902.09310}}}} % Replace URL with link to full paper or comment out this line

\title{\Large \anon{Anonymized}{Known-authors} SIAM/ACM Preprint Series Macros for Use With \LaTeX\relatedversion}
\anon{
    \author{Submission ID XYZ}  % replace with actual submission id. Keep things anonymous during the double-blind review.
}
{ % Actual author names go below
    \author{Corey Gray\thanks{Society for Industrial and Applied Mathematics.}
    \and Tricia Manning\thanks{Society for Industrial and Applied Mathematics.}}    
}

\date{}

\maketitle

% Copyright Statement
% When submitting your final paper to a SIAM proceedings, it is requested that you include
% the appropriate copyright in the footer of the paper.  The copyright added should be
% consistent with the copyright selected on the copyright form submitted with the paper.
% Please note that "20XX" should be changed to the year of the meeting.

% Default Copyright Statement
\fancyfoot[R]{\scriptsize{Copyright \textcopyright\ 2027 by SIAM\\
Unauthorized reproduction of this article is prohibited}}

% Depending on which copyright you agree to when you sign the copyright form, the copyright
% can be changed to one of the following after commenting out the default copyright statement
% above.

%\fancyfoot[R]{\scriptsize{Copyright \textcopyright\ 20XX\\
%Copyright for this paper is retained by authors}}

%\fancyfoot[R]{\scriptsize{Copyright \textcopyright\ 20XX\\
%Copyright retained by principal author's organization}}

%\pagenumbering{arabic}
%\setcounter{page}{1}%Leave this line commented out.

\begin{abstract} \small\baselineskip=9pt An abstract is a brief summary of the paper's contributions, written for experts.
\anon{Authors are anonymized for double-blind review.}{It was written by Gray and Manning.}
\end{abstract}


\section{Introduction.}
An introduction is a gentler description and summary of the paper than the abstract, written for non-experts. It describes the paper's concepts, contribution, context and significance.

\subsection{Problem Specification.}
\label{sec:problem}
In this paper, we consider the solution of the $N \times
N$ linear
system
\begin{equation} \label{axb}
A x = b
\end{equation}
where $A$ is large, sparse, symmetric, and positive definite.  We consider
the direct solution of \cref{axb} 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.


\section{Design Considerations.}
\label{sec:design}
Several good ordering algorithms (nested dissection and
minimum degree)
are available for computing $P$~\cite{GEORGELIU,ROSE72}.
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~\cite{BANKSMITH}.
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.

\begin{theorem}\label{thm:extend3d}
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.\end{theorem}

Our purpose here is to examine the nonnumerical complexity of the
sparse elimination algorithm given in~\cite{BANKSMITH}.
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; see Thm.~\ref{thm:extend3d}.
% \cref{thm:extend3d} does not work, give ?? insteand of Thm.
This is accomplished by exploiting the m-tree,
a particular spanning tree for the graph of the filled-in matrix.
Several good ordering algorithms (nested dissection and minimum degree)
are available for computing $P$~\cite{GEORGELIU,ROSE72}.
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$.

\begin{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 in each of the three
independent variables and then ignoring the intermediate
grids; this artifice simplifies coding considerably.
\end{proof}

Our purpose here is to examine the nonnumerical complexity of the
sparse elimination algorithm given in~\cite{BANKSMITH}.
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.

\begin{Definition}{\rm We describe the two methods in \cref{sec:design}. 
In \cref{sec:robust} we discuss some remaining details.}
\end{Definition}

Our purpose here is to examine the nonnumerical complexity of the
sparse elimination algorithm given in  \cite{BANKSMITH}.
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.
Several good ordering algorithms (nested dissection and minimum degree)
are available for computing $P$~\cite{GEORGELIU,ROSE72}.
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~\cite{BANKSMITH}.
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.

\begin{lemma} 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$.
\end{lemma}

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~\cite{LAW,LIU,LIU2,ROSE72,ROSE76,ROSEWHITTEN,SCHREIBER}.
In \cref{sec:robust}, 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~\cite{LAW,LIU,LIU2,ROSE72,ROSE76,ROSEWHITTEN,SCHREIBER}.

In \cref{sec:design}, we review the bordering algorithm, and introduce
the sorting and intersection problems that arise in the
sparse formulation of the algorithm.
In \cref{sec:robust}, 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~\cite{LAW,LIU,LIU2,ROSE72,ROSE76,ROSEWHITTEN,SCHREIBER}.


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~\cite{LAW,LIU,LIU2,ROSE72,ROSE76,ROSEWHITTEN,SCHREIBER}.
In \cref{sec:robust}, 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~\cite{LAW,LIU,LIU2,ROSE72,ROSE76,ROSEWHITTEN,SCHREIBER}.
This is accomplished by exploiting the m-tree,
a particular spanning tree for the graph of the filled-in matrix.
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~\cite{EISENSTAT,GEORGELIU,LAW,LIU,LIU2,ROSE76,SCHREIBER}.


We show a blank figure in \cref{fig:blank}.

\begin{figure}
\vspace{14pc}
\caption{This is a blank figure.}\label{fig:blank}
\end{figure}

\subsection{Robustness.}
\label{sec:robust}
We do not
attempt to present an overview
here, but rather attempt to focus on those results that
are relevant to our particular algorithm; see \cref{fig:blank}.
This section assumes prior knowledge of the role of graph theory
in sparse Gaussian elimination; surveys of this role are
available in~\cite{ROSE72,GEORGELIU}. More general
discussions of elimination trees are given in~\cite{LAW,LIU,LIU2,SCHREIBER}.
Thus, at the $k$th stage, the bordering algorithm consists of
solving the lower triangular system
\begin{equation} \label{1.2}
 L_{k-1}v = c
\end{equation}
and setting
\begin{eqnarray}
\ell &=& D^{-1}_{k-1}v , \\
\delta &=& \alpha - \ell^{t} v .
\end{eqnarray}

\section{Algorithm}

We provide some pseudocode in Algorithm~\ref{alg:deterministicmps}.


\newcommand{\squarecut}{scooped-square}
\newcommand{\True}{\texttt{True}}
\newcommand{\False}{\texttt{False}}

% works with \usepackage{algpseudocode}
\begin{algorithm}[Deterministic-MPS]{maximal Poisson-disk sampling}  \label{alg:deterministicmps}
  \begin{algorithmic} [3]
\Require Rectangular grid $\mathcal{G}$ of whole grid squares
\Require Flag if domain is periodic: \True\ or \False
\Ensure Maximal Poisson-disk sampling of rectangle
    \Function{Deterministic-MPS}{$\mathcal{G}$}
    \State // {Initialize Grid $\mathcal{G}$}
    \For{$g \in \mathcal{G}$}
      \State $g.\textrm{point} = (u,v)$ uniform random in square
      \State $g.\textrm{time} = A e^{-Aw}$, rand $w$, expovariate in area
      \State $g.\textrm{scooped-square}$ = square polygon $g$
    \EndFor
    \State Global pre-pass heuristic
    \State // {Find locally-early squares}
     \For{{$g \in \mathcal{G}$} and {$h \in \textrm{neighbors}(g)$}}
      \State increment \#antecedents of $g$ or $h$ (later)
     \EndFor
     \For{{$g \in \mathcal{G}$}}
       \State EarlySquares.add($g$ if no antecedents)
     \EndFor

    \State // {Accept samples and update}
    \Repeat 
        \State $g=$ EarlySquares.pop()  \Comment{any order}
        \State accept $g.\textrm{point}$ as Poisson-disk sample
         \For{$h \in \textrm{neighbors}(g)$}
           \State decrement h.antecedents 
           \State \Comment{since g no longer blocks h}
           \State // {resample candidates in disk($g.\textrm{point}$)}
	   \If{$h.\textrm{point} \in \textrm{disk}(g.\textrm{point})$}
	   \State $h.\textrm{scooped-square} \mathrel{-}= \textrm{disk}(g.\textrm{point})$ \label{line:scoop}
	   \If{$h.\textrm{\squarecut}$ is empty}
	     \State $h.\textrm{time} = \infty$
	   \Else
  	     \State trim chocks of $h.\textrm{\squarecut}$  \label{line:trim}
	     \State triangulate remaining polygon  \label{line:triangulate}
	     \State $U \in \{ \textrm{chocks, triangles} \}$ by area  \label{line:sampleregion}
	     \State $h.\textrm{point} \in U$ uniform by area \label{line:samplepoint}
	     \State $h.\textrm{time}\, \mathrel{+}= $ expovar( A($h.\textrm{\squarecut}$) )
	   \EndIf
           \For{$s \in \textrm{neighbors}(h)$}
             \If{$h$ is later than $s$, but was earlier}
             \State increment h.antecedents
             \State decrement $s$.antecedents
             \If $s$ has no antecedents
             \State EarlySquares.add( $s$)
             \EndIf
             \EndIf
            \EndFor
          \EndIf
          \If $h$ has no antecedents
          \State EarlySquares.add( $h$ )
          \EndIf
        \EndFor
    \Until EarlySquares == empty
    
    \EndFunction
  \end{algorithmic}
\end{algorithm}


\section{Results.} We do not
attempt to present an overview
here, but rather attempt to focus on those results that
are relevant to our particular algorithm, Algorithm~\ref{alg:deterministicmps}.

\subsection{Versatility.}The special
structure of this problem allows us to make exact estimates of
the 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~\cite{GEORGELIU,ROSEWHITTEN}.  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~\cite{LAW,LIU,LIU2,ROSE72,ROSE76,ROSEWHITTEN,SCHREIBER}.
In \cref{sec:robust}, 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
\cite{LAW,LIU,LIU2,ROSE72,ROSE76,ROSEWHITTEN,SCHREIBER}.

In \cref{sec:design}, we review the bordering algorithm, and introduce
the sorting and intersection problems that arise in the
sparse formulation of the algorithm.
In \cref{sec:robust}, 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~\cite{LAW,LIU,LIU2,ROSE72,ROSE76,ROSEWHITTEN,SCHREIBER}.


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~\cite{LAW,LIU,LIU2,ROSE72,ROSE76,ROSEWHITTEN,SCHREIBER}.
In \cref{sec:robust}, 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. 

\section*{Acknowledgements}
\anon
{Redacted for anonymity.} %Leave as-is
{ %Actual acknowledgement goes here.
I thank Thouis Ray Jones for suggesting this problem to me in 2012, and my institution for funding me.

 {\tiny
My institution requires this disclaimer on all my publications, even though it handicaps its employees by preventing the author from making full use of the proceedings page limit. This technical article contains objective information and does not necessarily represent the subjective opinions of my institution. The authors are not authorized to communicate the policy of the institution. That said, my institution does not necessarily represent my views nor speak for me.\par
 }
}

% if using BibTex
\bibliographystyle{siam}
\bibliography{ltexpprt_references}
% else
%\begin{thebibliography}{99}
%
%%1
%\bibitem{BANKSMITH}
%R.~E. Bank and R.~K. Smith, {\em General sparse elimination requires no
%  permanent integer storage}, SIAM J. Sci. Stat. Comput., 8 (1987),
%  pp.~574--584.
%
%%2
%\bibitem{EISENSTAT}
%S.~C. Eisenstat, M.~C. Gursky, M.~Schultz, and A.~Sherman, {\em
%  Algorithms and data structures for sparse symmetric Gaussian elimination},
%  SIAM J. Sci. Stat. Comput., 2 (1982), pp.~225--237.
%
%%3
%\bibitem{GEORGELIU}
%A.~George and J.~Liu, {\em Computer Solution of Large Sparse Positive
%  Definite Systems}, Prentice Hall, Englewood Cliffs, NJ, 1981.
%
%%4
%\bibitem{LAW}
%K.~H. Law and S.~J. Fenves, {\em A node addition model for symbolic
%  factorization}, ACM TOMS, 12 (1986), pp.~37--50.
%
%%5
%\bibitem{LIU}
%J.~W.~H. Liu, {\em A compact row storage scheme for Cholesky factors
%  using elimination trees}, ACM TOMS, 12 (1986), pp.~127--148.
%
%%6
%\bibitem{LIU2}
%\sameauthor , {\em The role of
%  elimination trees in sparse factorization}, Tech. Report CS-87-12,
%  Department of Computer Science, York University, Ontario, Canada, 1987.
%
%%7
%\bibitem{ROSE72}
%D.~J. Rose, {\em A graph theoretic study of the numeric solution of
%  sparse positive definite systems}, in Graph Theory and Computing, Academic  Press, New
%York, 1972.
%
%%8
%\bibitem{ROSE76}
%D.~J. Rose, R.~E. Tarjan, and G.~S. Lueker, {\em Algorithmic aspects of
%  vertex elimination on graphs}, SIAM J. Comput., 5 (1976), pp.~226--283.
%
%%9
%\bibitem{ROSEWHITTEN}
%D.~J. Rose and G.~F. Whitten, {\em A recursive analysis of disection
%  strategies}, in Sparse Matrix Computations, Academic Press, New York, 1976.
%
%%10
%\bibitem{SCHREIBER}
%R.~Schrieber, {\em A new implementation of sparse Gaussian elimination},
%  ACM TOMS, 8 (1982), pp.~256--276.
%
%\end{thebibliography}

\end{document}

% End of ltexpprt.tex 
