@article{constantine2010-rapr,
author = {Paul G. Constantine and David F. Gleich},
title = {Random Alpha {PageRank}},
journal = {Internet Mathematics},
year = {2010},
volume = {6},
pages = {189--236},
number = {2},
month = {September},
abstract = {We suggest a revision to the PageRank random surfer model that considers
the influence of a population of random surfers on the PageRank vector.
In the revised model, each member of the population has its own teleportation
parameter chosen from a probability distribution, and consequently,
the ranking vector is random. We propose three algorithms for computing
the statistics of the random ranking vector based respectively on
(i) random sampling, (ii) paths along the links of the underlying
graph, and (iii) quadrature formulas. We find that the expectation
of the random ranking vector produces similar rankings to its deterministic
analogue, but the standard deviation gives uncorrelated information
(under a Kendall-tau metric) with myriad potential uses. We examine
applications of this model to web spam.},
doi = {10.1080/15427951.2009.10129185},
file = {:constantine 2010 - random alpha pagerank.pdf},
keywords = {self},
owner = {David Gleich},
timestamp = {2010.01.07},
url = {http://projecteuclid.org/DPubS?service=UI&version=1.0&verb=Display&handle=euclid.im/1285339073}
}
@article{Constantine-2011-gni,
author = {Paul G. Constantine and David F. Gleich and Gianluca Iaccarino},
title = {A factorization of the spectral {Galerkin} system for parameterized
matrix equations: derivation and applications},
journal = {SIAM Journal of Scientific Computing},
year = {2011},
volume = {33},
pages = {2995--3009},
number = {5},
abstract = {Recent work has explored solver strategies for the linear system of
equations arising from a spectral Galerkin approximation of the solution
of PDEs with parameterized (or stochastic) inputs. We consider the
related problem of a matrix equation whose matrix and right-hand
side depend on a set of parameters (e.g., a PDE with stochastic inputs
semidiscretized in space) and examine the linear system arising from
a similar Galerkin approximation of the solution. We derive a useful
factorization of this system of equations, which yields bounds on
the eigenvalues, clues to preconditioning, and a flexible implementation
method for a wide array of problems. We complement this analysis
with (i) a numerical study of preconditioners on a standard elliptic
PDE test problem and (ii) a fluids application using existing CFD
codes; the MATLAB codes used in the numerical studies are available
online.},
doi = {10.1137/100799046},
file = {:Constantine 2011 - spectral galerkin.pdf},
keywords = {self},
owner = {David F. Gleich},
timestamp = {2010.09.15}
}
@article{constantine2010-parameterized,
author = {Paul G. Constantine and David F. Gleich and Gianluca Iaccarino},
title = {Spectral Methods for Parameterized Matrix Equations},
journal = {SIAM Journal on Matrix Analysis and Applications},
year = {2010},
volume = {31},
pages = {2681-2699},
number = {5},
abstract = {We apply polynomial approximation methods—known in the numerical PDEs
context as spectral methods—to approximate the vector-valued function
that satisfies a linear system of equations where the matrix and
the right-hand side depend on a parameter. We derive both an interpolatory
pseudospectral method and a residual-minimizing Galerkin method,
and we show how each can be interpreted as solving a truncated infinite
system of equations; the difference between the two methods lies
in where the truncation occurs. Using classical theory, we derive
asymptotic error estimates related to the region of analyticity of
the solution, and we present a practical residual error estimate.
We verify the results with two numerical examples.},
doi = {10.1137/090755965},
file = {:constantine 2010 - parameterized matrix equations.pdf},
keywords = {parameterized systems; spectral methods; self},
owner = {David F. Gleich},
publisher = {SIAM},
timestamp = {2010.09.24}
}
@article{gleich2010-inner-outer,
author = {David F. Gleich and Andrew P. Gray and Chen Greif and Tracy Lau},
title = {An inner-outer iteration for {PageRank}},
journal = {SIAM Journal of Scientific Computing},
year = {2010},
volume = {32},
pages = {349--371},
number = {1},
month = {February},
abstract = {We present a new iterative scheme for PageRank computation. The algorithm
is applied to the linear system formulation of the problem, using
inner-outer stationary iterations. It is simple, can be easily implemented
and parallelized, and requires minimal storage overhead. Our convergence
analysis shows that the algorithm is effective for a crude inner
tolerance and is not sensitive to the choice of the parameters involved.
The same idea can be used as a preconditioning technique for nonstationary
schemes. Numerical examples featuring matrices of dimensions exceeding
100,000,000 in sequential and parallel environments demonstrate the
merits of our technique. Our code is available online for viewing
and testing, along with several large scale examples.},
doi = {10.1137/080727397},
file = {:gleich 2010 - inner-outer pagerank.pdf},
keywords = {self},
owner = {David F. Gleich},
timestamp = {2009.07.10}
}
@article{gleich2007-approximate,
author = {David F. Gleich and Marzia Polito},
title = {Approximating Personalized {PageRank} with Minimal Use of Webgraph
Data},
journal = {Internet Mathematics},
year = {2007},
volume = {3},
pages = {257--294},
number = {3},
month = {December},
abstract = {In this paper, we consider the problem of calculating fast and accurate
approximations to the personalized PageRank score of a webpage. We
focus on techniques to improve speed by limiting the amount of web
graph data we need to access.
Our algorithms provide both the approximation to the personalized
PageRank score as well as guidance in using only the necessary information—and
therefore sensibly reduce not only the computational cost of the
algorithm but also the memory and memory bandwidth requirements.
We report experiments with these algorithms on web graphs of up to
118 million pages and prove a theoretical approximation bound for
all. Finally, we propose a local, personalized web-search system
for a future client system using our algorithms.},
doi = {10.1080/15427951.2006.10129128},
file = {:gleich 2007 - approximate personalized pagerank.pdf},
key = {GP2007},
keywords = {pagerank, self},
owner = {David Gleich},
timestamp = {2006.11.27}
}
@article{Gleich-2011-cads,
author = {Gleich, David F. and Wang, Ying and Meng, Xiangrui and Ronaghi, Farnaz
and Gerritsen, Margot and Saberi, Amin},
title = {Some computational tools for digital archive and metadata maintenance},
journal = {BIT Numerical Mathematics},
year = {2011},
volume = {51},
pages = {127-154},
abstract = {Computational tools are a mainstay of current search and recommendation
technology. But modern digital archives are astonishingly diverse
collections of older digitized material and newer born digital content.
Finding interesting material in these archives is still challenging.
The material often lacks appropriate annotation---or metadata---so
that people can find the most interesting material. We describe four
computational tools we developed to aid in the processing and maintenance
of large digital archives. The first is an improvement to a graph
layout algorithm for graphs with hundreds of thousands of nodes.
The second is a new algorithm for matching databases with links among
the objects, also known as a network alignment problem. The third
is an optimization heuristic to disambiguate a set of geographic
references in a book. And the fourth is a technique to automatically
generate a title from a description.},
affiliation = {Sandia National Laboratories, Livermore, CA 94550, USA},
doi = {10.1007/s10543-011-0324-6},
file = {:gleich 2011 - comptuational tools.pdf},
issn = {0006-3835},
issue = {1},
keyword = {Mathematics and Statistics},
keywords = {self},
owner = {David F. Gleich},
publisher = {Springer Netherlands},
timestamp = {2011.03.25}
}
@article{wang2008-monte-carlo-for-adjoint,
author = {Qiqi Wang and David F. Gleich and Amin Saberi and Nasrollah Etemadi
and Parviz Moin},
title = {A {Monte Carlo} method for solving unsteady adjoint equations},
journal = {Journal of Computational Physics},
year = {2008},
volume = {227},
pages = {6184--6205},
number = {12},
month = {June},
abstract = {Traditionally, solving the adjoint equation for unsteady problems
involves solving a large, structured linear system. This paper presents
a variation on this technique and uses a Monte Carlo linear solver.
The Monte Carlo solver yields a forward-time algorithm for solving
unsteady adjoint equations. When applied to computing the adjoint
associated with Burgers� equation, the Monte Carlo approach is
faster for a large class of problems while preserving sufficient
accuracy.},
address = {San Diego, CA, USA},
doi = {10.1016/j.jcp.2008.03.006},
file = {:wang 2008 - monte carlo adjoint.pdf},
issn = {0021-9991},
keywords = {self},
owner = {David Gleich},
publisher = {Academic Press Professional, Inc.},
timestamp = {2008.10.18}
}