CV
Research Interests
 Applied numerical linear algebra
 Scientific computing
 Highperformance computing
 Spectral network analysis methods
 Optimization via surrogate models
 Finite element analysis
 Computational tools for electrical power grids
 Simulation tools for microelectromechanical systems (MEMS)
Experience and Education
2017present  Associate Professor of Computer Science  Cornell University 
20092017  Assistant Professor of Computer Science  Cornell University 
20062009  Courant Instructor of Mathematics  New York University 
19992006  Ph.D. in Computer Science  University of California, Berkeley 
19951999  B.S. in Math and Computer Science  University of Maryland, College Park 
Awards
2015  Middleware Best Student Paper 
2015  KDD Best Student Paper 
2015 
SIGEST Featured Paper
Featured paper in SIAM Review from specialist journals on a rotating basis 
2015 
SIAG/LA Prize
Awarded once every three years for the best applied linear algebra journal paper. 
2014 
Douglas Whitney Award
Awarded annually to a Cornell Engineering faculty for teaching excellence. 
2010  Sloan Research Fellowship 
2008 
Alston S. Householder Award
Awarded once every three years for best thesis in numerical linear algebra. 
1999  NSF Graduate Student Fellowship 
Publications
Journal papers

Y. Li, K. Kloster, K. He, D. Bindel, and J. Hopcroft, “Local Spectral Clustering for Overlapping Community Detection,” ACM Transactions on Knowledge Discovery from Data, vol. 12, no. 2, p. 17, 2018.
@article{2018tkdd, author = {Li, Yixuan and Kloster, Kyle and He, Kun and Bindel, David and Hopcroft, John}, title = {Local Spectral Clustering for Overlapping Community Detection}, journal = {ACM Transactions on Knowledge Discovery from Data}, volume = {12}, number = {2}, pages = {17}, year = {2018}, doi = {10.1145/3106370} }
Abstract:
Large graphs arise in a number of contexts and understanding their structure and extracting information from them is an important research area. Early algorithms for mining communities have focused on global graph structure, and often run in time proportional to the size of the entire graph. As we explore networks with millions of vertices and find communities of size in the hundreds, it becomes important to shift our attention from macroscopic structure to microscopic structure in large networks. A growing body of work has been adopting local expansion methods in order to identify communities from a few exemplary seed members.
In this article, we propose a novel approach for finding overlapping communities called Lemon (Local Expansion via Minimum One Norm). Provided with a few known seeds, the algorithm finds the community by performing a local spectral diffusion. The core idea of Lemon is to use short random walks to approximate an invariant subspace near a seed set, which we refer to as local spectra. Local spectra can be viewed as the lowdimensional embedding that captures the nodes’ closeness in the local network structure. We show that Lemon’s performance in detecting communities is competitive with stateoftheart methods. Moreover, the running time scales with the size of the community rather than that of the entire graph. The algorithm is easy to implement and is highly parallelizable. We further provide theoretical analysis of the local spectral properties, bounding the measure of tightness of extracted community using the eigenvalues of graph Laplacian.
We thoroughly evaluate our approach using both synthetic and realworld datasets across different domains, and analyze the empirical variations when applying our method to inherently different networks in practice. In addition, the heuristics on how the seed set quality and quantity would affect the performance are provided.

C. Ponce and D. Bindel, “FLiER: Practical Topology Update Detection Using Sparse PMUs,” IEEE Transactions on Power Systems, vol. 32, no. 6, pp. 4222–4232, 2017.
@article{2017tps, author = {Ponce, Colin and Bindel, David}, title = {{FLiER}: Practical Topology Update Detection Using Sparse {PMU}s}, journal = {IEEE Transactions on Power Systems}, volume = {32}, number = {6}, pages = {42224232}, year = {2017}, doi = {10.1109/TPWRS.2017.2662002} }
Abstract:
In this paper, we present a Fingerprint Linear Estimation Routine (FLiER) to identify topology changes in power networks using readings from sparselydeployed phasor measurement units (PMUs). When a power line, load, or generator trips in a network, or when a substation is reconfigured, the event leaves a unique “voltage fingerprint” of bus voltage changes that we can identify using only the portion of the network directly observed by the PMUs. The naive bruteforce approach to identify a failed line from such voltage fingerprints, though simple and accurate, is slow.We derive an approximate algorithm based on a local linearization and a novel filtering approach that is faster and only slightly less accurate. We present experimental results using the IEEE 57bus, IEEE 118bus, and Polish 1999 2000 winter peak networks.

E. Yilmaz and D. Bindel, “Temperature Sensitivity and Shape Optimization of SolidState Wave Gyroscopes,” IEEE Sensors, vol. 16, no. 6, pp. 6213–6221, 2016.
@article{2016sensors, author = {Yilmaz, Erdal and Bindel, David}, title = {Temperature Sensitivity and Shape Optimization of SolidState Wave Gyroscopes}, journal = {IEEE Sensors}, volume = {16}, number = {6}, pages = {62136221}, year = {2016}, doi = {10.1109/JSEN.2016.2580670} }
Abstract:
We analyze the change of angular gain and vibration frequency of solidstate wave gyroscopes as a result of geometry perturbations due to thermal expansion. We analyze sensitivity of the device to thermal expansion effects by an isoparametric finite element analysis method, and we analyze the sensitivity to thermal changes in the material properties assuming a linear dependence on temperature. We quantify these sensitivities for common device geometries, and use our analysis as the basis for a local optimization problem that minimizes temperature sensitivity as a function of device shape.

D. Bindel and A. Hood, “Localization Theorems for Nonlinear Eigenvalues,” SIAM Review, vol. 57, no. 4, pp. 585–607, Dec. 2015.
SIGEST feature article.@article{2015sirev, author = {Bindel, David and Hood, Amanda}, title = {Localization Theorems for Nonlinear Eigenvalues}, journal = {SIAM Review}, publisher = {SIAM}, volume = {57}, number = {4}, pages = {585607}, month = dec, year = {2015}, notable = {SIGEST feature article.}, doi = {10.1137/15M1026511} }
Abstract:
Let $T : \Omega \rightarrow {\Bbb C}^{n\times n}$ be a matrixvalued function that is analytic on some simplyconnected domain $\Omega \subset {\Bbb C}$. A point $\lambda \in \Omega$ is an eigenvalue if the matrix $T(\lambda)$ is singular. In this paper, we describe new localization results for nonlinear eigenvalue problems that generalize Gershgorin’s theorem, pseudospectral inclusion theorems, and the BauerFike theorem. We use our results to analyze three nonlinear eigenvalue problems: an example from delay differential equations, a problem due to Hadeler, and a quantum resonance computation.

D. Bindel, J. Kleinberg, and S. Oren, “How Bad is Forming Your Own Opinion?,” Games and Economic Behavior, vol. 92, no. C, pp. 248–265, 2015.
@article{2015geb, author = {Bindel, David and Kleinberg, Jon and Oren, Sigal}, title = {How Bad is Forming Your Own Opinion?}, journal = {Games and Economic Behavior}, volume = {92}, number = {C}, year = {2015}, pages = {248265}, doi = {10.1016/j.geb.2014.06.004}, arxiv = {1203.2973} }
Abstract:
The question of how people form their opinion has fascinated economists and sociologists for long time. In many of the models, a group of people in a social network, each holding a numerical opinion, arrive at a shared opinion through repeated averaging with their neighbors in the network. Motivated by the observation that in reality consensus is rarely reached, we study a related sociological model in which individuals’ intrinsic beliefs counterbalance the averaging process and yield a diversity of opinions.
We interpret the repeated averaging process as bestresponse dynamics in an underlying game with natural payoffs and its limit as an equilibrium. This allows us to study the cost of disagreement by comparing between the cost at equilibrium and the social optimum. We also consider a natural network design problem in this setting: which links can we add to the underlying network to reduce the cost at equilibrium?

D. Bindel, M. Friedman, W. Govaerts, J. Hughes, and Y. A. Kuznetsov, “Numerical Computation of Bifurcations in Large Equilibrium Systems in MATLAB,” Journal of Computational and Applied Mathematics, vol. 261, pp. 232–248, 2014.
@article{2014matcont, author = {Bindel, David and Friedman, Mark and Govaerts, Willy and Hughes, Jeremy and Kuznetsov, Yuri A.}, title = {Numerical Computation of Bifurcations in Large Equilibrium Systems in {MATLAB}}, journal = {Journal of Computational and Applied Mathematics}, volume = {261}, pages = {232248}, year = {2014}, doi = {10.1016/j.cam.2013.10.034} }
Abstract:
The Continuation of Invariant Subspaces (CIS) algorithm produces a smoothlyvarying basis for an invariant subspace R(s) of a parameterdependent matrix $A(s)$. We have incorporated the CIS algorithm into
Cl_matcont
, a Matlab package for the study of dynamical systems and their bifurcations. Using subspace reduction, we extend the functionality ofCl_matcont
to largescale computations of bifurcations of equilibria. In this paper, we describe the algorithms and functionality of the resulting Matlab bifurcation packageCl_matcontL
. The novel features include: new CISbased, continuous, wellscaled test functions for codimension 1 and 2 bifurcations; detailed description of locators for large problems; and examples of bifurcation analysis in large sparse problems. 
D. Bindel and A. Hood, “Localization Theorems for Nonlinear Eigenvalues,” SIAM Journal on Matrix Analysis, vol. 34, no. 4, pp. 1728–1749, 2013.
2015 SIAG/LA award (best journal paper in applied LA in three years).@article{2013simax, author = {Bindel, David and Hood, Amanda}, title = {Localization Theorems for Nonlinear Eigenvalues}, journal = {SIAM Journal on Matrix Analysis}, volume = {34}, number = {4}, pages = {17281749}, year = {2013}, doi = {10.1137/130913651}, arxiv = {http://arxiv.org/abs/1303.4668}, notable = {2015 SIAG/LA award (best journal paper in applied LA in three years).} }
Abstract:
Let $T : \Omega \rightarrow {\Bbb C}^{n \times n}$ be a matrixvalued function that is analytic on some simplyconnected domain $\Omega \subset {\Bbb C}$. A point $\lambda \in \Omega$ is an eigenvalue if the matrix $T(\lambda)$ is singular. In this paper, we describe new localization results for nonlinear eigenvalue problems that generalize Gershgorin’s theorem, pseudospectral inclusion theorems, and the BauerFike theorem. We use our results to analyze three nonlinear eigenvalue problems: an example from delay differential equations, a problem due to Hadeler, and a quantum resonance computation.

W. Xie, G. Wang, D. Bindel, A. Demers, and J. Gehrke, “Fast Iterative Graph Computation with Block Updates,” Proceedings of the VLDB Endowment, vol. 6, no. 14, pp. 2014–2025, 2013.
@article{2013blockgrace, author = {Xie, Wenlei and Wang, Guozhang and Bindel, David and Demers, Alan and Gehrke, Johannes}, journal = {Proceedings of the VLDB Endowment}, number = {14}, pages = {20142025}, publisher = {VLDB Endowment}, title = {Fast Iterative Graph Computation with Block Updates}, volume = {6}, year = {2013}, doi = {10.14778/2556549.2556581}, code = {https://github.com/wenleix/BlockGRACE} }
Abstract:
Scaling iterative graph processing applications to large graphs is an important problem. Performance is critical, as data scientists need to execute graph programs many times with varying parameters. The need for a highlevel, highperformance programming model has inspired much research on graph programming frameworks. In this paper, we show that the important class of computationally light graph applications – applications that perform little computation per vertex – has severe scalability problems across multiple cores as these applications hit an early “memory wall” that limits their speedup. We propose a novel blockoriented computation model, in which computation is iterated locally over blocks of highly connected nodes, significantly improving the amount of computation per cache miss. Following this model, we describe the design and implementation of a blockaware graph processing runtime that keeps the familiar vertexcentric programming paradigm while reaping the benefits of blockoriented execution. Our experiments show that blockoriented execution significantly improves the performance of our framework for several graph applications.

W. He, D. Bindel, and S. Govindjee, “Topology Optimization in Micromechanical Resonator Design,” Optimization and Engineering, vol. 13, no. 2, 2012.
@article{2012memsopt, author = {He, Wei and Bindel, David and Govindjee, Sanjay}, title = {Topology Optimization in Micromechanical Resonator Design}, journal = {Optimization and Engineering}, volume = {13}, number = {2}, year = {2012}, doi = {10.1007/s1108101191391} }
Abstract:
A topology optimization problem in micromechanical resonator design is addressed in this paper. The design goal is to control the first several eigenfrequencies of a micromechanical resonator using topology optimization. The design variable is the distribution of mass in a constrained domain which we model via (1) the Simple Isotropic Material with Penalization Model and (2) the Peak Function Model. The overall optimization problem is solved using the Method of Moving Asymptotes and a Genetic Algorithm combined with a local gradient method. A numerical example is presented to highlight the features of the methods in more detail. The advantages and disadvantages of each method are discussed.

Y. Zhao, Y. Chen, and D. Bindel, “Towards Unbiased EndtoEnd Network Diagnosis,” IEEE/ACM Transactions on Networking, vol. 17, no. 6, pp. 1724–1737, Dec. 2009.
@article{2009tons, author = {Zhao, Yao and Chen, Yan and Bindel, David}, title = {Towards Unbiased EndtoEnd Network Diagnosis}, journal = {IEEE/ACM Transactions on Networking}, volume = {17}, number = {6}, pages = {17241737}, month = dec, year = {2009}, doi = {10.1109/TNET.2009.2022158} }
Abstract:
Internet fault diagnosis is extremely important for endusers, overlay network service providers (like Akamai ), and even Internet service providers (ISPs). However, because linklevel properties cannot be uniquely determined from endtoend measurements, the accuracy of existing statistical diagnosis approaches is subject to uncertainty from statistical assumptions about the network. In this paper, we propose a novel leastbiased endtoend network diagnosis (in short, LEND) system for inferring linklevel properties like loss rate. We define a minimal identifiable link sequence (MILS) as a link sequence of minimal length whose properties can be uniquely identified from endtoend measurements. We also design efficient algorithms to find all the MILSs and infer their loss rates for diagnosis. Our LEND system works for any network topology and for both directed and undirected properties and incrementally adapts to network topology and property changes. It gives highly accurate estimates of the loss rates of MILSs, as indicated by both extensive simulations and Internet experiments. Furthermore, we demonstrate that such diagnosis can be achieved with fine granularity and in near realtime even for reasonably large overlay networks. Finally, LEND can supplement existing statistical inference approaches and provide smooth tradeoff between diagnosis accuracy and granularity.

D. Bindel, J. Demmel, and M. Friedman, “Continuation of Invariant Subspaces in Large Bifurcation Problems,” SIAM Journal on Scientific Computing, vol. 30, no. 2, pp. 637–656, Feb. 2008.
@article{2008cis, author = {Bindel, David and Demmel, James and Friedman, Mark}, title = {Continuation of Invariant Subspaces in Large Bifurcation Problems}, journal = {SIAM Journal on Scientific Computing}, volume = {30}, number = {2}, pages = {637656}, month = feb, year = {2008}, doi = {10.1137/060654219} }
Abstract:
We summarize an algorithm for computing a smooth orthonormal basis for an invariant subspace of a parameterdependent matrix, and describe how to extend it for numerical bifurcation analysis. We adapt the continued subspace to track behavior relevant to bifurcations, and use projection methods to deal with large problems. To test our ideas, we have integrated our code into MATCONT, a program for numerical continuation and bifurcation analysis.

Y. Chen, D. Bindel, H. Song, B. Chavez, and R. Katz, “AlgebraBased Scalable Overlay Network Monitoring: Algorithms, Evaluation, and Applications,” ACM Transactions on Networking, vol. 15, no. 5, pp. 1084–1097, Oct. 2007.
@article{2007tons, author = {Chen, Yan and Bindel, David and Song, Hanhee and Chavez, Brian and Katz, Randy}, title = {AlgebraBased Scalable Overlay Network Monitoring: Algorithms, Evaluation, and Applications}, journal = {ACM Transactions on Networking}, volume = {15}, number = {5}, pages = {10841097}, month = oct, year = {2007}, doi = {10.1109/TNET.2007.896251} }
Abstract:
Overlay network monitoring enables distributed Internet applications to detect and recover from path outages and periods of degraded performance within seconds. For an overlay network with end hosts, existing systems either require measurements, and thus lack scalability, or can only estimate the latency but not congestion or failures. Our earlier extended abstract [Y. Chen, D. Bindel, and R. H. Katz, “Tomographybased overlay network monitoring,” Proceedings of the ACM SIGCOMM Internet Measurement Conference (IMC), 2003] briefly proposes an algebraic approach that selectively monitors linearly independent paths that can fully describe all the paths. The loss rates and latency of these paths can be used to estimate the loss rates and latency of all other paths. Our scheme only assumes knowledge of the underlying IP topology, with links dynamically varying between lossy and normal. In this paper, we improve, implement, and extensively evaluate such a monitoring system. We further make the following contributions: i) scalability analysis indicating that for reasonably large n (e.g., 100), the growth of $k$ is bounded as $O(n \log n)$, ii) efficient adaptation algorithms for topology changes, such as the addition or removal of end hosts and routing changes, iii) measurement load balancing schemes, iv) topology measurement error handling, and v) design and implementation of an adaptive streaming media system as a representative application. Both simulation and Internet experiments demonstrate we obtain highly accurate path loss rate estimation while adapting to topology changes within seconds and handling topology errors.

D. Bindel and M. Zworski, “Symmetry of Bound and Antibound States in the Semiclassical Limit,” Letters in Math Physics, vol. 81, no. 2, pp. 107–117, Aug. 2007.
@article{2007symmetry, author = {Bindel, David and Zworski, Maciej}, title = {Symmetry of Bound and Antibound States in the Semiclassical Limit}, journal = {Letters in Math Physics}, volume = {81}, number = {2}, pages = {107117}, month = aug, year = {2007}, doi = {10.1007/s1100500701787} }
Abstract:
Motivated by a recent numerical observation we show that in one dimensional scattering a barrier separating the interaction region from infinity implies approximate symmetry of bound and antibound states. We also outline the numerical procedure used for an efficient computation of one dimensional resonances.

D. Bindel and S. Govindjee, “Elastic PMLs for Resonator Anchor Loss Simulation,” International Journal for Numerical Methods in Engineering, vol. 64, no. 6, pp. 789–818, Oct. 2005.
@article{2005ijnme, author = {Bindel, David and Govindjee, Sanjay}, title = {Elastic {PMLs} for Resonator Anchor Loss Simulation}, journal = {International Journal for Numerical Methods in Engineering}, volume = {64}, number = {6}, pages = {789818}, month = oct, year = {2005}, doi = {10.1002/nme.1394} }
Abstract:
Electromechanical resonators and filters, such as quartz, ceramic, and surfaceacoustic wave devices, are important signalprocessing elements in communication systems. Over the past decade, there has been substantial progress in developing new types of miniaturized electromechanical resonators using microfabrication processes. For these microresonators to be viable they must have high and predictable quality factors ($Q$). Depending on scale and geometry, the energy losses that lower $Q$ may come from material damping, thermoelastic damping, air damping, or radiation of elastic waves from an anchor. Of these factors, anchor losses are the least understood because such losses are due to a complex radiation phenomena in a semiinfinite elastic halfspace. Here, we describe how anchor losses can be accurately computed using an absorbing boundary based on a perfectly matched layer (PML) which absorbs incoming waves over a wide frequency range for any nonzero angle of incidence. We exploit the interpretation of the PML as a complexvalued change of coordinates to illustrate how one can come to a simpler finite element implementation than was given in its original presentations. We also examine the convergence and accuracy of the method, and give guidelines for how to choose the parameters effectively. As an example application, we compute the anchor loss in a micro disk resonator and compare it to experimental data. Our analysis illustrates a surprising modemixing phenomenon which can substantially affect the quality of resonance.

D. Bindel, J. Demmel, W. Kahan, and O. Marques, “On Computing Givens Rotations Reliable and Efficiently,” ACM Transactions on Mathematical Software, vol. 28, no. 2, pp. 206–238, Jun. 2002.
@article{2002toms, author = {Bindel, David and Demmel, James and Kahan, William and Marques, Osni}, title = {On Computing {Givens} Rotations Reliable and Efficiently}, journal = {ACM Transactions on Mathematical Software}, volume = {28}, number = {2}, pages = {206238}, month = jun, year = {2002}, doi = {10.1145/567806.567809} }
Abstract:
We consider the efficient and accurate computation of Givens rotations. When $f$ and $g$ are positive real numbers, this simply amounts to computing the values of $c = f/\sqrt{f^2 + g^2}$, $s = g/\sqrt{f^2 + g^2}$, and $r = \sqrt{f^2 + g^2}$. This apparently trivial computation merits closer consideration for the following three reasons. First, while the definitions of $c$, $s$ and $r$ seem obvious in the case of two nonnegative arguments $f$ and $g$, there is enough freedom of choice when one or more of $f$ and $g$ are negative, zero or complex that LAPACK auxiliary routines SLARTG, CLARTG, SLARGV and CLARGV can compute rather different values of $c$, $s$ and $r$ for mathematically identical values of $f$ and $g$. To eliminate this unnecessary ambiguity, the BLAS Technical Forum chose a single consistent definition of Givens rotations that we will justify here. Second, computing accurate values of $c$, $s$ and $r$ as efficiently as possible and reliably despite over/underflow is surprisingly complicated. For complex Givens rotations, the most efficient formulas require only one real square root and one real divide (as well as several much cheaper additions and multiplications), but a reliable implementation using only working precision has a number of cases. On a Sun Ultra10, the new implementation is slightly faster than the previous LAPACK implementation in the most common case, and 2.7 to 4.6 times faster than the corresponding vendor, reference or ATLAS routines. It is also more reliable; all previous codes occasionally suffer from large inaccuracies due to over/underflow. For real Givens rotations, there are also improvements in speed and accuracy, though not as striking. Third, the design process that led to this reliable implementation is quite systematic, and could be applied to the design of similarly reliable subroutines.
Conference papers

K. Dong, D. Eriksson, H. Nickisch, D. Bindel, and A. G. Wilson, “Scalable Log Determinants for Gaussian Process Kernel Learning,” in Proceedings of NIPS 2017, 2017.
@inproceedings{2017nips, author = {Dong, Kun and Eriksson, David and Nickisch, Hannes and Bindel, David and Wilson, Andrew Gordon}, booktitle = {Proceedings of NIPS 2017}, title = {Scalable Log Determinants for Gaussian Process Kernel Learning}, year = {2017}, month = dec, link = {https://arxiv.org/pdf/1711.03481.pdf}, arxiv = {1711.03481.pdf} }
Abstract:
For applications as varied as Bayesian neural networks, determinantal point processes, elliptical graphical models, and kernel learning for Gaussian processes (GPs), one must compute a log determinant of an $n \times n$ positive definite matrix, and its derivatives – leading to prohibitive $O(n^3)$ computations. We propose novel $O(n)$ approaches to estimating these quantities from only fast matrix vector multiplications (MVMs). These stochastic approximations are based on Chebyshev, Lanczos, and surrogate models, and converge quickly even for kernel matrices that have challenging spectra. We leverage these approximations to develop a scalable Gaussian process approach to kernel learning. We find that Lanczos is generally superior to Chebyshev for kernel learning, and that a surrogate approach can be highly efficient and accurate with popular kernels.

M. Lee, D. Bindel, and D. Mimno, “From Correlation to Hierarchy: Practical Topic Modeling via Spectral Inference,” in Proceedings of the 12th INFORMS Workshop on Data Mining and Decision Analytics, 2017.
Best student paper award@inproceedings{2017informs, author = {Lee, Moontae and Bindel, David and Mimno, David}, title = {From Correlation to Hierarchy: Practical Topic Modeling via Spectral Inference}, booktitle = {Proceedings of the 12th INFORMS Workshop on Data Mining and Decision Analytics}, year = {2017}, month = oct, notable = {Best student paper award} }
Abstract:
Topic models were originally applied in text analysis for extracting highlevel themes from documents, but they work equally well in any setting where users select items from an inventory. Recent work in spectral topic modeling has provided algorithms that operate only on easilycollected summary statistics, rather than exhaustively iterating over the full dataset. The “anchor word” algorithms learn topics by decomposing the cooccurrence between pairs of words into a matrix of topics over words and a matrix of relations between topics. While these algorithms provide transparent inference and provable guarantees in addition to scalability, there are several known issues: inference can be infeasible for large vocabularies and cannot learn quality topics on noisy real data with high sensitivity to learning parameters. In this paper, we solidify the foundations of anchorbased spectral inference and propose practical algorithms that can efficiently tackle each of these problems within the framework of Joint Stochastic Matrix Factorization. These algorithms preserve the provable guarantees and scalability of earlier algorithms, but are more consistent and more stable in identifying quality topics. In addition, this algorithm can also consider and learn meaningful correlations between topics, enabling correlated and hierarchical models. We demonstrate these methods on two text corpora, a corpus of user movie ratings, and a corpus of song playlists.

P. Shi, K. He, D. Bindel, and J. Hopcroft, “Local Lanczos Spectral Approximation for Community Detection,” in Proceedings of ECMLPKDD, 2017.
@inproceedings{2017ecmlpkdd, author = {Shi, Pan and He, Kun and Bindel, David and Hopcroft, John}, title = {Local Lanczos Spectral Approximation for Community Detection}, booktitle = {Proceedings of ECMLPKDD}, year = {2017}, month = sep }
Abstract:
We propose a novel approach called the Local Lanczos Spectral Approximation (LLSA) for identifying all latent members of a local community from very few seed members. To reduce the computation complexity, we first apply a fast heat kernel diffusing to sample a comparatively small subgraph covering almost all possible community members around the seeds. Then starting from a normalized indicator vector of the seeds and by a few steps of Lanczos iteration on the sampled subgraph, a local eigenvector is gained for approximating the eigenvector of the transition matrix with the largest eigenvalue. Elements of this local eigenvector is a relaxed indicator for the affiliation probability of the corresponding nodes to the target community. We conduct extensive experiments on realworld datasets in various domains as well as synthetic datasets. Results show that the proposed method outperforms stateoftheart local community detection algorithms. To the best of our knowledge, this is the first work to adapt the Lanczos method for local community detection, which is natural and potentially effective. Also, we did the first attempt of using heat kernel as a sampling method instead of detecting communities directly, which is proved empirically to be very efficient and effective.

K. Wilson, D. Bindel, and N. Snavely, “When is Rotations Averaging Hard?,” in Proceedings of ECCV 2016, 2016.
@inproceedings{2016rotations, author = {Wilson, Kyle and Bindel, David and Snavely, Noah}, booktitle = {Proceedings of ECCV 2016}, title = {When is Rotations Averaging Hard?}, month = oct, year = {2016} }
Abstract:
Rotations averaging has become a key subproblem in global Structure from Motion methods. Several solvers exist, but they do not have guarantees of correctness. They can produce highquality results, but also sometimes fail. Our understanding of what makes rotations averaging problems easy or hard is still very limited. To investigate the difficulty of rotations averaging, we perform a local convexity analysis under an $L_2$ cost function. Although a previous result has shown that in general, this problem is locally convex almost nowhere, we show how this negative conclusion can be reversed by considering the gauge ambiguity.
Our theoretical analysis reveals the factors that determine local convexity—noise and graph structure—as well as how they interact, which we describe by a particular Laplacian matrix. Our results are useful for predicting the difficulty of problems, and we demonstrate this on practical datasets. Our work forms the basis of a deeper understanding of the key properties of rotations averaging problems, and we discuss how it can inform the design of future solvers for this important problem.

K. He, P. Shi, J. Hopcroft, and D. Bindel, “Local Spectral Diffusion for Robust Community Detection,” in KDD Workshop on Mining and Learning with Graphs, 2016.
@inproceedings{2016lospkdd, author = {He, Kun and Shi, Pan and Hopcroft, John and Bindel, David}, booktitle = {KDD Workshop on Mining and Learning with Graphs}, title = {Local Spectral Diffusion for Robust Community Detection}, month = aug, year = {2016} }
Abstract:
We address a semisupervised learning problem of identifying all latent members of a local community from very few labeled seed members in large networks. By a simple and efficient sampling method, we conduct a comparatively small subgraph encompassing most of the latent members such that the followup membership identification could focus on an accurate local region instead of the whole network. Then we look for a sparse vector, a relaxed indicator vector representing the subordinative probability of the corresponding nodes, that lies in a local spectral subspace defined by an order$d$ Krylov subspace. The subspace serves as a local proxy for the invariant subspace spanned by leading eigenvectors of the Laplacian matrices. Based on Rayleigh quotients, we relate the local membership identification task as a local RatioCut or local normalized cut optimization problem, and provide some theoretical justifications.
We thoroughly explore different probability diffusion methods for the subspace definition and evaluate our method on four groups with a total of 28 representative LFR benchmark datasets, and eight public available realworld networks with labeled ground truth communities across multiple domains. Experimental results exhibit the effectiveness and robustness of the proposed algorithm, and the local spectral communities perform better than those from the celebrated Heat Kernel diffusion and the PageRank diffusion.

E. Yilmaz and D. Bindel, “Temperature Sensitivity of SolidWave Gyroscopes (Late News),” in Proceedings of the Hilton Head SolidSate Sensor and Actuator Workshop 2016, 2016.
@inproceedings{2016hhworkshop, author = {Yilmaz, Erdal and Bindel, David}, booktitle = {Proceedings of the Hilton Head SolidSate Sensor and Actuator Workshop 2016}, title = {Temperature Sensitivity of SolidWave Gyroscopes (Late News)}, month = jun, year = {2016} }
Abstract:
We analyze the change of angular gain and vibration frequency of solidwave gyroscopes as a result of geometry perturbations due to thermal expansion. We formulate a temperature sensitivity analysis by assuming a linear dependence of material properties to temperature, and quantify it for common device geometries.

A. E. Gencer, E. G. Sirer, R. Van Renesse, and D. Bindel, “Configuring Distributed Computations Using Response Surfaces,” in Proceedings of Middleware 2015, 2015.
Best student paper.@inproceedings{2015middleware, author = {Gencer, Adam Efe and Sirer, Emin Gun and Van Renesse, Robbert and Bindel, David}, title = {Configuring Distributed Computations Using Response Surfaces}, booktitle = {Proceedings of Middleware 2015}, month = dec, year = {2015}, notable = {Best student paper.}, doi = {10.1145/2814576.2814730} }
Abstract:
Configuring large distributed computations is a challenging task. Efficiently executing distributed computations requires configuration tuning based on careful examination of application and hardware properties. Considering the large number of parameters and impracticality of using trial and error in a production environment, programmers tend to make these decisions based on their experience and rules of thumb. Such configurations can lead to underutilized and costly clusters, and missed deadlines.
In this paper, we present a new methodology for determining desired hardware and software configuration parameters for distributed computations. The key insight behind this methodology is to build a response surface that captures how applications perform under different hardware and software configuration. Such a model can be built through iterated experiments using the real system, or, more efficiently, using a simulator. The resulting model can then generate recommendations for configuration parameters that are likely to yield the desired results even if they have not been tried either in simulation or in reallife. The process can be iterated to refine previous predictions and achieve better results.
We have implemented this methodology in a configuration recommendation system for MapReduce 2.0 applications. Performance measurements show that representative applications achieve up to $5 \times$ performance improvement when they use the recommended configuration parameters compared to the default ones.

M. Lee, D. Bindel, and D. Mimno, “Robust Spectral Inference for Joint Stochastic Matrix Factorization,” in Proceedings of NIPS 2015, 2015, pp. 2710–2718.
@inproceedings{2015nips, author = {Lee, Moontae and Bindel, David and Mimno, David}, title = {Robust Spectral Inference for Joint Stochastic Matrix Factorization}, booktitle = {Proceedings of NIPS 2015}, pages = {27102718}, month = dec, year = {2015} }
Abstract:
Spectral inference provides fast algorithms and provable optimality for latent topic analysis. But for real data these algorithms require additional adhoc heuristics, and even then often produce unusable results. We explain this poor performance by casting the problem of topic inference in the framework of Joint Stochastic Matrix Factorization (JSMF) and showing that previous methods violate the theoretical conditions necessary for a good solution to exist. We then propose a novel rectification method that learns high quality topics and their interactions even on small, noisy data. This method achieves results comparable to probabilistic techniques in several domains while maintaining scalability and provable optimality.

K. He, Y. Sun, D. Bindel, J. Hopcroft, and Y. Li, “Detecting Overlapping Communities from Local Spectral Subspaces,” in Proceedings of ICDM 2015, 2015.
@inproceedings{2015icdm, author = {He, Kun and Sun, Yiwei and Bindel, David and Hopcroft, John and Li, Yixuan}, title = {Detecting Overlapping Communities from Local Spectral Subspaces}, booktitle = {Proceedings of ICDM 2015}, month = nov, year = {2015}, doi = {10.1109/ICDM.2015.89}, arxiv = {1509.08065} }
Abstract:
Based on the definition of local spectral subspace, we propose a novel approach called LOSP for local overlapping community detection. Using the power method for a few steps, LOSP finds an approximate invariant subspace, which depicts the embedding of the local neighborhood structure around the seeds of interest. LOSP then identifies the local community expanded from the given seeds by seeking a sparse indicator vector in the subspace where the seeds are in its support. We provide a systematic investigation on LOSP, and thoroughly evaluate it on large real world networks across multiple domains. With the prior information of very few seed members, LOSP can detect the remaining members of a target community with high accuracy. Experiments demonstrate that LOSP outperforms the Heat Kernel and PageRank diffusions. Using LOSP as a subroutine, we further address the problem of multiple membership identification, which aims to find all the communities a single vertex belongs to. High F1 scores are achieved in detecting multiple local communities with respect to arbitrary single seed for various large real world networks.

W. Xie, D. Bindel, A. Demers, and J. Gehrke, “EdgeWeighted Personalized PageRank: Breaking A DecadeOld Performance Barrier,” in Proceedings of ACM KDD 2015, 2015.
Best student paper award.@inproceedings{2015edgeppr, author = {Xie, Wenlei and Bindel, David and Demers, Alan and Gehrke, Johannes}, booktitle = {Proceedings of ACM KDD 2015}, title = {EdgeWeighted Personalized {PageRank}: Breaking A DecadeOld Performance Barrier}, month = aug, year = {2015}, doi = {10.1145/2783258.2783278}, notable = {Best student paper award.}, code = {https://github.com/wenleix/EdgePPR}, slides = {present/201508kddtalk_kddaug15.pdf}, talk = {https://www.youtube.com/watch?v=Cop9Arcw6wY} }
Abstract:
Personalized PageRank is a standard tool for finding vertices in a graph that are most relevant to a query or user. To personalize PageRank, one adjusts node weights or edge weights that determine teleport probabilities and transition probabilities in a random surfer model. There are many fast methods to approximate PageRank when the node weights are personalized; however, personalization based on edge weights has been an open problem since the dawn of personalized PageRank over a decade ago. In this paper, we describe the first fast algorithm for computing PageRank on general graphs when the edge weights are personalized. Our method, which is based on model reduction, outperforms existing methods by nearly five orders of magnitude. This huge performance gain over previous work allows us — for the very first time — to solve learningtorank problems for edge weight personalization at interactive speeds, a goal that had not previously been achievable for this class of problems.

Y. Li, K. He, D. Bindel, and J. Hopcroft, “Uncovering the Small Community Structure in Large Networks: A Local Spectral Approach,” in Proceedings of WWW 2015, 2015.
@inproceedings{2015www, author = {Li, Yixuan and He, Kun and Bindel, David and Hopcroft, John}, title = {Uncovering the Small Community Structure in Large Networks: A Local Spectral Approach}, booktitle = {Proceedings of WWW 2015}, month = may, year = {2015}, doi = {10.1145/2736277.2741676}, arxiv = {1509.07715} }
Abstract:
Large graphs arise in a number of contexts and understanding their structure and extracting information from them is an important research area. Early algorithms on mining communities have focused on the global structure, and often run in time functional to the size of the entire graph. Nowadays, as we often explore networks with billions of vertices and find communities of size hundreds, it is crucial to shift our attention from macroscopic structure to microscopic structure when dealing with large networks. A growing body of work has been adopting local expansion methods in order to identify the community from a few exemplary seed members. Very few approaches can systematically demonstrate both high efficiency and effectiveness that significantly stands out amongst the divergent approaches in finding communities.
In this paper, we propose a novel approach for finding overlapping communities called LEMON (Local Expansion via Minimum One Norm). Different from PageRanklike diffusion methods, LEMON finds the community by seeking a sparse vector in the span of the local spectra such that the seeds are in its support. We show that LEMON can achieve the highest detection accuracy among stateoftheart proposals. The running time depends on the size of the community rather than that of the entire graph. The algorithm is easy to implement, and is highly parallelizable.
Moreover, given that networks are not all similar in nature, a comprehensive analysis on how the local expansion approach is suited for uncovering communities in different networks is still lacking. We thoroughly evaluate our approach using both synthetic and realworld datasets across different domains, and analyze the empirical variations when applying our method to inherently different networks in practice. In addition, the heuristics on how the quality and quantity of the seed set would affect the performance are provided.

K. Dong and D. Bindel, “Modified Kernel Polynomial Method for Estimating Graph Spectra,” in SIAM Network Science 2015 (poster), 2015.
@inproceedings{2015siamns, author = {Dong, Kun and Bindel, David}, title = {Modified Kernel Polynomial Method for Estimating Graph Spectra}, booktitle = {SIAM Network Science 2015 (poster)}, month = may, year = {2015} }
Abstract:
The kernel polynomial method (KPM) is a standard tool in condensed matter physics to estimate the density of states for a quantum system. We use the KPM to instead estimate the eigenvalue densities of the normalized adjacency matrices of “natural” graphs. Because natural graph spectra often include highmultiplicity eigenvalues corresponding to certain motifs in the graph, we introduce a preprocessing phase that counts just these special eigenvalues, leaving the rest of the eigenvalue distribution to be estimated by the standard KPM.

E. Yilmaz and D. Bindel, “Effects of imperfections on solidwave gyroscope dynamics,” in Proceedings of IEEE SENSORS 2013, 2013.
@inproceedings{2013sensors, author = {Yilmaz, Erdal and Bindel, David}, title = {Effects of imperfections on solidwave gyroscope dynamics}, booktitle = {Proceedings of IEEE SENSORS 2013}, month = nov, year = {2013}, doi = {10.1109/ICSENS.2013.6688462} }
Abstract:
Solidwave gyroscopes are symmetric resonators that sense rotation by measuring how Coriolis forces perturb a degenerate mode pair. The idealized dynamics of these devices are described by ODE models of two identical oscillators coupled by a perturbation due to rotation. In miniaturized solidwave gyroscopes, geometric distortions due to imperfect fabrication also perturb the dynamics, and this limits sensing accuracy. In this work, we describe how geometric imperfections affect the dynamics of solidwave gyroscopes. We also use selection rules both to find qualitative information about what types of geometry perturbations most affect sensor performance and to accelerate computations

T. Zou, G. Wang, M. Vaz Salles, D. Bindel, A. Demers, J. Gehrke, and W. White, “Making TimeStepped Applications Tick in the Cloud,” in Proceedings of the Second ACM Symposium on Cloud Computing (SOCC), 2011.
@inproceedings{2011socc, author = {Zou, Tao and Wang, Guozhang and Vaz Salles, Marcos and Bindel, David and Demers, Alan and Gehrke, Johannes and White, Walker}, title = {Making TimeStepped Applications Tick in the Cloud}, booktitle = {Proceedings of the Second ACM Symposium on Cloud Computing (SOCC)}, month = oct, year = {2011}, doi = {10.1145/2038916.2038936} }
Abstract:
Scientists are currently evaluating the cloud as a new platform. Many important scientific applications, however, perform poorly in the cloud. These applications proceed in highly parallel discrete timesteps or “ticks,” using logical synchronization barriers at tick boundaries. We observe that network jitter in the cloud can severely increase the time required for communication in these applications, significantly increasing overall running time.
In this paper, we propose a general parallel framework to process timestepped applications in the cloud. Our framework exposes a highlevel, datacentric programming model which represents application state as tables and dependencies between states as queries over these tables. We design a jittertolerant runtime that uses these data dependencies to absorb latency spikes by (1) carefully scheduling computation and (2) replicating data and computation. Our datadriven approach is transparent to the scientist and requires little additional code. Our experiments show that our methods improve performance up to a factor of three for several typical timestepped applications.

D. Bindel, S. Oren, and J. Kleinberg, “How Bad is Forming Your Own Opinion?,” in Proceedings of the 52nd IEEE Symposium on Foundations of Computer Science (FOCS), 2011.
@inproceedings{2011focs, author = {Bindel, David and Oren, Sigal and Kleinberg, Jon}, title = {How Bad is Forming Your Own Opinion?}, booktitle = {Proceedings of the 52nd IEEE Symposium on Foundations of Computer Science (FOCS)}, month = oct, year = {2011}, doi = {10.1109/FOCS.2011.43}, arxiv = {1203.2973} }
Abstract:
A longstanding line of work in economic theory has studied models by which a group of people in a social network, each holding a numerical opinion, can arrive at a shared opinion through repeated averaging with their neighbors in the network. Motivated by the observation that consensus is rarely reached in real opinion dynamics, we study a related sociological model in which individuals’ intrinsic beliefs counterbalance the averaging process and yield a diversity of opinions. By interpreting the repeated averaging as bestresponse dynamics in an underlying game with natural payoffs, and the limit of the process as an equilibrium, we are able to study the cost of disagreement in these models relative to a social optimum. We provide a tight bound on the cost at equilibrium relative to the optimum, our analysis draws a connection between these agreement models and extremal problems for generalized eigenvalues. We also consider a natural network design problem in this setting, where adding links to the underlying network can reduce the cost of disagreement at equilibrium.

C. BruynsMaxwell and D. Bindel, “Modal Parameter Tracking for Shape Changing Objects,” in Proceedings of DAFx 2007, 2007.
@inproceedings{2007sound, author = {BruynsMaxwell, Cynthia and Bindel, David}, title = {Modal Parameter Tracking for Shape Changing Objects}, booktitle = {Proceedings of DAFx 2007}, month = sep, year = {2007} }
Abstract:
For interactive sound synthesis, we would like to change the shape of a finite element model of an instrument and rapidly hear how the sound changes. Using modal synthesis methods, we would need to compute a new modal decomposition with each change in the geometry, making the analysis too slow for interactive use. However, by using modes computed for one geometry to estimate the frequencies for nearby geometries, we can hear much more quickly how changing the instrument shape changes the sound. In this paper, we describe how to estimate resonant frequencies of an instrument by combining information about the modes of two similar instruments. We also describe the balance between computational speed and accuracy of the computed resonances.

J. Demmel, J. Dongarra, B. Parlett, W. Kahan, M. Gu, D. Bindel, Y. Hida, X. Li, O. Marques, J. Riedy, C. Voemel, J. Langou, P. Lusczek, J. Kurzak, A. Butarri, J. Langou, and S. Tomov, “Prospectus for the Next LAPACK and ScaLAPACK Libraries,” in Proceedings of PARA 2006, 2006, pp. 11–23.
@inproceedings{2006para, author = {Demmel, James and Dongarra, Jack and Parlett, Beresford and Kahan, William and Gu, Ming and Bindel, David and Hida, Yozo and Li, Xiaoye and Marques, Osni and Riedy, Jason and Voemel, Christof and Langou, Julien and Lusczek, Piotr and Kurzak, Jakub and Butarri, Alfredo and Langou, Julie and Tomov, Stanimire}, title = {Prospectus for the Next {LAPACK} and {ScaLAPACK} Libraries}, booktitle = {Proceedings of PARA 2006}, pages = {1123}, year = {2006} }
Abstract:
New releases of the widely used LAPACK and ScaLAPACK numerical linear algebra libraries are planned. Based on an ongoing user survey (<www.netlib.org/lapackdev>) and research by many people, we are proposing the following improvements: Faster algorithms, including better numerical methods, memory hierarchy optimizations, parallelism, and automatic performance tuning to accommodate new architectures; More accurate algorithms, including better numerical methods, and use of extra precision; Expanded functionality, including updating and downdating, new eigenproblems, etc. and putting more of LAPACK into ScaLAPACK; Improved ease of use, e.g., via friendlier interfaces in multiple languages. To accomplish these goals we are also relying on better software engineering techniques and contributions from collaborators at many institutions.

C. Bruyns and D. Bindel, “Shape Changing Symmetric Objects for Sound Synthesis,” in Proceedings of 121st AES, 2006.
@inproceedings{2006sound, author = {Bruyns, Cynthia and Bindel, David}, title = {Shape Changing Symmetric Objects for Sound Synthesis}, booktitle = {Proceedings of 121st AES}, month = oct, year = {2006} }
Abstract:
In the last decade, many researchers have used modal synthesis for sound generation. Using a modal decomposition, one can convert a large system of coupled differential equations into simple, independent differential equations in one variable. To synthesize sound from the system, one solves these decoupled equations numerically, which is much more efficient than solving the original coupled system. For large systems, such as those obtained from finiteelement analysis of a musical instrument, the initial modal decomposition is timeconsuming. To design instruments from physical simulation, one would like to be able to compute modes in realtime, so that the geometry, and therefore spectrum, of an instrument can be changed interactively. In this paper, we describe how to quickly compute modes of instruments which have rotational symmetry in order to synthesize sounds of new instruments quickly enough for interactive instrument design.

Y. Zhao, Y. Chen, and D. Bindel, “Toward Unbiased EndtoEnd Network Diagnosis,” in Proceedings of SIGCOMM 2006, 2006, pp. 219–230.
@inproceedings{2006sigcomm, author = {Zhao, Yao and Chen, Yan and Bindel, David}, title = {Toward Unbiased EndtoEnd Network Diagnosis}, booktitle = {Proceedings of SIGCOMM 2006}, pages = {219230}, year = {2006}, doi = {10.1145/1151659.1159939} }
Abstract:
Internet fault diagnosis is extremely important for end users, overlay network service providers (like Akamai [1]) and even Internet service providers (ISPs). However, because linklevel properties cannot be uniquely determined from endtoend measurements, the accuracy of existing statistical diagnosis approaches is subject to uncertainty from statistical assumptions about the network. In this paper, we propose a novel Leastbiased Endtoend Network Diagnosis (in short, LEND) system for inferring linklevel properties like loss rate. We define a minimal identifiable link sequence (MILS) as a link sequence of minimal length whose properties can be uniquely identified from endtoend measurements. We also design efficient algorithms to find all the MILSes and infer their loss rates for diagnosis. Our LEND system works for any network topology and for both directed and undirected properties, and incrementally adapts to network topology and property changes. It gives highly accurate estimates of the loss rates of MILSes, as indicated by both extensive simulations and Internet experiments. Furthermore, we demonstrate that such diagnosis can be achieved with fine granularity and in near realtime even for reasonably large overlay networks. Finally, LEND can supplement existing statistical inference approaches and provide smooth tradeoff between diagnosis accuracy and granularity.

Y. Zhao, Y. Chen, and D. Bindel, “Toward Deterministic Overlay Diagnosis,” in ACM SIGMETRICS/Performance 2006, 2006, pp. 387–388.

T. Koyama, D. Bindel, W. He, E. Quevy, J. Demmel, S. Govindjee, and R. Howe, “Simulation Tools for Damping in High Frequency Resonators,” in Proceedings of IEEE SENSORS 2005, 2005.
@inproceedings{2005sensors, author = {Koyama, Tsuyoshi and Bindel, David and He, Wei and Quevy, Emmanuel and Demmel, James and Govindjee, Sanjay and Howe, Roger}, title = {Simulation Tools for Damping in High Frequency Resonators}, booktitle = {Proceedings of IEEE SENSORS 2005}, month = nov, year = {2005}, doi = {10.1109/ICSENS.2005.1597708} }
Abstract:
This paper presents the development of HiQLab, a simulation tool to compute the effect of damping in high frequency resonators. Existing simulation tools allow designers to compute resonant frequencies but few tools provide estimates of damping, which is crucial in evaluating the performance of such devices. In the current code, two damping mechanisms: thermoelastic damping and anchor loss, have been implemented. Thermoelastic damping results from irreversible heat flow due to mechanicallydriven temperature gradients, while anchor loss occurs when highfrequency mechanical waves radiate away from the resonator and into the substrate. Our finiteelement simulation tool discretizes PDE models of both phenomena, and evaluates the quality factor ($Q$), a measure of damping in the system, with specialized eigencomputations and model reduction techniques. The core functions of the tool are written in C++ for performance. Interfaces are in Lua and MATLAB, which give users access to powerful visualization and pre and postprocessing capabilities.

Y. Zhao, Y. Chen, and D. Bindel, “Scalable and Deterministic Overlay Network Diagnosis,” in Proceedings of ACM SIGCOMM 2005 (poster), 2005.

D. Bindel, J. Demmel, W. Govaerts, and Y. Kuznetsov, “Bifurcation Analysis of Large Equilibrium Systems in MATLAB,” in Proceedings of ICCS 2005, 2005, vol. 3514, pp. 50–57.
@inproceedings{2005iccs, author = {Bindel, David and Demmel, James and Govaerts, Willy and Kuznetsov, Yuri}, title = {Bifurcation Analysis of Large Equilibrium Systems in {MATLAB}}, booktitle = {Proceedings of ICCS 2005}, volume = {3514}, series = {Springer LNCS}, pages = {5057}, month = apr, year = {2005}, doi = {10.1007/11428831_7} }
Abstract:
The Continuation of Invariant Subspaces (CIS) algorithm produces a smoothly varying basis for an invariant subspace $R(s)$ of a parameterdependent matrix $A(s)$. In the case when $A(s)$ is the Jacobian matrix for a system that comes from a spatial discretization of a partial differential equation, it will typically be large and sparse.
Cl_matcont
is a userfriendly MATLAB package for the study of dynamical systems and their bifurcations. We incorporate the CIS algorithm intoCl_matcont
to extend its functionality to large scale bifurcation computations via subspace reduction 
D. Bindel, E. Quevy, T. Koyama, J. Demmel, and R. Howe, “Anchor Loss Simulation in Resonators,” in Proceedings of MEMS 2005, 2005.
@inproceedings{2005mems, author = {Bindel, David and Quevy, Emmanuel and Koyama, Tsuyoshi and Demmel, James and Howe, Roger}, title = {Anchor Loss Simulation in Resonators}, booktitle = {Proceedings of MEMS 2005}, month = feb, year = {2005}, doi = {10.1109/MEMSYS.2005.1453885} }
Abstract:
Surfacemicromachined resonators and filters are attractive for many RF applications. While existing simulation tools allow designers to compute resonant frequencies, few tools provide estimates of the damping in these devices. This paper reports on a new tool that allows designers, for the first time, to compute anchor losses in highfrequency resonators and account for subsurface scatterers. By exercising the tool on a family of radially driven disk resonators, we show that the anchor loss mechanism for this class of devices involves a parasitic mixedmode bending action that pumps energy into the substrate. Further, using the tool, we predict a large variation in resonator quality depending upon film thickness. Our simulation shows that the source of this variation is a complex radialtobending motion interaction, which we visualize with a rootlocus diagram. We experimentally verify this predicted sensitivity using polySiGe disk resonators having $Q$’s ranging from 200 to 54,000.

Y. Chen, D. Bindel, H. Song, and R. Katz, “An Algebraic Approach to Practial and Scalable Overlay Network Monitoring,” in Proceedings of ACM SIGCOMM 2004, 2004.
@inproceedings{2004sigcomm, author = {Chen, Yan and Bindel, David and Song, Hanhee and Katz, Randy}, title = {An Algebraic Approach to Practial and Scalable Overlay Network Monitoring}, booktitle = {Proceedings of ACM SIGCOMM 2004}, year = {2004}, doi = {10.1145/1015467.1015475} }
Abstract:
Overlay network monitoring enables distributed Internet applications to detect and recover from path outages and periods of degraded performance within seconds. For an overlay network with $n$ end hosts, existing systems either require $O(n^2)$ measurements, and thus lack scalability, or can only estimate the latency but not congestion or failures. Our earlier extended abstract briefly proposes an algebraic approach that selectively monitors $k$ linearly independent paths that can fully describe all the $O(n^2)$ paths. The loss rates and latency of these $k$ paths can be used to estimate the loss rates and latency of all other paths. Our scheme only assumes knowledge of the underlying IP topology, with links dynamically varying between lossy and normal.In this paper, we improve, implement and extensively evaluate such a monitoring system. We further make the following contributions: i) scalability analysis indicating that for reasonably large n (e.g., 100), the growth of $k$ is bounded as $O(n \log n)$, ii) efficient adaptation algorithms for topology changes, such as the addition or removal of end hosts and routing changes, iii) measurement load balancing schemes, and iv) topology measurement error handling. Both simulation and Internet experiments demonstrate we obtain highly accurate path loss rate estimation while adapting to topology changes within seconds and handling topology errors.

D. Bindel, Z. Bai, and J. Demmel, “Model Reduction for RF MEMS Simulation,” in Proceedings of PARA 2004, 2004.
@inproceedings{2004para, author = {Bindel, David and Bai, Zhaojun and Demmel, James}, title = {Model Reduction for {RF MEMS} Simulation}, booktitle = {Proceedings of PARA 2004}, month = jun, year = {2004}, doi = {10.1007/11558958_34} }
Abstract:
Radiofrequency (RF) MEMS resonators, integrated into CMOS chips, are of great interest to engineers planning the next generation of communication systems. Fast simulations are necessary in order to gain insights into the behavior of these devices. In this paper, we discuss two structurepreserving modelreduction techniques and apply them to the frequencydomain analysis of two proposed MEMS resonator designs.

Y. Chen, D. Bindel, and R. Katz, “TomographyBased Overlay Network Monitoring,” in Proceedings of ACM SIGCOMM Internet Measurement Conference (IMC), 2003.
@inproceedings{2003imc, author = {Chen, Yan and Bindel, David and Katz, Randy}, title = {TomographyBased Overlay Network Monitoring}, booktitle = {Proceedings of ACM SIGCOMM Internet Measurement Conference (IMC)}, year = {2003}, doi = {10.1145/948205.948233} }
Abstract:
Overlay network monitoring enables distributed Internet applications to detect and recover from path outages and periods of degraded performance within seconds. For an overlay network with $n$ end hosts, existing systems either require $O(n^2)$ measurements, and thus lack scalability, or can only estimate the latency but not congestion or failures. Unlike other network tomography systems, we characterize endtoend losses (this extends to any additive metrics, including latency) rather than individual link losses. We find a minimal basis set of $k$ linearly independent paths that can fully describe all the $O(n^2)$ paths. We selectively monitor and measure the loss rates of these paths, then apply them to estimate the loss rates of all other paths. By extensively studying synthetic and real topologies, we find that for reasonably large n (e.g., 100), $k$ is only in the range of $O(n \log n)$. This is explained by the moderately hierarchical nature of Internet routine.Our scheme only assumes the knowledge of underlying IP topology, and any link can become lossy or return to normal. In addition, our technique is tolerant to topology measurement inaccuracies, and is adaptive to topology changes.

J. Clark, D. Bindel, W. Kao, E. Zhu, A. Kuo, N. Zhou, J. Nie, J. Demmel, Z. Bai, S. Govindjee, K. S. J. Pister, M. Gu, and A. Agogino, “Addressing the Needs of Complex MEMS Design,” in Proceedings of MEMS 2002, 2002.
@inproceedings{2002mems, author = {Clark, Jason and Bindel, David and Kao, Wayne and Zhu, Ernest and Kuo, Andrew and Zhou, Ningning and Nie, Jiawang and Demmel, James and Bai, Zhaojun and Govindjee, Sanjay and Pister, Kristofer S. J. and Gu, Ming and Agogino, Alice}, title = {Addressing the Needs of Complex {MEMS} Design}, booktitle = {Proceedings of MEMS 2002}, month = jan, year = {2002}, doi = {10.1109/MEMSYS.2002.984240} }
Abstract:
In this paper, we report several advances in the Sugar 2.0 MEMS system simulation package, including reducedorder modeling techniques, simple hierarchical description of complex structures, synthesis tools, a variety of models, and a webbased interface. Examples include the modeling of a torsional micromirror with lateral actuators compared to experiment, and the prototyping of a microrobot.

Y. Chen, A. Bargteil, D. Bindel, R. Katz, and J. Kubiatowicz, “Quantifying Network Denial of Service: A Location Service Case Study,” in Proceedings of the International Conference on Information and Communications Security (ICICS), 2001, vol. 2229, pp. 340–351.
@inproceedings{2001icics, author = {Chen, Yan and Bargteil, Adam and Bindel, David and Katz, Randy and Kubiatowicz, John}, title = {Quantifying Network Denial of Service: A Location Service Case Study}, booktitle = {Proceedings of the International Conference on Information and Communications Security (ICICS)}, volume = {2229}, series = {LNCS}, publisher = {Springer}, pages = {340351}, month = nov, year = {2001}, doi = {10.1007/3540456007_37} }
Abstract:
Network Denial of Service (DoS) attacks are increasing in frequency, severity and sophistication, making it desirable to measure the resilience of systems to DoS attacks. In this paper, we propose a simulationbased methodology and apply it to attacks on object location services such as DNS. Our results allow us to contrast the DoS resilience of three distinct architectures for object location.

J. Clark, D. Bindel, N. Zhou, S. Bhave, Z. Bai, J. Demmel, and K. S. J. Pister, “SUGAR: Advancements in a 3D MultiDomain Simulation Package for MEMS,” in Proceedings of the Microscale Systems: Mechanics and Measurements Symposium, 2001.
@inproceedings{2001sugar, author = {Clark, Jason and Bindel, David and Zhou, Ningning and Bhave, Sunil and Bai, Zhaojun and Demmel, James and Pister, Kristofer S. J.}, title = {{SUGAR}: Advancements in a 3D MultiDomain Simulation Package for {MEMS}}, booktitle = {Proceedings of the Microscale Systems: Mechanics and Measurements Symposium}, month = jun, year = {2001} }
Abstract:
Advancements in Sugar include 1) parameterizable netlists, 2) nonlinear frequency response analysis, 3) subnets, 4) improved MNA, 5) reduced order modeling, and 6) a more accurate nonlinear beam model. Examples of these features include the simulation of a twoaxis mirror with over 10,000 degrees of freedom, the reduced order modeling applied of an electrostatic gap actuator, the parameterized deflection space of a thermal actuator and serpentine flexure, and the nonlinear response of a fixedfixed beam.

Z. Bai, D. Bindel, J. Clark, N. Zhou, J. Demmel, and K. S. J. Pister, “New Numerical Techniques and Tools in SUGAR for 3D MEMS Simulation,” in Proceedings of the Fourth International Conference on Modeling and Simulation of Microsystems (MSM), 2001.
@inproceedings{2001msm, author = {Bai, Zhaojun and Bindel, David and Clark, Jason and Zhou, Ningning and Demmel, James and Pister, Kristofer S. J.}, title = {New Numerical Techniques and Tools in {SUGAR} for {3D MEMS} Simulation}, booktitle = {Proceedings of the Fourth International Conference on Modeling and Simulation of Microsystems (MSM)}, month = mar, year = {2001} }
Abstract:
SUGAR is a nodal analysis package for 3D MEMS simulation that owes its heritage and its name to the SPICE family of circuit simulation. SUGAR has undergone the stage of proofofconcept which showed that nodal analysis was in fact just as accurate and much faster than finite element simulation on many MEMS problems. The upcoming major release of SUGAR is version 2.0, which includes a number of new features, such as 3D beam and gap elements, thermal expansion, linearly and rotationally accelerating frames, and userdefined models.

J. Kubiatowicz, D. Bindel, Y. Chen, S. Czerwinski, P. Eaton, D. Geels, R. Gummadi, S. Rhea, H. Weatherspoon, W. Weimer, C. Wells, and B. Zhao, “OceanStore: An Architecture for GlobalScale Persistent Storage,” in Procedings of the Ninth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS 2000), 2000.
@inproceedings{2000asplos, author = {Kubiatowicz, John and Bindel, David and Chen, Yan and Czerwinski, Steven and Eaton, Patrick and Geels, Dennis and Gummadi, Ramakrishna and Rhea, Sean and Weatherspoon, Hakim and Weimer, Westley and Wells, Chris and Zhao, Ben}, title = {{OceanStore}: An Architecture for GlobalScale Persistent Storage}, booktitle = {Procedings of the Ninth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS 2000)}, month = nov, year = {2000}, doi = {10.1145/356989.357007} }
Abstract:
OceanStore is a utility infrastructure designed to span the globe and provide continuous access to persistent information. Since this infrastructure is comprised of untrusted servers, data is protected through redundancy and cryptographic techniques. To improve performance, data is allowed to be cached anywhere, anytime. Additionally, monitoring of usage patterns allows adaptation to regional outages and denial of service attacks; monitoring also enhances performance through proactive movement of data. A prototype implementation is currently under development.

J. Clark, N. Zhou, D. Bindel, L. Schenato, W. Wu, J. Demmel, and K. S. J. Pister, “3D MEMS Simulation Modeling Using Modified Nodal Analysis,” in Proceedings of the Microscale Systems: Mechanics and Measurements Symposium, 2000, pp. 68–75.
@inproceedings{2000mems, author = {Clark, Jason and Zhou, Ningning and Bindel, David and Schenato, Luca and Wu, W. and Demmel, James and Pister, Kristofer S. J.}, title = {{3D} {MEMS} Simulation Modeling Using Modified Nodal Analysis}, booktitle = {Proceedings of the Microscale Systems: Mechanics and Measurements Symposium}, pages = {6875}, month = jun, year = {2000} }
Abstract:
The modeling, simulation, and experimental verification of several MEMS devices are presented. Simulated results include 3D mode analysis, residual stress effects, thermal expansion, nonlinear deflections, timevarying electrostatic forces, process sensitivities, induced currents, and the transient performance in accelerated reference frames. To simulate the performance of these MEMS devices a modified nodal analysis approach is used to formulate a system of ODEs that is solved by static, steady state, and transient solvers.
Reports

A. Hood and D. Bindel, “Pseudospectral bounds on transient growth for higher order and constant delay differential equations,” Nov. 2016. Submitted to SIAM Journal on Matrix Analysis and Applictions.
@techreport{2016transienttr, author = {Hood, Amanda and Bindel, David}, title = {Pseudospectral bounds on transient growth for higher order and constant delay differential equations}, month = nov, year = {2016}, arxiv = {1611.05130}, link = {http://arxiv.org/pdf/1611.05130}, status = {unrefereed}, submit = {Submitted to SIAM Journal on Matrix Analysis and Applictions.} }

C. Ponce and D. Bindel, “FLiER: Practical Topology Update Detection Using Sparse PMUs,” Jul. 2016. Accepted by IEEE Transactions on Power Systems.
@techreport{2016fliertr, author = {Ponce, Colin and Bindel, David}, title = {{FLiER}: Practical Topology Update Detection Using Sparse {PMU}s}, month = jul, year = {2016}, arxiv = {1409.6644}, link = {http://arxiv.org/pdf/1409.6644v3}, code = {https://github.com/cponce512/FLiER_Test_Suite/}, status = {unrefereed}, submit = {Accepted by IEEE Transactions on Power Systems.} }
Abstract:
In this paper, we present a Fingerprint Linear Estimation Routine (FLiER) to identify topology changes in power networks using readings from sparselydeployed phasor measurement units (PMUs). When a power line, load, or generator trips in a network, or when a substation is reconfigured, the event leaves a unique “voltage fingerprint” of bus voltage changes that we can identify using only the portion of the network directly observed by the PMUs. The naive bruteforce approach to identify a failed line from such voltage fingerprints, though simple and accurate, is slow. We derive an approximate algorithm based on a local linearization and a novel filtering approach that is faster and only slightly less accurate. We present experimental results using the IEEE 57bus, IEEE 118bus, and Polish 19992000 winter peak networks.

J. Chadwick and D. Bindel, “An Efficient Solver for Sparse Linear Systems Based on RankStructured Cholesky Factorization,” Jul. 2015.
@techreport{2015rsc, author = {Chadwick, Jeffrey and Bindel, David}, title = {An Efficient Solver for Sparse Linear Systems Based on RankStructured {Cholesky} Factorization}, month = jul, year = {2015}, arxiv = {1507.05593}, link = {http://arxiv.org/pdf/1507.05593}, code = {https://github.com/jeffchadwick/rank_structured_cholesky}, status = {unrefereed} }
Abstract:
Direct factorization methods for the solution of large, sparse linear systems that arise from PDE discretizations are robust, but typically show poor time and memory scalability for large systems. In this paper, we describe an efficient sparse, rankstructured Cholesky algorithm for solution of the positive definite linear system Ax=b when A comes from a discretized partialdifferential equation. Our approach combines the efficient memory access patterns of conventional supernodal Cholesky algorithms with the memory efficiency of rankstructured direct solvers. For several test problems arising from PDE discretizations, our method takes less memory than standard sparse Cholesky solvers and less wallclock time than standard preconditioned iterations.

D. Bindel and A. Hood, “Localization Theorems for Nonlinear Eigenvalues,” Aug. 2013. Appeared in SIAM Journal on Matrix Analysis and Applications in 2013.
@techreport{2013nep, author = {Bindel, David and Hood, Amanda}, title = {Localization Theorems for Nonlinear Eigenvalues}, month = aug, year = {2013}, arxiv = {1303.4668}, link = {http://arxiv.org/pdf/1303.4668}, status = {unrefereed}, submit = {Appeared in SIAM Journal on Matrix Analysis and Applications in 2013.} }
Abstract:
Let $T : \Omega \rightarrow {\Bbb C}^{n \times n}$ be a matrixvalued function that is analytic on some simplyconnected domain $\Omega \subset {\Bbb C}$. A point $\lambda \in \Omega$ is an eigenvalue if the matrix $T(\lambda)$ is singular. In this paper, we describe new localization results for nonlinear eigenvalue problems that generalize Gershgorin’s theorem, pseudospectral inclusion theorems, and the BauerFike theorem. We use our results to analyze three nonlinear eigenvalue problems: an example from delay differential equations, a problem due to Hadeler, and a quantum resonance computation.

W. He, D. Bindel, and S. Govindjee, “Topology Optimization in Micromechanical Resonator Design,” Structural Engineering Mechanics and Materials, Department of Civil and Environmental Engineering, University of California, Berkeley, UCB/SEMM2009/04, Dec. 2009. Appeared in Optimization and Engineering in 2012
@techreport{2009topology, author = {He, Wei and Bindel, David and Govindjee, Sanjay}, title = {Topology Optimization in Micromechanical Resonator Design}, number = {UCB/SEMM2009/04}, institution = {Structural Engineering Mechanics and Materials, Department of Civil and Environmental Engineering, University of California, Berkeley}, month = dec, year = {2009}, status = {unrefereed}, submit = {Appeared in Optimization and Engineering in 2012} }
Abstract:
A topology optimization problem in microelectromechanical resonator design is addressed in this paper. The design goal is to control the first several eigenfrequencies of a microelectromechanical resonator using topology optimization in order to improve the resonator’s quality of resonance. The design variable is the distribution of mass in a constrained domain which we model via (1) the Simple Isotropic Material with Penalization Model and (2) the Peak Function Model. The overall optimization problem is solved using the Method of Moving Asymptotes and a Genetic Algorithm combined with a local gradient method. A numerical example is presented to highlight the features of the methods in more detail. The advantages and disadvantages of each method are discussed.

D. Bindel, “Structured and ParameterDependent Eigensolvers for SimulationBased Design of Resonant MEMS,” PhD thesis, University of California, Berkeley, 2006. Appears as Tech Report EECS2006109.
2008 Householder Award (best NLA thesis over three years)@phdthesis{2006dissertation, author = {Bindel, David}, title = {Structured and ParameterDependent Eigensolvers for SimulationBased Design of Resonant {MEMS}}, school = {University of California, Berkeley}, month = aug, year = {2006}, status = {unrefereed}, submit = {Appears as Tech Report EECS2006109.}, notable = {2008 Householder Award (best NLA thesis over three years)} }
Abstract:
This dissertation is about computational tools to aid in the design of resonant MicroElectroMechanical Systems (MEMS), tiny vibrating devices built by processes like those used to make integrated circuits. Vibrating MEMS are used in accelerometers and gyroscopes, in sensors to detect chemicals and to measure pressure, and in communication devices such as cell phones. MEMS engineers can use computer simulations to design devices using fewer costly and timeconsuming prototype tests, but these simulations are only as useful as the models on which they are built. In this work, we contribute new mathematical models, numerical methods, and software tools to simulate resonant MEMS, and apply these tools to analyze specific devices. We describe physical models of damped vibrations of MEMS, including anchor loss and thermoelastic effects which are widely recognized as important, but not modeled in generality by existing tools. Though the resulting systems of equations are large and nonHermitian, and depend nonlinearly on frequency, we use the equation structure to develop efficient structured Krylov subspace projection methods for computing free vibrations and reducedorder models. We also provide efficient continuation methods for recomputing eigendecompositions under changes to design parameters or operating conditions. Our models and analysis methods are integrated into HiQLab, a new finite element tool with a particularly flexible architecture which we have designed. Using HiQLab, we simulate example resonator designs, and compare our results to laboratory measurements. Our simulations reveal a previouslyunknown mode interference phenomenon, subsequently observed in experiments, which dramatically affects the amount of damping near certain critical values of geometric parameters.

D. Bindel and J. Demmel, “Continuation of Invariant Subspaces for Large Bifurcation Problems,” UC Berkeley Computer Science Division, EECS200613, Feb. 2006. Appeared in SIAM Journal on Scientific Computing in 2008.
@techreport{2006cis, author = {Bindel, David and Demmel, James}, title = {Continuation of Invariant Subspaces for Large Bifurcation Problems}, number = {EECS200613}, institution = {UC Berkeley Computer Science Division}, month = feb, year = {2006}, status = {unrefereed}, submit = {Appeared in SIAM Journal on Scientific Computing in 2008.} }
Abstract:
We summarize an algorithm for computing a smooth orthonormal basis for an invariant subspace of a parameterdependent matrix, and describe how to extend it for numerical bifurcation analysis. We adapt the continued subspace to track behavior relevant to bifurcations, and use projection methods to deal with large problems. To test our ideas, we have integrated our code into MATCONT, a program for numerical continuation and bifurcation analysis.

D. Bindel, S. Chandresekaran, J. Demmel, D. Garmire, and M. Gu, “A Fast and Stable Nonsymmetric Eigensolver for Certain Structured Matrices,” May 2005.
@techreport{2005compan, author = {Bindel, David and Chandresekaran, Shivkumar and Demmel, James and Garmire, David and Gu, Ming}, title = {A Fast and Stable Nonsymmetric Eigensolver for Certain Structured Matrices}, month = may, year = {2005}, status = {unrefereed} }
Abstract:
We consider the set of matrices which differ from symmetric, skew symmetric, or unitary by only a low rank modification. This class of matrices includes companion matrices, arrow matrices, and matrices corresponding to mechanical oscillators with localized damping. We show that Hessenberg and Schur forms for such matrices have semiseparable structure, and we use this fact to construct a backward stable eigensolver for such matrices which requires $O(n)$ space and runs in $O(n^2)$ time. We evaluate the performance and accuracy of our approach for several test problems, including the computation of all the roots of a polynomial or a matrix polynomial.

D. Bindel and S. Govindjee, “Elastic PMLs for Resonator Anchor Loss Simulation,” Structural Engineering Mechanics and Materials, Department of Civil and Environmental Engineering, University of California, Berkeley, UCB/SEMM2005/01, Feb. 2005. Appeared in International Journal on Numerical Methods in Engineering in 2005.
@techreport{2005pmltr, author = {Bindel, David and Govindjee, Sanjay}, title = {Elastic {PML}s for Resonator Anchor Loss Simulation}, number = {UCB/SEMM2005/01}, institution = {Structural Engineering Mechanics and Materials, Department of Civil and Environmental Engineering, University of California, Berkeley}, month = feb, year = {2005}, status = {unrefereed}, submit = {Appeared in International Journal on Numerical Methods in Engineering in 2005.} }
Abstract:
Electromechanical resonators and filters, such as quartz, ceramic, and surfaceacoustic wave devices, are important signalprocessing elements in communication systems. Over the past decade, there has been substantial progress in developing new types of miniaturized electromechanical resonators using microfabrication processes. For these microresonators to be viable they must have high and predictable quality factors ($Q$). Depending on scale and geometry, the energy losses that lower $Q$ may come from material damping, thermoelastic damping, air damping, or radiation of elastic waves from an anchor. Of these factors, anchor losses are the least understood because such losses are due to a complex radiation phenomena in a semiinfinite elastic halfspace. Here, we describe how anchor losses can be accurately computed using an absorbing boundary based on a perfectly matched layer (PML) which absorbs incoming waves over a wide frequency range for any nonzero angle of incidence. We exploit the interpretation of the PML as a complexvalued change of coordinates to illustrate how one can come to a simpler finite element implementation than was given in its original presentations. We also examine the convergence and accuracy of the method, and give guidelines for how to choose the parameters effectively. As an example application, we compute the anchor loss in a micro disk resonator and compare it to experimental data. Our analysis illustrates a surprising modemixing phenomenon which can substantially affect the quality of resonance.

Y. Chen, D. Bindel, H. Song, and R. Katz, “TomographyBased Overlay Network Monitoring,” UC Berkeley Computer Science Division, CSD031252, Jun. 2003. Appeared in SIGCOMM IMC 2003
@techreport{2003tomographytr, author = {Chen, Yan and Bindel, David and Song, Hanhee and Katz, Randy}, title = {TomographyBased Overlay Network Monitoring}, number = {CSD031252}, institution = {UC Berkeley Computer Science Division}, month = jun, year = {2003}, status = {unrefereed}, submit = {Appeared in SIGCOMM IMC 2003} }
Abstract:
Overlay network monitoring enables distributed Internet applications to detect and recover from path outages and periods of degraded performance within seconds. For an overlay network with $n$ end hosts, existing systems either require $O(n^2)$ measurements, and thus lack scalability, or can only estimate the latency but not congestion or failures. Unlike other network tomography systems, we characterize endtoend losses (this extends to any additive metrics, including latency) rather than individual link losses. We find a minimal basis set of $k$ linearly independent paths that can fully describe all the $O(n^2)$ paths. We selectively monitor and measure the loss rates of these paths, then apply them to estimate the loss rates of all other paths. By extensively studying synthetic and real topologies, we find that for reasonably large n (e.g., 100), $k$ is only in the range of $O(n \log n)$. This is explained by the moderately hierarchical nature of Internet routine.Our scheme only assumes the knowledge of underlying IP topology, and any link can become lossy or return to normal. In addition, our technique is tolerant to topology measurement inaccuracies, and is adaptive to topology changes.

D. Bindel, J. Demmel, W. Kahan, and O. Marques, “On Computing Givens Rotations Reliable and Efficiently,” LAPACK Working Notes, 128, Jan. 2001. Appeared in ACM Transactions on Mathematical Software in 2002.
@techreport{2001givens, author = {Bindel, David and Demmel, James and Kahan, William and Marques, Osni}, title = {On Computing {Givens} Rotations Reliable and Efficiently}, institution = {LAPACK Working Notes}, number = {128}, month = jan, year = {2001}, status = {unrefereed}, submit = {Appeared in ACM Transactions on Mathematical Software in 2002.} }
Abstract:
We consider the efficient and accurate computation of Givens rotations. When $f$ and $g$ are positive real numbers, this simply amounts to computing the values of $c = f/\sqrt{f^2 + g^2}$, $s = g/\sqrt{f^2 + g^2}$, and $r = \sqrt{f^2 + g^2}$. This apparently trivial computation merits closer consideration for the following three reasons. First, while the definitions of $c$, $s$ and $r$ seem obvious in the case of two nonnegative arguments $f$ and $g$, there is enough freedom of choice when one or more of $f$ and $g$ are negative, zero or complex that LAPACK auxiliary routines SLARTG, CLARTG, SLARGV and CLARGV can compute rather different values of $c$, $s$ and $r$ for mathematically identical values of $f$ and $g$. To eliminate this unnecessary ambiguity, the BLAS Technical Forum chose a single consistent definition of Givens rotations that we will justify here. Second, computing accurate values of $c$, $s$ and $r$ as efficiently as possible and reliably despite over/underflow is surprisingly complicated. For complex Givens rotations, the most efficient formulas require only one real square root and one real divide (as well as several much cheaper additions and multiplications), but a reliable implementation using only working precision has a number of cases. On a Sun Ultra10, the new implementation is slightly faster than the previous LAPACK implementation in the most common case, and 2.7 to 4.6 times faster than the corresponding vendor, reference or ATLAS routines. It is also more reliable; all previous codes occasionally suffer from large inaccuracies due to over/underflow. For real Givens rotations, there are also improvements in speed and accuracy, though not as striking. Third, the design process that led to this reliable implementation is quite systematic, and could be applied to the design of similarly reliable subroutines.

J. Kubiatowicz, D. Bindel, Y. Chen, S. Czerwinski, P. Eaton, D. Geels, R. Gummadi, S. Rhea, H. Weatherspoon, W. Weimer, C. Wells, and B. Zhao, “OceanStore: An Architecture for GlobalScale Persistent Storage,” UC Berkeley Computer Science Division, CSD001102, Mar. 2000. Appeared in ASPLOS 2000.
@techreport{2000oceanstoretr, author = {Kubiatowicz, John and Bindel, David and Chen, Yan and Czerwinski, Steven and Eaton, Patrick and Geels, Dennis and Gummadi, Ramakrishna and Rhea, Sean and Weatherspoon, Hakim and Weimer, Westley and Wells, Chris and Zhao, Ben}, title = {{OceanStore}: An Architecture for GlobalScale Persistent Storage}, number = {CSD001102}, institution = {UC Berkeley Computer Science Division}, month = mar, year = {2000}, status = {unrefereed}, submit = {Appeared in ASPLOS 2000.} }
Abstract:
OceanStore is a utility infrastructure designed to span the globe and provide continuous access to persistent information. Since this infrastructure is comprised of untrusted servers, data is protected through redundancy and cryptographic techniques. To improve performance, data is allowed to be cached anywhere, anytime. Additionally, monitoring of usage patterns allows adaptation to regional outages and denial of service attacks; monitoring also enhances performance through proactive movement of data. A prototype implementation is currently under development.
External Talks
Colloquium and Seminar Talks

Model Reduction for EdgeWeighted Personalized PageRank
2017 Feb • Berkeley CS Colloquium
colloquium 
Nonlinear Eigenvalue Problems: Theory and Applications
2017 Jan • Berkeley Applied Math Seminar 
Model Reduction for EdgeWeighted Personalized PageRank
2016 Dec • NYU Numerical Analysis and Scientific Computing Seminar 
Fast Fingerprints for Power System Events
2016 Oct • Argonne National Lab 
Fast Fingerprints for Power System Events
2016 Aug • Lawrence Berkeley Lab 
Model Reduction for EdgeWeighted Personalized PageRank
2016 Apr • Purdue Computational and Applied Mathematics Seminar 
Model Reduction for EdgeWeighted Personalized PageRank
2016 Mar • Hong Kong Baptist University 
Nonlinear Eigenvalue Problems: Theory and Applications
2016 Mar • University of Arizona Math Colloquium
colloquium 
Model Reduction for EdgeWeighted Personalized PageRank
2015 Oct • Stanford LA/Opt Seminar 
Model Reduction for EdgeWeighted Personalized PageRank
2015 Oct • Berkeley Matrix Computations Seminar 
Music of the Microspheres
2014 Apr • Oxford University NA Seminar 
Music of the Microspheres
2014 Jan • UMCP NA Seminar 
Music of the Microspheres
2013 Nov • Seminar at UTRC 
Music of the Microspheres
2013 Oct • Tufts/Schlumberger Scientific Computing Seminar 
Computer Aided Design of MicroElectroMechanical Systems
2013 Apr • Civil Engineering Seminar at Duke 
Communities, Spectral Clustering, and Random Walks
2011 Nov • University of Chicago Scientific Computing Seminar 
Matrix Factorizations for Computer Network Tomography
2011 Apr • NYU NA Seminar 
Applications and Analysis of Nonlinear Eigenvalue Problems
2009 Nov • Simon Fraser University NA Seminar 
ComputerAided Design for MicroElectroMechanical Systems
2008 Nov • Stanford LA/Opt Seminar 
ComputerAided Design for MicroElectroMechanical Systems
2008 Nov • MIT Applied Math Colloquium
colloquium 
Bounds and Error Estimates for Nonlinear Eigenvalue Problems
2008 Oct • Berkeley Applied Math Seminar 
ComputerAided Design for MicroElectroMechanical Systems
2008 Feb • McGill NA Seminar 
ComputerAided Design for MicroElectroMechanical Systems
2008 Jan • Rice University Applied Math Colloquium
colloquium 
ComputerAided Design for MicroElectroMechanical Systems
2007 Nov • Temple University NA Seminar 
ComputerAided Design for MicroElectroMechanical Systems
2007 Nov • Cornell CS Colloquium
colloquium 
ComputerAided Design for MicroElectroMechanical Systems
2007 Mar • Columbia Applied Math Colloquium
colloquium 
Spectral Inclusion Regions for Bifurcation Analysis
2006 Aug • Stanford NA Seminar 
ComputerAided Design for MicroElectroMechanical Systems
2006 Apr • Purdue CS 
ComputerAided Design for MicroElectroMechanical Systems
2006 Apr • CU Boulder CS Colloquium
colloquium 
ComputerAided Design for MicroElectroMechanical Systems
2006 Mar • UC Davis CS Colloquium
colloquium 
ComputerAided Design for MicroElectroMechanical Systems
2006 Feb • Penn State University 
ComputerAided Design for MicroElectroMechanical Systems
2006 Feb • Caltech CS Colloquium
colloquium 
ComputerAided Design for MicroElectroMechanical Systems
2006 Jan • Sandia National Labs 
ComputerAided Design of MEMS
2004 Nov • NYU Numerical Analysis Seminar 
SUGAR: A MEMS Simulation Program
2002 Jun • Sun Microsystems 
Simulating MicroElectroMechanical Systems
2002 Mar • UC Davis
Workshop and Conference Talks

Scalable Algorithms for KernelBased Surrogates in Prediction and Optimization
2017 Nov • Workshop on Surrogate Models and Coarsening Techniques, UCLA IPAM
invited 
Dynamics via Nonlinear Pseudospectra
2017 Jul • Foundations of Computational Math 2017
minisymposium invited 
Stochastic estimators in Gaussian process kernel learning
2017 Jun • Householder Symposium
invited poster 
An Efficient Solver for Sparse Linear Systems based on RankStructured Cholesky Factorization
2017 Mar • SIAM CSE 2017
minisymposium invited 
An Efficient Solver for Sparse Linear Systems based on RankStructured Cholesky Factorization
2016 Mar • TSIMF Workshop on Structured Matrix Computations with Applications
invited 
Grumbles of a Numerical Analyst
2015 Dec • Dagstuhl Seminar on Approximate and Probabilistic Computing
invited 
An Efficient Solver for Sparse Linear Systems based on RankStructured Cholesky Factorization
2015 Oct • SIAM LA 2015
minisymposium invited 
Localizing Nonlinear Eigenvalue Problems: Theory and Applications
2015 Oct • SIAM LA 2015 (Prize Lecture)
invited plenary 
EdgeWeighted Personalized PageRank: Breaking a DecadeOld Performance Barrier
2015 Aug • KDD 2015 (poster session)
poster 
FLiER: Practical Topology Error Correction Using Sparse PMUs
2015 Feb • ARPAe Innovation Summit, National Harbor, MD
poster 
An Efficient Solver for Sparse Linear Systems based on RankStructured Cholesky Factorization
2013 Jul • Workshop on Forty Years of Nested Dissection, University of Waterloo

Some perturbation theorems for nonlinear eigenvalue problems
2013 Jan • Workshop on Dissipative Spectral Theory, Cardiff
invited 
Computer Aided Design of MicroElectroMechanical Systems
2012 Dec • SCMS Workshop on Recent Advances in Scientific Computing, Fudan University
invited 
Computer Aided Design of MicroElectroMechanical Systems
2012 Dec • FIST Workshop at Shanghai Tech
invited 
Matrix Factorizations for Computer Network Tomography
2011 Jul • Householder Symposium
invited plenary 
Integrating Multiphysics and Multiscale Modeling Environment Together
2011 May • DSRC Meeting, Alexandria
invited 
Resonances: Interpretation, Computation, and Perturbation
2010 Jul • Workshop in honor of Pete Stewart at UT Austin
invited 
StructurePreserving Model Reduction for MEMS Modeling
2010 Jul • SIAM Annual Meeting
minisymposium invited 
Finite Element Software for Bone Deformation and Failure
2010 Apr • BTHSCA1 Workshop, UCLA IPAM
invited 
Bounds and Error Estimates for Resonance Problems
2009 Jul • SIAM Annual Meeting
minisymposium invited 
ComputerAided Design for MicroElectroMechanical Systems
2008 Jun • Householder Symposium (Householder Award Talk)
invited plenary 
Error Bounds and Error Estimates for Nonlinear Eigenvalue Problems
2008 Jun • Householder Symposium
minisymposium invited 
Numerical and SemiAnalytical StructurePreserving Model Reduction for MEMS
2007 Dec • DARPA MEMS/NEMS Workshop
invited 
Numerical and SemiAnalytical StructurePreserving Model Reduction for MEMS
2007 Sep • ICIAM
minisymposium invited 
Structure Preserving Model Reduction for Damped Resonant MEMS
2007 Jul • USNCCM
minisymposium invited 
Numerical and SemiAnalytical StructurePreserving Model Reduction for MEMS
2007 Jul • ICIAM
minisymposium invited 
Model Reduction and Mode Computation for Damped Resonant MEMS
2007 Feb • SIAM CSE
minisymposium invited 
Elastic PMLs for Resonator Anchor Loss Simulation
2005 Jul • US National Conference on Computational Mechanics
minisymposium invited 
Continuation of Invariant Subspaces of Sparse ParameterDependent Matrices
2005 May • Householder Symposium
invited plenary 
Fast Hessenberg QR Iteration for Companion Matrices
2004 Jul • SIAM Annual Meeting
minisymposium invited 
Fast QR Iteration for Companion Matrices
2003 Jul • SIAM Linear Algebra Meeting
minisymposium invited
Software
PySOT  Python Surrogate Optimization Toolbox 
POAP  Python for Optimization with Asynchronous Plumbing 
GraphDoS  Analyzing graphs based on global and local Density of States 
RSC  Rankstructured Cholesky for fast PDE solves 
AxFEM  Fast simulation of nearaxisymmetric resonant MEMS 
MatScat  1D scattering and resonance computation in MATLAB 
BoneFEA  Finite element analysis of human bones 
MATFEAP  MATLAB interfaces to the FEAP finite element code 
MWrap  A gateway language for mixing MATLAB and C 
Matexpr  A MATLABlike minilanguage for fast inner loops in C 
HiQLab  Finite element analysis of damping in highfrequency MEMS 
SUGAR  Systemlevel simulation software for MEMS 
CLAPACK 3.0  C interfaces to the LAPACK linear algebra library 
Teaching
S18:  CS 6241  Numerical Methods for Data Science 
F17:  CS 5220  Applications of Parallel Computers 
S17:  CS 4220/5223 / MATH 4260  Numerical Analysis: Linear and Nonlinear Problems 
F16:  CS 6210  Matrix Computations 
S16:  CS 4220/5223 / MATH 4260  Numerical Analysis: Linear and Nonlinear Problems 
F15:  CS 5220  Applications of Parallel Computers 
S15:  CS 4220/5223 / MATH 4260  Numerical Analysis: Linear and Nonlinear Problems 
S14:  CS 5220  Applications of Parallel Computers 
F13:  CS 6210  Matrix Computations 
F12:  CS 6210  Matrix Computations 
S12:  CS 3220  Introduction to Scientific Computing 
F11:  CS 5220  Applications of Parallel Computers 
S11:  CS 3220  Introduction to Scientific Computing 
S10:  CS 5220  Applications of Parallel Computers 
F09:  CS 6210  Matrix Computations 
S09:  NYU G22.2112  Scientific Computing 
F08:  NYU G22.2945  High Performance Scientific Computing 
S08:  NYU V63.0222  Honors Calculus II 
F07:  NYU V63.0233  Theory of Probability 
S07:  NYU V63.0222  Honors Calculus II 
F06:  NYU V55.0101  Quantitative Reasoning: Mathematical Patterns in Nature 
F05:  Berkeley CS 164  Compilers and Programming Languages (TA for Richard Fateman) 
F01:  Berkeley CS 267  Applications of Parallel Computers (TA for Kathy Yelick) 
Societies
Member  SIAM  (Society for Industrial and Applied Mathematics) 
Member  AMS  (American Mathematical Society) 
Member  ACM  (Association for Computing Machinery) 
Member  IEEE  (Institute of Electrical and Electronics Engineers) 
Service
External Activities
Local Activities
20172018  External committee member  ECE/CAM Faculty Recruiting Committee 
20172018  Committee member  CS Chair Search Committee 
20172018  Committee chair  CS Graduate Admissions Committee 
20172017  Committee member  CS Colloquium Committee 
20172017  Committee Member  Applied Math Graduate Admissions Committee 
20162017  Committee member  CS Faculty Recruiting Committee 
20152016  Committee member  CS Graduate Admissions 
2015  Committee member  Applied Math Curriculum Review Committee 
2014  Judge  BigRed Hacks 
20132014  Committee member  Applied Math Graduate Admissions 
20112012  Committee member  Applied Math Graduate Admissions 
20112014  Committee member  Cornell Faculty Advisory Board on Information Technology 
20102011  Committee member  CS Graduate Admissions 
20102011  Committee member  Applied Math Graduate Admissions 
20092010  Committee member  CS Graduate Admissions 
20092010  Committee member  Applied Math Graduate Admissions 
2009present  Organizer  Cornell Scientific Computing and Numeric Seminar 
Review Activity
ACM Journal on Emerging Technologies in Computing Systems  2014 
ACM Transactions on Mathematical Software  2017 2016 2015 2014 2013 
American Mathematical Monthly  2015 
SIAM Journal on Applied Mathematics  2016 
SIAM Journal on Matrix Analysis  2015 2014 2012 2009 2008 2007 2006 2005 
SIAM Journal on Multiscale Modeling and Simulation  2012 
SIAM Journal on Scientific Computing  2017 2016 2015 2014 2009 2008 
IEEE Sensors  2014 
IEEE Transactions on Dependable and Secure Computing  2014 
IEEE Journal of Microelectromechanical Systems  2011 2010 2009 2008 2007 2003 
IEEE Transactions on Signal Processing  2007 
Applicable Analysis  2007 
Applied Mathematics and Computation  2017 2011 
Communications in Pure and Applied Math  2010 
International Journal of Computer Mathematics  2012 
International Journal of Solids and Structures  2015 
Journal of Applied Mechanics  2007 
Journal of Applied Physics  2007 
Journal of Computational Physics  2016 2015 2012 2011 
Journal of Micromechanics and Microengineering  2017 2016 2015 2014 2011 2009 2008 2007 
Journal of Machine Learning Research  2016 
Journal of Physics A: Mathematical and Theoretical  2007 
Linear Algebra and its Applications  2017 2015 2014 2013 2010 2009 2003 
Mathematics of Computation  2007 
Multiscale Modeling and Simulation  2013 
Numerical Linear Algebra with Applications  2017 2016 2015 2014 2013 2012 2011 2010 
Numerische Mathematik  2011 2009 
Transactions of the Canadian Society for Mechanical Engineering  2009 
DSL 2011: IFIP Working Conference on DomainSpecific Languages  2011 
PARA04 conference proceedings  2004 
IEEE ARITH conference  2004 
ACM International Conference on Supercomputing  2003 
ACM SIGGRAPH  2011 2009 
Proposal referee for the Netherlands science foundation (NWO)  2003 
Proposal referee for DOE  2015 2009 
Proposal referee for NSF  2018 2017 2016 2012 
Proposal referee for NASA  2017 
Students
PhD students
David Eriksson Applied Math 
Surrogate optimization methods
Coadvised (secondary advisor: Christine Shoemaker) 
Kun Dong Applied Math 
Spectral graph analysis 
Eric Lee Computer Science 
Analysis of power grids 
Moontae Lee Computer Science 
Spectral methods for topic models
Coadvised (primary advisor: David Mimno) 
Amanda Hood Applied Math Ph.D., 2017 
Localizing the eigenvalues of matrixvalued functions: analysis and applications 
Colin Ponce Computer Science Ph.D., 2016 
NetworkStructured Error Flattening for Power Grids and Other RealWorld Networks 
Erdal Yilmaz Applied Physics Ph.D., 2016 
Design, Analysis and Simulation of Microscale SolidWave Gyroscopes
Research advisor (formally advised by Richard Lovelace) 
Masters students
Bingqing Ma Computer Science M.Eng., 2018 
Web Interface to a Finite Element Analysis Program 
Alvin Zhu Computer Science M.Eng., 2018 
Fast nonnegative projection of low rank matrices 
Tommy Shum Computer Science M.Eng., 2018 
PySOT in the Cloud 
Peiyu Shi Computer Science M.Eng., 2018 
A web dashboard for PySOT 
Israr Mahmood Computer Science M.Eng., 2018 
A web dashboard for PySOT 
Daniel Liu Computer Science M.Eng., 2017 
Bayesian optimization in PySOT 
Han Wen Chen Computer Science M.Eng., 2017 
Jupyter Notebooks for Finite Element Analysis 
Michael Ficenic Computer Science M.Eng., 2017 
Network Classification via Spectral Features 
Paul West Computer Science M.Eng., 2017 
Optimization with PreEmptible VMs 
Joel Lubitinsky Computer Science M.Eng., 2017 
ResourceCoupled Evolutionary Games 
IoanaMaria Tamas Computer Science M.Eng., 2017 
ResourceCoupled Evolutionary Games 
Batu Inal Computer Science M.Eng., 2016 
Super Seminar Scraper 
Sania Nagpal Computer Science M.Eng., 2016 
Fast Trial Spaces for Parameterized PageRank Problems 
Suarabh Netravalkar Computer Science M.Eng., 2016 
Fast Trial Spaces for Parameterize PageRank Problems 
Shitong Jia Computer Science M.Eng., 2016 
EtchaSketch 3D 
Jing Jing Computer Science M.Eng., 2016 
Super Seminar Scraper 
Jiankun Lu Computer Science M.Eng., 2016 
Super Seminar Scraper 
Xiangyu Zhang Computer Science M.Eng., 2016 
EdgeWeighted Parameterized PageRank: A Demo 
Markus Salasoo Computer Science M.Eng., 2016 
EdgeWeighted Parameterized PageRank: A Demo 
Ziyang Tang Computer Science M.Eng., 2016 
Optimizing Price of Anarchy in a Model of Opinion Formation 
Jia Zhang Computer Science M.Eng., 2016 
Spectral Histograms on Networks 
Xiaoan Yan Computer Science M.Eng., 2015 
EdgeWeighted Parameterized PageRank: A Demo 
Chen TingHao Electrical Engineering M.Eng., 2013 
MEMS Simulation as a Service 
Syed Hassan Computer Science M.Eng., 2013 
MEMS Simulation as a Service 
Kim Young Jae Computer Science M.Eng., 2013 
Teaching Support Vector Machines to Predict Profitable Stock Offers 
Jungmin Yun Computer Science M.Eng., 2012 
Python Implementation of a Stochastic RBF Optimization Method 
Jesseon Chang Computer Science M.Eng., 2012 
Python Implementation of a Stochastic RBF Optimization Method 
ChenYi Chen Computer Science M.Eng., 2012 
A Flexible Interface to FEAP 
Scott Purdy Computer Science M.Eng., 2010 
Process Replication for HPC Applications 
Peter Hunt Computer Science M.Eng., 2010 
Process Replication for HPC Applications 
Silvio Tarca Scientific Computing (NYU) M.S., 2010 
Performance Optimization of Symmetric Factorization Algorithms 
Undergraduate students
Nathaniel Rogalskyj  Identifying Network Changes from Ringdown Analysis (2016) 
Anna Yesypenko  Graph Analysis via Density of States (2016) 
Moteleolu Onabajo  Graph Analysis via Density of States (2016) 
Jianqiu Wang  Graph Analysis via Density of States (2016) 
Humam Alwassel  Automated Floating Point Error Analysis (2015) 
Patrick Chen  Super Seminar Scraper (201516) 
Jooyoung Park  Maximum Entropy Method Implementation in MATLAB (2015) 
Sheroze Sherifdeen  MatScat for Python (201516) 
Nimit Sohoni  Review of the FEAST Eigensolver (2015) 
Leon Davis  Diagonal Completion for LowRank Matrices (2015) 
Greg Rosenthal  PageRank with Random Edge Weights (2015) 
Eric Ma  Graph Analysis via Spectral Histograms (2015) 
Brandon Hartz  Fast PageRank on ParameterDependent Graphs (2014) 
Marshall Jiang  Randomly Projected GMRES (201415) 
KyuYoung Kim  Evaluating Overlapping Community Detection via Matrix Factorizations (201112) 
Jiexun Xu  Fast Factorizations for Network Tomography (2008) 
Iva Vukicevic  Error Bounds and Estimates for a Discrete SineGordon Equation (2008) 
Daniel Parry  Bounds on Biased and Unbiased Random Walks (2008) 
Anwis Davis  MEMS Web Service (2002) 
Ernest Zhu  MEMS Web Service (2001) 
Wayne Kao  MEMS Web Service (2001) 
Thesis committees
Current
 Chris Browne (Applied Math)
 Gabriela Calinao Correa (Material Science)
 Yuan Cheng (Civil Engineering)
 Kun Dong (Applied Math)
 David Eriksson (Applied Math)
 Marc Gilles (Applied Math)
 Jiayi Guo (Operations Research)
 Matthew Hin (Applied Math)
 Shreyas Honrao (Material Science)
 Junteng Jia (Chemistry)
 Chaitali Joshi (Physics)
 Fujun Luan (Computer Science)
 Moontae Lee (Computer Science)
 Hubert Lin (Computer Science)
 Stephen McDowell (Computer Science)
 Enrique Rojas (Atmospheric Science)
 Zhengdi Shen (Applied Math)
 Qinru Shi (Applied Math)
 Yu Su (Chemical Engineering)
 Saul Toscano (Operations Research)
 Sheng Wang (Mechanical Engineering)
 Mengqi Xia (Computer Science)