Research Interests

Experience and Education

September 2022-August 2025 Collaboration Director, Simons Collaboration on Hidden Symmetries and Fusion Energy.
January 2021-December 2023 Associate Dean for DEI, Ann S. Bowers College of Computing and Information Science Cornell University
July 2020-June 2025 Director, Center for Applied Mathematics Cornell University
2023-present Professor of Computer Science Cornell University
2017-2023 Associate Professor of Computer Science Cornell University
Spring 2019 Visiting Scholar, Department of Statistics University of Chicago
Fall 2018 Faculty Research Participant Argonne National Laboratory
2009-2017 Assistant Professor of Computer Science Cornell University
2006-2009 Courant Instructor of Mathematics New York University
1999-2006 Ph.D. in Computer Science University of California, Berkeley
1995-1999 B.S. in Math and Computer Science University of Maryland, College Park

Awards

2024 SIAM Fellow
Recognition "For contributions in numerical linear algebra and its innovative use in broad areas of computational science and engineering."
2020 James and Mary Tien Excellence in Teaching Award
Highest award for teaching in Cornell's College of Engineering.
2019 KDD Best Research Paper Award
2018 Cornell COE Research Excellence Award
Awarded annually to two Cornell engineering professors at each level.
2018 ASPLOS Most Influential Paper Award 2018
Recognizes a historical ASPLOS paper that has had major influence on the field.
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

  1. M. Ruth and D. Bindel, “Finding Birkhoff Averages via Adaptive Filtering,” vol. 34, no. 12, p. 123109, Dec. 2024.
    @article{2024-chaos,
      author = {Ruth, Maximillian and Bindel, David},
      title = {Finding {Birkhoff} Averages via Adaptive Filtering},
      month = dec,
      year = {2024},
      arxiv = {2403.19003},
      volume = {34},
      number = {12},
      pages = {123109},
      doi = {10.1063/5.0215396}
    }
    

    Abstract:

    In many applications, one is interested in classifying trajectories of Hamiltonian systems as invariant tori, islands, or chaos. The convergence rate of ergodic Birkhoff averages can be used to categorize these regions, but many iterations of the return map are needed to implement this directly. Recently, it has been shown that a weighted Birkhoff average can be used to accelerate the convergence, resulting in a useful method for categorizing trajectories.

    In this paper, we show how a modified version the reduced rank extrapolation method (named Birkhoff RRE) can also be used to find optimal weights for the weighted average with a single linear least-squares solve. Using these, we classify trajectories with fewer iterations of the map than the standard weighted Birkhoff average. Furthermore, for the islands and invariant circles, a subsequent eigenvalue problem gives the number of islands and the rotation number. Using these numbers, we find Fourier parameterizations of invariant circles and islands. We show examples of Birkhoff RRE on the standard map and on magnetic field line dynamics.

  2. M. Wang, Y. Yang, D. Bindel, and K. He, “Streaming Local Community Detection Through Approximate Conductance,” IEEE Transactions on Big Data, vol. 10, pp. 12–22, Feb. 2024.
    @article{2024-ieee-big-data,
      author = {Wang, Meng and Yang, Yanhao and Bindel, David and He, Kun},
      title = {Streaming Local Community Detection Through Approximate Conductance},
      journal = {IEEE Transactions on Big Data},
      volume = {10},
      year = {2024},
      month = feb,
      pages = {12--22},
      doi = {10.1109/TBDATA.2023.3310251},
      arxiv = {2110.14972}
    }
    

    Abstract:

    Community is a universal structure in various complex networks, and community detection is a fundamental task for network analysis. With the rapid growth of network scale, networks are massive, changing rapidly and could naturally be modeled as graph streams. Due to the limited memory and access constraint in graph streams, existing non-streaming community detection methods are no longer applicable. This raises an emerging need for online approaches. In this work, we consider the problem of uncovering the local community containing a few query nodes in graph streams, termed streaming local community detection. This is a new problem raised recently that is more challenging for community detection and only a few works address this online setting. Correspondingly, we design an online single-pass streaming local community detection approach. Inspired by the “local” property of communities, our method samples the local structure around the query nodes in graph streams, and extracts the target community on the sampled subgraph using our proposed metric called the approximate conductance. Comprehensive experiments show that our method remarkably outperforms the streaming baseline on both effectiveness and efficiency, and even achieves similar accuracy comparing to the state-of-the-art non-streaming local community detection methods that use static and complete graphs.

  3. D. Bindel, M. Landreman, and M. Padidar, “Understanding Trade-offs in Stellarator Design with Multi-objective Optimization,” Journal of Plasma Physics, vol. 85, no. 5, p. 905890503, 2023.
    @article{2023-jpp,
      author = {Bindel, David and Landreman, Matt and Padidar, Misha},
      title = {Understanding Trade-offs in Stellarator Design with Multi-objective Optimization},
      journal = {Journal of Plasma Physics},
      volume = {85},
      number = {5},
      pages = {905890503},
      year = {2023},
      arxiv = {2304.08698},
      doi = {10.1017/S0022377823000788}
    }
    

    Abstract:

    In designing stellarators, any design decision ultimately comes with a trade-off. Improvements in particle confinement, for instance, may increase the burden on engineers to build more complex coils, and the tightening of financial constraints may simplify the design and worsen some aspects of transport. Understanding trade-offs in stellarator designs is critical in designing high performance devices that satisfy the multitude of physical, engineering, and financial criteria. In this study we show how multi-objective optimization (MOO) can be used to investigate trade-offs and develop insight into the role of design parameters. We discuss the basics of MOO, as well as practical solution methods for solving MOO problems. We apply these methods to bring insight into the selection of two common design parameters: the aspect ratio of an ideal magnetohydrodynamic equilibrium, and the total length of the electromagnetic coils.

  4. D. Bindel, M. Landreman, and M. Padidar, “Direct Optimization of Fast-Ion Confinement in Stellarators,” Plasma Physics and Controlled Fusion, vol. 65, p. 065012, 2023.
    @article{2023-ppcf,
      author = {Bindel, David and Landreman, Matt and Padidar, Misha},
      title = {Direct Optimization of Fast-Ion Confinement in Stellarators},
      journal = {Plasma Physics and Controlled Fusion},
      volume = {65},
      pages = {065012},
      year = {2023},
      arxiv = {2302.11369},
      doi = {10.1088/1361-6587/acd141}
    }
    

    Abstract:

    Confining energetic ions such as alpha particles is a prime concern in the design of stellarators. However, directly measuring alpha confinement through numerical simulation of guiding-center trajectories has been considered to be too computationally expensive and noisy to include in the design loop, and instead has been most often used only as a tool to assess stellarator designs post hoc. In its place, proxy metrics, simplified measures of confinement, have often been used to design configurations because they are computationally more tractable and have been shown to be effective. Despite the success of proxies, it is unclear what is being sacrificed by using them to design the device rather than relying on direct trajectory calculations. In this study, we optimize stellarator designs for improved alpha particle confinement without the use of proxy metrics. In particular, we numerically optimize an objective function that measures alpha particle losses by simulating alpha particle trajectories. While this method is computationally expensive, we find that it can be used successfully to generate configurations with low losses.

  5. X. Zhu, L. Huang, E. H. Lee, C. A. Ibrahim, and D. Bindel, “Bayesian Transformed Gaussian Processes,” Transactions on Machine Learning Research, 2023.
    @article{2023-tmlr,
      title = {Bayesian Transformed Gaussian Processes},
      author = {Zhu, Xinran and Huang, Leo and Lee, Eric Hans and Ibrahim, Cameron Alexander and Bindel, David},
      journal = {Transactions on Machine Learning Research},
      issn = {2835-8856},
      year = {2023},
      link = {https://openreview.net/forum?id=4zCgjqjzAv},
      arxiv = {2210.10973}
    }
    

    Abstract:

    The Bayesian transformed Gaussian (BTG) model, proposed by Kedem and Oliviera in 1997, was developed as a Bayesian approach to trans-Kriging in the spatial statistics community. In this paper, we revisit BTG in the context of modern Gaussian process literature by framing it as a fully Bayesian counterpart to the Warped Gaussian process that marginalizes out a joint prior over input warping and kernel hyperparameters. As with any other fully Bayesian approach, this treatment introduces prohibitively expensive computational overhead; unsurprisingly, the BTG posterior predictive distribution, itself estimated through high-dimensional integration, must be inverted in order to perform model prediction. To address these challenges, we introduce principled numerical techniques for computing with BTG efficiently using a combination of doubly sparse quadrature rules, tight quantile bounds, and rank-one matrix algebra to enable both fast model prediction and model selection. These efficient methods allow us to compute with higher-dimensional datasets and apply BTG with layered transformations that greatly improve its expressibility. We demonstrate that BTG achieves superior empirical performance over MLE-based models in the low-data regime —situations in which MLE tends to overfit.

  6. S. Glas, M. Padidar, A. Kellison, and D. Bindel, “Global Stochastic Optimization of Stellarator Coil Configurations,” Journal of Plasma Physics, vol. 88, no. 2, Apr. 2022.
    @article{2022-stellarator,
      author = {Glas, Silke and Padidar, Misha and Kellison, Ariel and Bindel, David},
      title = {Global Stochastic Optimization of Stellarator Coil Configurations},
      month = apr,
      year = {2022},
      volume = {88},
      number = {2},
      journal = {Journal of Plasma Physics},
      arxiv = {2110.07464},
      link = {https://doi.org/10.1017/S002237782200023X},
      doi = {10.1017/S002237782200023X}
    }
    

    Abstract:

    In the construction of a stellarator, the manufacturing and assembling of the coil system is a dominant cost. These coils need to satisfy strict engineering tolerances, and if those are not met the project could be canceled as in the case of the National Compact Stellarator Experiment (NCSX) project. Therefore, our goal is to find coil configurations that increase construction tolerances without compromising the performance of the magnetic field.

    In this paper, we develop a gradient-based stochastic optimization model which seeks robust stellarator coil configurations in high dimensions. In particular, we design a two-step method: first, we perform an approximate global search by a sample efficient trust-region Bayesian optimization; second, we refine the minima found in step one with a stochastic local optimizer. To this end, we introduce two stochastic local optimizers: BFGS applied to the Sample Average Approximation and Adam, equipped with a control variate for variance reduction. Numerical experiments performed on a W7-X-like coil configuration demonstrate that our global optimization approach finds a variety of promising local solutions at less than 0.1% of the cost of previous work, which considered solely local stochastic optimization.

  7. M. Pang, C. A. Shoemaker, and D. Bindel, “Early termination strategies with asynchronous parallel optimization in application to automatic calibration of groundwater PDE models,” Environmental Modelling and Software, vol. 147, p. 105237, Jan. 2022.
    @article{2022-ems,
      author = {Pang, Min and Shoemaker, Christine A. and Bindel, David},
      title = {Early termination strategies with asynchronous parallel optimization in application to automatic calibration of groundwater {PDE} models},
      month = jan,
      year = {2022},
      volume = {147},
      pages = {105237},
      journal = {Environmental Modelling and Software},
      doi = {10.1016/j.envsoft.2021.105237},
      link = {https://doi.org/10.1016/j.envsoft.2021.105237}
    }
    

    Abstract:

    Automatic calibration is widely used to estimate parameters in hydrological models. The main idea is to use optimization algorithms to minimize the discrepancy between field data and simulation prediction. This process involves iterative exchanges of a parameter set chosen by the optimization and simulation. However, for computationally expensive models, such as groundwater flow and transport models, the calibration process may be extremely computationally demanding. In this study, we introduce and demonstrate a new asynchronous parallel surrogate-assisted optimization algorithm with an early truncation feature and different knowledge extraction strategies (SO-AET-k). Results show that our asynchronous algorithm performs significantly better than the synchronous analogue (SO-SP), requiring only 40%–70% of the computation time to achieve the same averaged results. In addition, various knowledge extraction strategies of the asynchronous SO-AET-k are tested. In comparisons with two other algorithms, SCE-UA and APPSPACK, asynchronous SO-AET-k shows significantly better performance in terms of both efficiency and robustness.

  8. M. Xia, B. Walter, E. Michielssen, D. Bindel, and D. Marschner, “A wave optics based fiber scattering model,” ACM Transactions on Graphics, vol. 39, no. 6, p. 252.
    @article{2020-tog,
      author = {Xia, Mengqi and Walter, Bruce and Michielssen, Eric and Bindel, David and Marschner, David},
      title = {A wave optics based fiber scattering model},
      journal = {ACM Transactions on Graphics},
      month = dec,
      volume = {39},
      issue = {6},
      pages = {252},
      doi = {10.1145/3414685.3417841}
    }
    

    Abstract:

    Existing fiber scattering models in rendering are all based on tracing rays through fiber geometry, but for small fibers diffraction and interference are non-negligible, so relying on ray optics can result in appearance errors. This paper presents the first wave optics based fiber scattering model, introducing an azimuthal scattering function that comes from a full wave simulation. Solving Maxwell’s equations for a straight fiber of constant cross section illuminated by a plane wave reduces to solving for a 3D electromagnetic field in a 2D domain, and our fiber scattering simulator solves this 2.5D problem efficiently using the boundary element method (BEM). From the resulting fields we compute extinction, absorption, and far-field scattering distributions, which we use to simulate shadowing and scattering by fibers in a path tracer. We validate our path tracer against the wave simulation and the simulation against a measurement of diffraction from a single textile fiber. Our results show that our approach can reproduce a wide range of fibers with different sizes, cross sections, and material properties, including textile fibers, animal fur, and human hair. The renderings include color effects, softening of sharp features, and strong forward scattering that are not predicted by traditional ray-based models, though the two approaches produce similar appearance for complex fiber assemblies under many conditions.

  9. P. Shi, K. He, D. Bindel, and J. Hopcroft, “Krylov Subspace Approximation for Local Community Detection in Large Networks,” ACM Transactions on Knowledge Discovery from Data, Oct. 2019.
    @article{2019-tkdd,
      author = {Shi, Pan and He, Kun and Bindel, David and Hopcroft, John},
      title = {Krylov Subspace Approximation for Local Community Detection in Large Networks},
      journal = {ACM Transactions on Knowledge Discovery from Data},
      month = oct,
      year = {2019},
      doi = {10.1145/3340708},
      arxiv = {1712.04823}
    }
    

    Abstract:

    Community detection is an important information mining task to uncover modular structures in large networks. For increasingly common large network data sets, global community detection is prohibitively expensive, and attention has shifted to methods that mine local communities, i.e. identifying all latent members of a particular community from a few labeled seed members. To address such semi-supervised mining task, we systematically develop a local spectral subspace-based community detection method, called LOSP. We define a family of local spectral subspaces based on Krylov subspaces, and seek a sparse indicator for the target community via an $\ell_1$ norm minimization over the Krylov subspace. Variants of LOSP depend on type of random walks with different diffusion speeds, type of random walks, dimension of the local spectral subspace, and step of diffusions. The effectiveness of the proposed LOSP approach is theoretically analyzed based on Rayleigh quotients, and it is experimentally verified on a wide variety of real-world networks across social, production and biological domains, as well as on an extensive set of synthetic LFR benchmark datasets.

  10. M. A. Gilles, C. Earls, and D. Bindel, “A subspace pursuit method to infer refractivity in the marine atmospheric boundary layer,” IEEE Transactions on Geosciences and Remote Sensing, vol. 57, no. 8, pp. 5606–5617, Aug. 2019.
    @article{2019-subspace,
      author = {Gilles, Marc Aur\'ele and Earls, Christopher and Bindel, David},
      title = {A subspace pursuit method to infer refractivity in the marine atmospheric boundary layer},
      journal = {IEEE Transactions on Geosciences and Remote Sensing},
      volume = {57},
      number = {8},
      pages = {5606--5617},
      month = aug,
      year = {2019},
      arxiv = {1901.06432},
      doi = {10.1109/TGRS.2019.2900582}
    }
    

    Abstract:

    Inferring electromagnetic propagation characteristics within the marine atmospheric boundary layer (MABL) from data in real time is crucial for modern maritime navigation and communications. The propagation of electromagnetic waves is well modeled by a partial differential equation (PDE): a Helmholtz equation. A natural way to solve the MABL characterization inverse problem is to minimize what is observed and what is predicted by the PDE. However, this optimization is difficult because it has many local minima. We propose an alternative solution that relies on the properties of the PDE but does not involve solving the full forward model. Ducted environments result in an EM field which can be decomposed into a few propagating, trapped modes. These modes are a subset of the solutions to a Sturm-Liouville eigenvalue problem. We design a new objective function that measures the distance from the observations to a subspace spanned by these eigenvectors. The resulting optimization problem is much easier than the one that arises in the standard approach, and we show how to solve the associated nonlinear eigenvalue problem efficiently, leading to a real-time method.

  11. P. Shi, K. He, D. Bindel, and J. Hopcroft, “Locally-biased Spectral Approximation for Community Detection,” Knowledge-Based Systems, vol. 164, pp. 459–472, 2019.
    @article{2019-knosys,
      author = {Shi, Pan and He, Kun and Bindel, David and Hopcroft, John},
      title = {Locally-biased Spectral Approximation for Community Detection},
      journal = {Knowledge-Based Systems},
      volume = {164},
      pages = {459--472},
      year = {2019},
      doi = {10.1016/j.knosys.2018.11.012}
    }
    

    Abstract:

    We propose a Locally-Biased Spectral Approximation (LBSA) approach for identifying all latent members of a local community from very few seed members. To reduce the computation complexity, we first apply a fast random walk, personalized PageRank and heat kernel diffusion to sample a comparatively small subgraph covering almost all potential community members around the seeds. Then starting from a normalized indicator vector of the seeds and by a few steps of either Lanczos iteration or power 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 real-world datasets in various domains as well as synthetic datasets. Results show that the proposed method outperforms state-of-the-art 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.

  12. C. Ponce, D. Bindel, and P. Vassilevski, “A Nonlinear Algebraic Multigrid Framework for the Power Flow Equations,” SIAM Journal of Scientific Computing, vol. 40, no. 3, pp. B812–B833, 2018.
    @article{2018-sisc,
      author = {Ponce, Colin and Bindel, David and Vassilevski, Panayot},
      title = {A Nonlinear Algebraic Multigrid Framework for the Power Flow Equations},
      journal = {SIAM Journal of Scientific Computing},
      volume = {40},
      number = {3},
      pages = {B812--B833},
      year = {2018},
      doi = {10.1137/16M1109965}
    }
    

    Abstract:

    Multigrid is a highly scalable class of methods most often used for solving large linear systems. In this paper we develop a nonlinear algebraic multigrid framework for the power flow equations, a complex quadratic system of the form ${diag}({v})\overline{Y{v}}={s}$, where $Y$ is approximately a complex scalar rotation of a real graph Laplacian. This is a standard problem that needs to be solved repeatedly during power grid simulations. A key difference between our multigrid framework and typical multigrid approaches is the use of a novel multiplicative coarse-grid correction to enable a dynamic multigrid hierarchy. We also develop a new type of smoother that allows one to coarsen together the different types of nodes that appear in power grid simulations. In developing a specific multigrid method, one must make a number of choices that can significantly affect the method’s performance, such as how to construct the restriction and interpolation operators, what smoother to use, and how aggressively to coarsen. In this paper, we make simple but reasonable choices that result in a scalable and robust power flow solver. Experiments demonstrate this scalability and show that it is significantly more robust to poor initial guesses than current state-of-the-art solvers.

  13. 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{2018-tkdd,
      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 low-dimensional embedding that captures the nodes’ closeness in the local network structure. We show that Lemon’s performance in detecting communities is competitive with state-of-the-art 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 real-world 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.

  14. 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{2017-tps,
      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 = {4222--4232},
      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 sparsely-deployed 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 brute-force 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 57-bus, IEEE 118-bus, and Polish 1999- 2000 winter peak networks.

  15. E. Yilmaz and D. Bindel, “Temperature Sensitivity and Shape Optimization of Solid-State Wave Gyroscopes,” IEEE Sensors, vol. 16, no. 6, pp. 6213–6221, 2016.
    @article{2016-sensors,
      author = {Yilmaz, Erdal and Bindel, David},
      title = {Temperature Sensitivity and Shape Optimization of
                 Solid-State Wave Gyroscopes},
      journal = {IEEE Sensors},
      volume = {16},
      number = {6},
      pages = {6213--6221},
      year = {2016},
      doi = {10.1109/JSEN.2016.2580670}
    }
    

    Abstract:

    We analyze the change of angular gain and vibration frequency of solid-state 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.

  16. 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{2015-sirev,
      author = {Bindel, David and Hood, Amanda},
      title = {Localization Theorems for Nonlinear Eigenvalues},
      journal = {SIAM Review},
      publisher = {SIAM},
      volume = {57},
      number = {4},
      pages = {585--607},
      month = dec,
      year = {2015},
      notable = {SIGEST feature article.},
      doi = {10.1137/15M1026511}
    }
    

    Abstract:

    Let $T : \Omega \rightarrow {\Bbb C}^{n\times n}$ be a matrix-valued function that is analytic on some simply-connected 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 Bauer-Fike 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.

  17. 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{2015-geb,
      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 = {248--265},
      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 best-response 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?

  18. 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{2014-matcont,
      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 = {232--248},
      year = {2014},
      doi = {10.1016/j.cam.2013.10.034}
    }
    

    Abstract:

    The Continuation of Invariant Subspaces (CIS) algorithm produces a smoothly-varying basis for an invariant subspace R(s) of a parameter-dependent 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 of Cl_matcont to large-scale computations of bifurcations of equilibria. In this paper, we describe the algorithms and functionality of the resulting Matlab bifurcation package Cl_matcontL. The novel features include: new CIS-based, continuous, well-scaled test functions for codimension 1 and 2 bifurcations; detailed description of locators for large problems; and examples of bifurcation analysis in large sparse problems.

  19. 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{2013-simax,
      author = {Bindel, David and Hood, Amanda},
      title = {Localization Theorems for Nonlinear Eigenvalues},
      journal = {SIAM Journal on Matrix Analysis},
      volume = {34},
      number = {4},
      pages = {1728--1749},
      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 matrix-valued function that is analytic on some simply-connected 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 Bauer-Fike 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.

  20. 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{2013-blockgrace,
      author = {Xie, Wenlei and Wang, Guozhang and Bindel, David and Demers, Alan and Gehrke, Johannes},
      journal = {Proceedings of the VLDB Endowment},
      number = {14},
      pages = {2014--2025},
      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 high-level, high-performance 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 block-oriented 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 block-aware graph processing runtime that keeps the familiar vertex-centric programming paradigm while reaping the benefits of block-oriented execution. Our experiments show that block-oriented execution significantly improves the performance of our framework for several graph applications.

  21. W. He, D. Bindel, and S. Govindjee, “Topology Optimization in Micromechanical Resonator Design,” Optimization and Engineering, vol. 13, no. 2, 2012.
    @article{2012-mems-opt,
      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/s11081-011-9139-1}
    }
    

    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.

  22. Y. Zhao, Y. Chen, and D. Bindel, “Towards Unbiased End-to-End Network Diagnosis,” IEEE/ACM Transactions on Networking, vol. 17, no. 6, pp. 1724–1737, Dec. 2009.
    @article{2009-tons,
      author = {Zhao, Yao and Chen, Yan and Bindel, David},
      title = {Towards Unbiased End-to-End Network Diagnosis},
      journal = {IEEE/ACM Transactions on Networking},
      volume = {17},
      number = {6},
      pages = {1724--1737},
      month = dec,
      year = {2009},
      doi = {10.1109/TNET.2009.2022158}
    }
    

    Abstract:

    Internet fault diagnosis is extremely important for end-users, overlay network service providers (like Akamai ), and even Internet service providers (ISPs). However, because link-level properties cannot be uniquely determined from end-to-end 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 least-biased end-to-end network diagnosis (in short, LEND) system for inferring link-level 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 end-to-end 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 real-time even for reasonably large overlay networks. Finally, LEND can supplement existing statistical inference approaches and provide smooth tradeoff between diagnosis accuracy and granularity.

  23. 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{2008-cis,
      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 = {637--656},
      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 parameter-dependent 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.

  24. Y. Chen, D. Bindel, H. Song, B. Chavez, and R. Katz, “Algebra-Based Scalable Overlay Network Monitoring: Algorithms, Evaluation, and Applications,” ACM Transactions on Networking, vol. 15, no. 5, pp. 1084–1097, Oct. 2007.
    @article{2007-tons,
      author = {Chen, Yan and Bindel, David and Song, Hanhee and Chavez, Brian and Katz, Randy},
      title = {Algebra-Based Scalable Overlay Network Monitoring:
                 Algorithms, Evaluation, and Applications},
      journal = {ACM Transactions on Networking},
      volume = {15},
      number = {5},
      pages = {1084--1097},
      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, “Tomography-based 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.

  25. 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{2007-symmetry,
      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 = {107--117},
      month = aug,
      year = {2007},
      doi = {10.1007/s11005-007-0178-7}
    }
    

    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.

  26. 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{2005-ijnme,
      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 = {789--818},
      month = oct,
      year = {2005},
      doi = {10.1002/nme.1394}
    }
    

    Abstract:

    Electromechanical resonators and filters, such as quartz, ceramic, and surface-acoustic wave devices, are important signal-processing 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 micro-resonators 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 semi-infinite elastic half-space. 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 non-zero angle of incidence. We exploit the interpretation of the PML as a complex-valued 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 mode-mixing phenomenon which can substantially affect the quality of resonance.

  27. 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{2002-toms,
      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 = {206--238},
      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 Ultra-10, 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

  1. X. Zhu, K. Wu, N. Maus, J. R. Gardner, and D. S. Bindel, “Variational Gaussian Processes with Decoupled Conditionals,” in Advances in Neural Information Processing Systems 2023, 2023.
    @inproceedings{2023-neurips,
      author = {Zhu, Xinran and Wu, Kaiwen and Maus, Natalie and Gardner, Jacob R. and Bindel, David S.},
      title = {Variational Gaussian Processes with Decoupled Conditionals},
      booktitle = {Advances in Neural Information Processing Systems 2023},
      year = {2023},
      month = dec,
      link = {https://openreview.net/forum?id=nwK8UkK3uB}
    }
    

    Abstract:

    Variational Gaussian processes (GPs) approximate exact GP inference by using a small set of inducing points to form a sparse approximation of the true posterior, with the fidelity of the model increasing with additional inducing points. Although the approximation error in principle can be reduced through the use of more inducing points, this leads to scaling optimization challenges and computational complexity. To achieve scalability, inducing point methods typically introduce conditional independencies and then approximations to the training and test conditional distributions. In this paper, we consider an alternative approach to modifying the training and test conditionals, in which we make them more flexible. In particular, we investigate decoupling the parametric form of the predictive mean and covariance in the conditionals, and learn independent parameters for predictive mean and covariance. We derive new evidence lower bounds (ELBO) under these more flexible conditionals, and provide two concrete examples of applying the decoupled conditionals. Empirically, we find this additional flexibility leads to improved model performance on a variety of regression tasks and Bayesian optimization (BO) applications.

  2. A. E. Kellison, A. W. Appel, M. Tekriwal, and D. S. Bindel, “LAProof: A Library of Formal Proofs of Accuracy and Correctness for Linear Algebra Programs,” in Proceedings of the 30th IEEE International Symposium on Computer Arithhmetic (ARITH), 2023.
    @inproceedings{2023-arith,
      author = {Kellison, Ariel E. and Appel, Andrew W. and Tekriwal, Mohit and Bindel, David S.},
      title = {{LAProof}: A Library of Formal Proofs of Accuracy and Correctness for Linear Algebra Programs},
      booktitle = {Proceedings of the 30th IEEE International Symposium on Computer Arithhmetic (ARITH)},
      year = {2023},
      month = sep,
      link = {https://github.com/ak-2485/ak-2485.github.io/blob/master/laproof.pdf}
    }
    

    Abstract:

    The LAProof library provides formal machine-checked proofs of the accuracy of basic linear algebra operations: inner product using conventional multiply and add, inner product using fused multiply-add, scaled matrix-vector and matrix-matrix multiplications, and scaled vector and matrix addition. These proofs can connect to concrete implementations of low-level basic linear algebra subprograms; as a proof of concept we present a machine-checked correctness proof of a C function implementing compressed-row-storage (CRS) sparse matrix-vector multiplication. Our accuracy proofs are backward error bounds and mixed backward-forward error bounds that account for underflow, proved subject to no assumptions except a low-level formal model of IEEE-754 arithmetic. We treat low-order error terms concretely, not approximating as $O(u^2)$.

  3. M. Tekriwal, A. W. Appel, A. E. Kellison, J.-B. Jeannin, and D. S. Bindel, “Verified Correctness, Accuracy, and Convergence of a Stationary Iterative Linear Solver: Jacobi Method,” in Proceedings of the 16th Conference on Intelligent Computer Mathematics (CICM), 2023.
    @inproceedings{2023-cicm,
      author = {Tekriwal, Mohit and Appel, Andrew W. and Kellison, Ariel E. and Jeannin, Jean-Baptiste and Bindel, David S.},
      title = {Verified Correctness, Accuracy, and Convergence of a Stationary Iterative Linear Solver: Jacobi Method},
      booktitle = {Proceedings of the 16th Conference on Intelligent Computer Mathematics (CICM)},
      year = {2023},
      month = sep,
      link = {https://www.cs.princeton.edu/~appel/papers/jacobi.pdf}
    }
    

    Abstract:

    Solving a sparse linear system of the form $Ax=b$ is a common engineering task, e.g., as a step in approximating solutions of differential equations. Inverting a large matrix $A$ is often too expensive, and instead engineers rely on iterative methods, which progressively approximate the solution $x$ of the linear system in several iterations, where each iteration is a much less expensive (sparse) matrix-vector multiplication. We present a formal proof in the Coq proof assistant of the correctness, accuracy and convergence of one prominent iterative method, the Jacobi iteration. The accuracy and convergence properties of Jacobi iteration are well-studied, but most past analyses were performed in real arithmetic; instead, we study those properties, and prove our results, in floating point arithmetic. We then show that our results are properly reflected in a concrete implementation in the C language. Finally, we show that the iteration will not overflow, under assumptions that we make explicit. Notably, our proofs are faithful to the details of the implementation, including C program semantics and floating-point arithmetic.

  4. D. Qi, D. Bindel, and A. Vladimirsky, “Surveillance Evasion Through Bayesian Reinforcement Learning,” in Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, 2023, vol. 206, pp. 8448–8462.
    @inproceedings{2023-aistats,
      title = {Surveillance Evasion Through Bayesian Reinforcement Learning},
      author = {Qi, Dongping and Bindel, David and Vladimirsky, Alexander},
      booktitle = {Proceedings of The 26th International Conference on Artificial Intelligence and Statistics},
      pages = {8448--8462},
      year = {2023},
      editor = {Ruiz, Francisco and Dy, Jennifer and van de Meent, Jan-Willem},
      volume = {206},
      series = {Proceedings of Machine Learning Research},
      month = {25--27 Apr},
      publisher = {PMLR},
      arxiv = {2109.14811},
      link = {https://proceedings.mlr.press/v206/qi23a.html}
    }
    

    Abstract:

    We consider a task of surveillance-evading path-planning in a continuous setting. An Evader strives to escape from a 2D domain while minimizing the risk of detection (and immediate capture). The probability of detection is path-dependent and determined by the spatially inhomogeneous surveillance intensity, which is fixed but a priori unknown and gradually learned in the multi-episodic setting. We introduce a Bayesian reinforcement learning algorithm that relies on a Gaussian Process regression (to model the surveillance intensity function based on the information from prior episodes), numerical methods for Hamilton-Jacobi PDEs (to plan the best continuous trajectories based on the current model), and Confidence Bounds (to balance the exploration vs exploitation). We use numerical experiments and regret metrics to highlight the significant advantages of our approach compared to traditional graph-based algorithms of reinforcement learning.

  5. X. Zhu, J. Gardner, and D. Bindel, “Efficient Variational Gaussian Processes Initialization via Kernel-based Least Squares Fitting,” in Proceedings of NeurIPS 2022 Workshop on Gaussian Processes, Spatiotemporal Modeling, and Decision-making Systems, 2022.
    @inproceedings{2022-neurips,
      author = {Zhu, Xinran and Gardner, Jacob and Bindel, David},
      title = {Efficient Variational {Gaussian} Processes Initialization via Kernel-based Least Squares Fitting},
      month = dec,
      year = {2022},
      booktitle = {Proceedings of NeurIPS 2022 Workshop on Gaussian Processes, Spatiotemporal Modeling, and Decision-making Systems},
      link = {https://gp-seminar-series.github.io/neurips-2022/assets/camera_ready/35.pdf}
    }
    

    Abstract:

    Stochastic variational Gaussian processes (SVGP) scale Gaussian process inference to large datasets through inducing points and stochastic training. However, the training process involves hard multimodal optimization, and often suffers from slow and suboptimal convergence when initializing inducing points directly from training data. We provide a better initialization of inducing points from kernelbased least squares fitting. We show empirically that our approach consistently reaches better prediction performance. The total time cost of our method, including initialization, is comparable to the standard SVGP training.

  6. X. Zhu, Y. Liu, P. Ghysels, D. Bindel, and X. S. Li, “GPTuneBand: Multi-task and Multi-fidelity Autotuning for Large-scale High Performance Computing Applications,” in Proceedings of the SIAM Conference on Parallel Processing, 2022.
    @inproceedings{2022-siam-pp,
      author = {Zhu, Xinran and Liu, Yang and Ghysels, Pieter and Bindel, David and Li, Xiaoye S.},
      title = {{GPTuneBand}: Multi-task and Multi-fidelity Autotuning for Large-scale High Performance Computing Applications},
      booktitle = {Proceedings of the SIAM Conference on Parallel Processing},
      month = feb,
      year = {2022},
      link = {https://crd.lbl.gov/assets/Uploads/GPTuneBand.pdf}
    }
    

    Abstract:

    This work proposes a novel multi-task and multi-fidelity autotuning framework, GPTuneBand, for tuning large-scale expensive high performance computing (HPC) applications. GPTuneBand combines a multi-task Bayesian optimization algorithm with a multi-armed bandit strategy, well-suited for tuning expensive HPC applications such as numerical libraries, scientific simulation codes and machine learning (ML) models, particularly with a very limited tuning budget. Our numerical results show that compared to other stateof-the-art autotuners, which only allows single-task or single-fidelity tuning, GPTuneBand obtains significantly better performance for numerical libraries and simulation codes, and competitive validation accuracy for training ML models. When tuning the Hypre library with 12 parameters, GPTuneBand wins over its single-fidelity predecessor GPTune on 62.5% tasks, with a maximum speedup of 1.2x, and wins over a single-task, multi-fidelity tuner BOHB on 72.5% tasks. When tuning the MFEM library on large numbers of CPU cores, GPTuneBand obtains a 1.7x speedup when compared with the default code parameters.

  7. M. Padidar, X. Zhu, L. Huang, J. Gardner, and D. Bindel, “Scaling Gaussian Processes with Derivative Information Using Variational Inference,” in Proceedings of NeurIPS 2021, 2021.
    @inproceedings{2021-neurips,
      author = {Padidar, Misha and Zhu, Xinran and Huang, Leo and Gardner, Jacob and Bindel, David},
      title = {Scaling {Gaussian} Processes with Derivative Information Using Variational Inference},
      month = dec,
      year = {2021},
      booktitle = {Proceedings of NeurIPS 2021},
      link = {https://proceedings.neurips.cc/paper/2021/file/32bbf7b2bc4ed14eb1e9c2580056a989-Paper.pdf}
    }
    

    Abstract:

    Gaussian processes with derivative information are useful in many settings where derivative information is available, including numerous Bayesian optimization and regression tasks that arise in the natural sciences. Incorporating derivative observations, however, comes with a dominating $O(N^3 D^3)$ computational cost when training on $N$ points in $D$ input dimensions. This is intractable for even moderately sized problems. While recent work has addressed this intractability in the low-$D$ setting, the high-$N$, high-$D$ setting is still unexplored and of great value, particularly as machine learning problems increasingly become high dimensional. In this paper, we introduce methods to achieve fully scalable Gaussian process regression with derivatives using variational inference. Analogous to the use of inducing values to sparsify the labels of a training set, we introduce the concept of inducing directional derivatives to sparsify the partial derivative information of a training set. This enables us to construct a variational posterior that incorporates derivative information but whose size depends neither on the full dataset size $N$ nor the full dimensionality $D$. We demonstrate the full scalability of our approach on a variety of tasks, ranging from a high dimensional stellarator fusion regression task to training graph convolutional neural networks on Pubmed using Bayesian optimization. Surprisingly, we find that our approach can improve regression performance even in settings where only label data is available.

  8. M. Lee, S. Cho, K. Dong, D. Mimno, and D. Bindel, “On-the-Fly Rectification for Robust Large-Vocabulary Topic Inference,” in Proceedings of the 38th International Conference on Machine Learning, 2021, vol. 139, pp. 6087–6097.
    @inproceedings{2021-icml,
      author = {Lee, Moontae and Cho, Sungjun and Dong, Kun and Mimno, David and Bindel, David},
      title = {On-the-Fly Rectification for Robust Large-Vocabulary Topic Inference},
      booktitle = {Proceedings of the 38th International Conference on Machine Learning},
      pages = {6087--6097},
      volume = {139},
      month = jul,
      year = {2021},
      link = {http://proceedings.mlr.press/v139/lee21c.html}
    }
    

    Abstract:

    Across many data domains, co-occurrence statistics about the joint appearance of objects are powerfully informative. By transforming unsupervised learning problems into decompositions of co-occurrence statistics, spectral algorithms provide transparent and efficient algorithms for posterior inference such as latent topic analysis and community detection. As object vocabularies grow, however, it becomes rapidly more expensive to store and run inference algorithms on co-occurrence statistics. Rectifying co-occurrence, the key process to uphold model assumptions, becomes increasingly more vital in the presence of rare terms, but current techniques cannot scale to large vocabularies. We propose novel methods that simultaneously compress and rectify co-occurrence statistics, scaling gracefully with the size of vocabulary and the dimension of latent space. We also present new algorithms learning latent variables from the compressed statistics, and verify that our methods perform comparably to previous approaches on both textual and non-textual data.

  9. L. Huang, A. Graven, and D. Bindel, “Density of States Graph Kernels,” in Proceedings of the 2021 SIAM International Conference on Data Mining, 2021, pp. 289–297.
    @inproceedings{2021-sdm,
      author = {Huang, Leo and Graven, Andrew and Bindel, David},
      title = {Density of States Graph Kernels},
      booktitle = {Proceedings of the 2021 SIAM International Conference on Data Mining},
      pages = {289--297},
      year = {2021},
      link = {https://doi.org/10.1137/1.9781611976700.33},
      doi = {10.1137/1.9781611976700.33}
    }
    

    Abstract:

    A fundamental problem on graph-structured data is that of quantifying similarity between graphs. Graph kernels are an established technique for such tasks; in particular, those based on random walks and return probabilities have proven to be effective in wide-ranging applications, from bioinformatics to social networks to computer vision. However, random walk kernels generally suffer from slowness and tottering, an effect which causes walks to overemphasize local graph topology, undercutting the importance of global structure. To correct for these issues, we recast return probability graph kernels under the more general framework of density of states — a framework which uses the lens of spectral analysis to uncover graph motifs and properties hidden within the interior of the spectrum — and use our interpretation to construct scalable, composite density of states based graph kernels which balance local and global information, leading to higher classification accuracies on benchmark datasets.

  10. I. Delbridge, D. Bindel, and A. G. Wilson, “Randomly projected additive Gaussian processes for regression,” in Proceedings of Machine Learning and Systems 2020, 2020, pp. 7526–7536.
    @inproceedings{2020-icml,
      author = {Delbridge, Ian and Bindel, David and Wilson, Andrew Gordon},
      title = {Randomly projected additive {Gaussian} processes for regression},
      booktitle = {Proceedings of Machine Learning and Systems 2020},
      pages = {7526--7536},
      year = {2020},
      link = {https://proceedings.icml.cc/static/paper_files/icml/2020/4272-Paper.pdf},
      talk = {https://icml.cc/virtual/2020/poster/6248}
    }
    

    Abstract:

    Gaussian processes (GPs) provide flexible distributions over functions, with inductive biases controlled by a kernel. However, in many applications Gaussian processes can struggle with even moderate input dimensionality. Learning a low dimensional projection can help alleviate this curse of dimensionality, but introduces many trainable hyperparameters, which can be cumbersome, especially in the small data regime. We use additive sums of kernels for GP regression, where each kernel operates on a different random projection of its inputs. Surprisingly, we find that as the number of random projections increases, the predictive performance of this approach quickly converges to the performance of a kernel operating on the original full dimensional inputs, over a wide range of data sets, even if we are projecting into a single dimension. As a consequence, many problems can remarkably be reduced to one dimensional input spaces, without learning a transformation. We prove this convergence and its rate, and additionally propose a deterministic approach that converges more quickly than purely random projections. Moreover, we demonstrate our approach can achieve faster inference and improved predictive accuracy for high-dimensional inputs compared to kernels in the original input space.

  11. E. H. Lee, D. Eriksson, D. Bindel, and B. Cheng, “Efficient Rollout Strategies for Bayesian Optimization,” in Proceedings of Uncertainty in Artificial Intelligence 2020, 2020, p. 124.
    @inproceedings{2020-uai,
      author = {Lee, Eric Hans and Eriksson, David and Bindel, David and Cheng, Bolong},
      title = {Efficient Rollout Strategies for Bayesian Optimization},
      month = jul,
      year = {2020},
      arxiv = {2002.10539},
      link = {http://auai.org/uai2020/proceedings/124_main_paper.pdf},
      booktitle = {Proceedings of Uncertainty in Artificial Intelligence 2020},
      pages = {124}
    }
    

    Abstract:

    Bayesian optimization (BO) is a class of sample-efficient global optimization methods, where a probabilistic model conditioned on previous observations is used to determine future evaluations via the optimization of an acquisition function. Most acquisition functions are myopic, meaning that they only consider the impact of the next function evaluation. Non-myopic acquisition functions consider the impact of the next h function evaluations and are typically computed through rollout, in which h steps of BO are simulated. These rollout acquisition functions are defined as h-dimensional integrals, and are expensive to compute and optimize. We show that a combination of quasi-Monte Carlo, common random numbers, and control variates significantly reduce the computational burden of rollout. We then formulate a policy-search based approach that removes the need to optimize the rollout acquisition function. Finally, we discuss the qualitative behavior of rollout policies in the setting of multi-modal objectives and model error.

  12. K. Wilson and D. Bindel, “On the Distribution of Minima in Intrinsic-Metric Rotation Averaging,” in Proceedings of CVPR 2020, 2020. accepted
    @inproceedings{2020-cvpr,
      author = {Wilson, Kyle and Bindel, David},
      title = {On the Distribution of Minima in Intrinsic-Metric Rotation Averaging},
      booktitle = {Proceedings of CVPR 2020},
      month = jun,
      year = {2020},
      arxiv = {2003.08310},
      link = {https://arxiv.org/abs/2003.08310},
      submit = {accepted}
    }
    

    Abstract:

    Rotation Averaging is a non-convex optimization problem that determines orientations of a collection of cameras from their images of a 3D scene. The problem has been studied using a variety of distances and robustifiers. The intrinsic (or geodesic) distance on SO(3) is geometrically meaningful; but while some extrinsic distance-based solvers admit (conditional) guarantees of correctness, no comparable results have been found under the intrinsic metric.

    In this paper, we study the spatial distribution of local minima. First, we do a novel empirical study to demonstrate sharp transitions in qualitative behavior; as problems become noisier, they transition from a single (easy-to-find) dominant minimum to a cost surface filled with minima. In the second part of this paper we derive a theoretical bound for when this transition occurs. This is an extension of the results of [24], which used local convexity as a proxy to study the difficulty of problem. By recognizing the underlying quotient manifold geometry of the problem we achieve an n-fold improvement over prior work. Incidentally, our analysis also extends the prior l2 work to general lp costs. Our results suggest using algebraic connectivity as an indicator of problem difficulty.

  13. M. Lee, D. Bindel, and D. Mimno, “Prior-Aware Composition Inference for Spectral Topic Models,” in Proceedings of AISTATS 2020, PMLR 108, 2020, pp. 4258–4268.
    @inproceedings{2020-aistats,
      author = {Lee, Moontae and Bindel, David and Mimno, David},
      title = {Prior-Aware Composition Inference for Spectral Topic Models},
      booktitle = {Proceedings of AISTATS 2020, PMLR 108},
      month = jun,
      year = {2020},
      pages = {4258--4268},
      link = {https://proceedings.mlr.press/v108/lee20c.html}
    }
    

    Abstract:

    Spectral algorithms operate on matrices or tensors of word co-occurrence to learn latent topics. These approaches remove the dependence on the original documents and produce substantial gains in efficiency with provable inference, but at a cost: the models can no longer infer any information about individual documents. Thresholded Linear Inverse is developed to learn document-specific topic compositions, but its linear characteristics limit the inference quality without considering any prior information on topic distributions. We propose two novel estimation methods that respect previously unclear prior structures of spectral topic models. Experiments on a variety of synthetic to real collections demonstrate that our Prior-Aware Dual Decomposition outperforms the baseline method, whereas our Prior-Aware Manifold Iteration performs even better on short realistic data.

  14. M. Lee, S. Cho, D. Bindel, and D. Mimno, “Practical Correlated Topic Modeling and Analysis via the Rectified Anchor Word Algorithm,” in Proceedings of EMNLP 2019, 2019.
    @inproceedings{2019-emnlp,
      author = {Lee, Moontae and Cho, Sungjun and Bindel, David and Mimno, David},
      title = {Practical Correlated Topic Modeling and Analysis via the Rectified Anchor Word Algorithm},
      booktitle = {Proceedings of EMNLP 2019},
      month = nov,
      year = {2019}
    }
    

    Abstract:

    Despite great scalability on large data and their ability to understand correlations between topics, spectral topic models have not been widely used due to the absence of reliability in real data and lack of practical implementations. This paper aims to solidify the foundations of spectral topic inference and provide a practical implementation for anchor-based topic modeling. Beginning with vocabulary curation, we scrutinize every single inference step with other viable options. We also evaluate our matrix-based approach against popular alternatives including a tensor-based spectral method as well as probabilistic algorithms. Our quantitative and qualitative experiments demonstrate the power of Rectified Anchor Word algorithm in various real datasets, providing a complete guide to practical correlated topic modeling.

  15. K. Dong, A. R. Benson, and D. Bindel, “Network density of states,” in Proceedings of KDD, 2019.
    Best research paper award
    @inproceedings{2019-kdd,
      author = {Dong, Kun and Benson, Austin R. and Bindel, David},
      title = {Network density of states},
      booktitle = {Proceedings of KDD},
      month = aug,
      year = {2019},
      arxiv = {1905.09758},
      doi = {10.1145/3292500.3330891},
      notable = {Best research paper award}
    }
    

    Abstract:

    Spectral analysis connects graph structure to the eigenvalues and eigenvectors of associated matrices. Much of spectral graph theory descends directly from spectral geometry, the study of differentiable manifolds through the spectra of associated differential operators. But the translation from spectral geometry to spectral graph theory has largely focused on results involving only a few extreme eigenvalues and their associated eigenvalues. Unlike in geometry, the study of graphs through the overall distribution of eigenvalues - the spectral density - is largely limited to simple random graph models. The interior of the spectrum of real-world graphs remains largely unexplored, difficult to compute and to interpret.

    In this paper, we delve into the heart of spectral densities of real-world graphs. We borrow tools developed in condensed matter physics, and add novel adaptations to handle the spectral signatures of common graph motifs. The resulting methods are highly efficient, as we illustrate by computing spectral densities for graphs with over a billion edges on a single compute node. Beyond providing visually compelling fingerprints of graphs, we show how the estimation of spectral densities facilitates the computation of many common centrality measures, and use spectral densities to estimate meaningful information about graph structure that cannot be inferred from the extremal eigenpairs alone.

  16. I. Delbridge, D. Bindel, and A. G. Wilson, “Ramdomly Projected Additive Gaussian Processes,” in Proceedings of the Third Workshop on Tractable Probabilistic Modelnig (TPM 2019), 2019.
    @inproceedings{2019-tpm,
      author = {Delbridge, Ian and Bindel, David and Wilson, Andrew Gordon},
      title = {Ramdomly Projected Additive Gaussian Processes},
      booktitle = {Proceedings of the Third Workshop on Tractable Probabilistic Modelnig (TPM 2019)},
      month = jun,
      year = {2019},
      link = {https://drive.google.com/file/d/1JhqA4nE6pZTBE6p9vTRlgAAfFAoo21h7/view}
    }
    
  17. D. Eriksson, K. Dong, E. Lee, D. Bindel, and A. G. Wilson, “Scaling Gaussian Process Regression with Derivatives,” in Proceedings of NeurIPS 2018, 2018.
    @inproceedings{2018-nips-a,
      author = {Eriksson, David and Dong, Kun and Lee, Eric and Bindel, David and Wilson, Andrew Gordon},
      title = {Scaling {Gaussian} Process Regression with Derivatives},
      booktitle = {Proceedings of NeurIPS 2018},
      month = dec,
      year = {2018},
      arxiv = {1810.12283.pdf},
      link = {http://papers.nips.cc/paper/7919-scaling-gaussian-process-regression-with-derivatives}
    }
    

    Abstract:

    Gaussian processes (GPs) with derivatives are useful in many applications, including Bayesian optimization, implicit surface reconstruction, and terrain reconstruction. Fitting a GP to function values and derivatives at $n$ points in $d$ dimensions requires linear solves and log determinants with an $n(d + 1) × n(d + 1)$ positive definite matrix – leading to prohibitive $O(n^3 d^3)$ computations for standard direct methods. We propose iterative solvers using fast $O(nd)$ matrix-vector multiplications (MVMs), together with pivoted Cholesky preconditioning that cuts the iterations to convergence by several orders of magnitude, allowing for fast kernel learning and prediction. Our approaches, together with dimensionality reduction, enables Bayesian optimization with derivatives to scale to high-dimensional problems and large evaluation budgets.

  18. J. Gardner, G. Pleiss, K. Weinberger, D. Bindel, and A. G. Wilson, “GPyTorch: Blackbox Matrix-Matrix Gaussian Process Inference with GPU Acceleration,” in Proceedings of NeuroIPS 2018, 2018.
    @inproceedings{2018-nips-b,
      author = {Gardner, Jacob and Pleiss, Geoff and Weinberger, Killian and Bindel, David and Wilson, Andrew Gordon},
      title = {{GPyTorch}: Blackbox Matrix-Matrix {Gaussian} Process Inference with {GPU} Acceleration},
      booktitle = {Proceedings of NeuroIPS 2018},
      month = dec,
      year = {2018},
      arxiv = {1809.11165.pdf},
      link = {http://papers.nips.cc/paper/7985-gpytorch-blackbox-matrix-matrix-gaussian-process-inference-with-gpu-acceleration}
    }
    

    Abstract:

    Despite advances in scalable models, the inference tools used for Gaussian processes (GPs) have yet to fully capitalize on developments in computing hardware. We present an efficient and general approach to GP inference based on Blackbox Matrix-Matrix multiplication (BBMM). BBMM inference uses a modified batched version of the conjugate gradients algorithm to derive all terms for training and inference in a single call. BBMM reduces the asymptotic complexity of exact GP inference from $O(n^3)$ to $O(n^2)$. Adapting this algorithm to scalable approximations and complex GP models simply requires a routine for efficient matrix-matrix multiplication with the kernel and its derivative. In addition, BBMM uses a specialized preconditioner to substantially speed up convergence. In experiments we show that BBMM effectively uses GPU hardware to dramatically accelerate both exact GP inference and scalable approximations. Additionally, we provide GPyTorch, a software platform for scalable GP inference via BBMM, built on PyTorch.

  19. 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{2017-nips,
      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.

  20. 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{2017-informs,
      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 high-level 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 easily-collected summary statistics, rather than exhaustively iterating over the full dataset. The “anchor word” algorithms learn topics by decomposing the co-occurrence 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 anchor-based 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.

  21. P. Shi, K. He, D. Bindel, and J. Hopcroft, “Local Lanczos Spectral Approximation for Community Detection,” in Proceedings of ECML-PKDD, 2017.
    @inproceedings{2017-ecml-pkdd,
      author = {Shi, Pan and He, Kun and Bindel, David and Hopcroft, John},
      title = {Local Lanczos Spectral Approximation for Community Detection},
      booktitle = {Proceedings of ECML-PKDD},
      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 real-world datasets in various domains as well as synthetic datasets. Results show that the proposed method outperforms state-of-the-art 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.

  22. K. Wilson, D. Bindel, and N. Snavely, “When is Rotations Averaging Hard?,” in Proceedings of ECCV 2016, 2016.
    @inproceedings{2016-rotations,
      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 high-quality 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.

  23. 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{2016-losp-kdd,
      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 semi-supervised 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 follow-up 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 real-world 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.

  24. E. Yilmaz and D. Bindel, “Temperature Sensitivity of Solid-Wave Gyroscopes (Late News),” in Proceedings of the Hilton Head Solid-Sate Sensor and Actuator Workshop 2016, 2016.
    @inproceedings{2016-hh-workshop,
      author = {Yilmaz, Erdal and Bindel, David},
      booktitle = {Proceedings of the Hilton Head Solid-Sate Sensor and
                     Actuator Workshop 2016},
      title = {Temperature Sensitivity of Solid-Wave Gyroscopes (Late News)},
      month = jun,
      year = {2016}
    }
    

    Abstract:

    We analyze the change of angular gain and vibration frequency of solid-wave 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.

  25. 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{2015-middleware,
      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 real-life. 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.

  26. 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{2015-nips,
      author = {Lee, Moontae and Bindel, David and Mimno, David},
      title = {Robust Spectral Inference for
                 Joint Stochastic Matrix Factorization},
      booktitle = {Proceedings of NIPS 2015},
      pages = {2710--2718},
      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 ad-hoc 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.

  27. 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{2015-icdm,
      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.

  28. W. Xie, D. Bindel, A. Demers, and J. Gehrke, “Edge-Weighted Personalized PageRank: Breaking A Decade-Old Performance Barrier,” in Proceedings of ACM KDD 2015, 2015.
    Best student paper award.
    @inproceedings{2015-edgeppr,
      author = {Xie, Wenlei and Bindel, David and Demers, Alan and Gehrke, Johannes},
      booktitle = {Proceedings of ACM KDD 2015},
      title = {Edge-Weighted Personalized {PageRank}:
                 Breaking A Decade-Old Performance Barrier},
      month = aug,
      year = {2015},
      doi = {10.1145/2783258.2783278},
      notable = {Best student paper award.},
      code = {https://github.com/wenleix/EdgePPR},
      slides = {present/2015-08-kdd-talk_kdd-aug15.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 learning-to-rank problems for edge weight personalization at interactive speeds, a goal that had not previously been achievable for this class of problems.

  29. 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{2015-www,
      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 PageRank-like 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 state-of-the-art 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 real-world 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.

  30. K. Dong and D. Bindel, “Modified Kernel Polynomial Method for Estimating Graph Spectra,” in SIAM Network Science 2015 (poster), 2015.
    @inproceedings{2015-siam-ns,
      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 high-multiplicity eigenvalues corresponding to certain motifs in the graph, we introduce a pre-processing phase that counts just these special eigenvalues, leaving the rest of the eigenvalue distribution to be estimated by the standard KPM.

  31. E. Yilmaz and D. Bindel, “Effects of imperfections on solid-wave gyroscope dynamics,” in Proceedings of IEEE SENSORS 2013, 2013.
    @inproceedings{2013-sensors,
      author = {Yilmaz, Erdal and Bindel, David},
      title = {Effects of imperfections on solid-wave gyroscope dynamics},
      booktitle = {Proceedings of IEEE SENSORS 2013},
      month = nov,
      year = {2013},
      doi = {10.1109/ICSENS.2013.6688462}
    }
    

    Abstract:

    Solid-wave 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 solid-wave 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 solid-wave 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

  32. T. Zou, G. Wang, M. Vaz Salles, D. Bindel, A. Demers, J. Gehrke, and W. White, “Making Time-Stepped Applications Tick in the Cloud,” in Proceedings of the Second ACM Symposium on Cloud Computing (SOCC), 2011.
    @inproceedings{2011-socc,
      author = {Zou, Tao and Wang, Guozhang and Vaz Salles, Marcos and Bindel, David and Demers, Alan and Gehrke, Johannes and White, Walker},
      title = {Making Time-Stepped 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 time-steps 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 time-stepped applications in the cloud. Our framework exposes a high-level, data-centric programming model which represents application state as tables and dependencies between states as queries over these tables. We design a jitter-tolerant runtime that uses these data dependencies to absorb latency spikes by (1) carefully scheduling computation and (2) replicating data and computation. Our data-driven 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 time-stepped applications.

  33. 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{2011-focs,
      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 long-standing 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 best-response 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.

  34. C. Bruyns-Maxwell and D. Bindel, “Modal Parameter Tracking for Shape Changing Objects,” in Proceedings of DAFx 2007, 2007.
    @inproceedings{2007-sound,
      author = {Bruyns-Maxwell, 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.

  35. 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{2006-para,
      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 = {11--23},
      year = {2006}
    }
    

    Abstract:

    New releases of the widely used LAPACK and ScaLAPACK numerical linear algebra libraries are planned. Based on an on-going user survey (<www.netlib.org/lapack-dev>) 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.

  36. C. Bruyns and D. Bindel, “Shape Changing Symmetric Objects for Sound Synthesis,” in Proceedings of 121st AES, 2006.
    @inproceedings{2006-sound,
      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 finite-element analysis of a musical instrument, the initial modal decomposition is time-consuming. To design instruments from physical simulation, one would like to be able to compute modes in real-time, 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.

  37. Y. Zhao, Y. Chen, and D. Bindel, “Toward Unbiased End-to-End Network Diagnosis,” in Proceedings of SIGCOMM 2006, 2006, pp. 219–230.
    @inproceedings{2006-sigcomm,
      author = {Zhao, Yao and Chen, Yan and Bindel, David},
      title = {Toward Unbiased End-to-End Network Diagnosis},
      booktitle = {Proceedings of SIGCOMM 2006},
      pages = {219--230},
      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 link-level properties cannot be uniquely determined from end-to-end 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 Least-biased End-to-end Network Diagnosis (in short, LEND) system for inferring link-level 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 end-to-end 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 real-time even for reasonably large overlay networks. Finally, LEND can supplement existing statistical inference approaches and provide smooth tradeoff between diagnosis accuracy and granularity.

  38. Y. Zhao, Y. Chen, and D. Bindel, “Toward Deterministic Overlay Diagnosis,” in ACM SIGMETRICS/Performance 2006, 2006, pp. 387–388.
    @inproceedings{2006-sigmetrics,
      author = {Zhao, Yao and Chen, Yan and Bindel, David},
      title = {Toward Deterministic Overlay Diagnosis},
      booktitle = {ACM SIGMETRICS/Performance 2006},
      pages = {387--388},
      year = {2006},
      doi = {10.1145/1140277.1140333}
    }
    
  39. 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{2005-sensors,
      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 mechanically-driven temperature gradients, while anchor loss occurs when high-frequency mechanical waves radiate away from the resonator and into the substrate. Our finite-element 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.

  40. Y. Zhao, Y. Chen, and D. Bindel, “Scalable and Deterministic Overlay Network Diagnosis,” in Proceedings of ACM SIGCOMM 2005 (poster), 2005.
    @inproceedings{2005-sigcomm,
      author = {Zhao, Yao and Chen, Yan and Bindel, David},
      title = {Scalable and Deterministic Overlay Network Diagnosis},
      booktitle = {Proceedings of ACM SIGCOMM 2005 (poster)},
      year = {2005}
    }
    
  41. 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{2005-iccs,
      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 = {50--57},
      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 parameter-dependent 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 user-friendly MATLAB package for the study of dynamical systems and their bifurcations. We incorporate the CIS algorithm into Cl_matcont to extend its functionality to large scale bifurcation computations via subspace reduction

  42. D. Bindel, E. Quevy, T. Koyama, J. Demmel, and R. Howe, “Anchor Loss Simulation in Resonators,” in Proceedings of MEMS 2005, 2005.
    @inproceedings{2005-mems,
      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:

    Surface-micromachined 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 high-frequency resonators and account for sub-surface 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 mixed-mode 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 radial-to-bending motion interaction, which we visualize with a root-locus diagram. We experimentally verify this predicted sensitivity using poly-SiGe disk resonators having $Q$’s ranging from 200 to 54,000.

  43. 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{2004-sigcomm,
      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.

  44. D. Bindel, Z. Bai, and J. Demmel, “Model Reduction for RF MEMS Simulation,” in Proceedings of PARA 2004, 2004.
    @inproceedings{2004-para,
      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:

    Radio-frequency (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 structure-preserving model-reduction techniques and apply them to the frequency-domain analysis of two proposed MEMS resonator designs.

  45. Y. Chen, D. Bindel, and R. Katz, “Tomography-Based Overlay Network Monitoring,” in Proceedings of ACM SIGCOMM Internet Measurement Conference (IMC), 2003.
    @inproceedings{2003-imc,
      author = {Chen, Yan and Bindel, David and Katz, Randy},
      title = {Tomography-Based 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 end-to-end 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.

  46. 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{2002-mems,
      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 reduced-order modeling techniques, simple hierarchical description of complex structures, synthesis tools, a variety of models, and a web-based interface. Examples include the modeling of a torsional micromirror with lateral actuators compared to experiment, and the prototyping of a microrobot.

  47. 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{2001-icics,
      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 = {340--351},
      month = nov,
      year = {2001},
      doi = {10.1007/3-540-45600-7_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 simulation-based 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.

  48. J. Clark, D. Bindel, N. Zhou, S. Bhave, Z. Bai, J. Demmel, and K. S. J. Pister, “SUGAR: Advancements in a 3D Multi-Domain Simulation Package for MEMS,” in Proceedings of the Microscale Systems: Mechanics and Measurements Symposium, 2001.
    @inproceedings{2001-sugar,
      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 Multi-Domain 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 two-axis 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 fixed-fixed beam.

  49. 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{2001-msm,
      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 proof-of-concept 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 user-defined models.

  50. 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 Global-Scale Persistent Storage,” in Procedings of the Ninth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS 2000), 2000.
    ASPLOS Most Influential Paper Award 2018
    @inproceedings{2000-asplos,
      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 Global-Scale 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},
      notable = {ASPLOS Most Influential Paper Award 2018}
    }
    

    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 pro-active movement of data. A prototype implementation is currently under development.

  51. 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{2000-mems,
      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 = {68--75},
      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, time-varying 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

  1. M. Ruth, R. Jorge, and D. Bindel, “The High-Order Magnetic Near-Axis Expansion: Ill-Posedness and Regularization,” Nov. 2024.
    @techreport{2024-jpp,
      author = {Ruth, Maximillian and Jorge, Rogerio and Bindel, David},
      title = {The High-Order Magnetic Near-Axis Expansion: Ill-Posedness and Regularization},
      month = nov,
      year = {2024},
      arxiv = {2411.04352},
      link = {https://arxiv.org/pdf/2411.04352},
      note = {Submitting to JPP},
      status = {unrefereed}
    }
    

    Abstract:

    When analyzing stellarator configurations, it is common to perform an asymptotic expansion about the magnetic axis. This so-called near-axis expansion is convenient for the same reason asymptotic expansions often are, namely, it reduces the dimension of the problem. This leads to convenient and quickly computed expressions of physical quantities, such as quasisymmetry and stability criteria, which can be used to gain further insight. However, it has been repeatedly found that the expansion diverges at high orders, limiting the physics the expansion can describe. In this paper, we show that the near-axis expansion diverges in vacuum due to ill-posedness and that it can be regularized to improve its convergence. Then, using realistic stellarator coil sets, we show that the near-axis expansion can converge to ninth order in the magnetic field, giving accurate high-order corrections to the computation of flux surfaces. We numerically find that the regularization improves the solutions of the near-axis expansion under perturbation, and we demonstrate that the radius of convergence of the vacuum near-axis expansion is correlated with the distance from the axis to the coils.

  2. M. Czekanski, B. Faber, M. Fairborn, A. Wright, and D. Bindel, “Walking on Spheres and Talking to Neighbors: Variance Reduction for Laplace’s Equation,” Apr. 2024.
    @techreport{2024-jcp,
      author = {Czekanski, Michael and Faber, Benjamin and Fairborn, Margaret and Wright, Adelle and Bindel, David},
      title = {Walking on Spheres and Talking to Neighbors: Variance Reduction for Laplace's Equation},
      month = apr,
      year = {2024},
      arxiv = {2404.17692},
      link = {http://arxiv.org/pdf/2403.19003},
      note = {Submitted to JCP},
      status = {unrefereed}
    }
    

    Abstract:

    Walk on Spheres algorithms leverage properties of Brownian Motion to create Monte Carlo estimates of solutions to a class of elliptic partial differential equations. Until recently, estimates were constructed pointwise and did not utilize the relationship between solutions at nearby points within a domain. We propose a new caching strategy which leverages the continuity of paths of Brownian Motion. In the case of Laplace’s equation with Dirichlet boundary conditions, our novel algorithm has improved asymptotic runtime compared to previous approaches. This is achieved by passing information from a cache of constant size. We also provide bounds on the performance of our algorithm and demonstrate its performance on an example problem.

  3. Y. Yang, M. Wang, D. Bindel, and H. He, “Streaming Local Community Detection through Approximate Conductance,” Oct. 2021.
    @techreport{2021-streaming,
      author = {Yang, Yanhao and Wang, Meng and Bindel, David and He, Hun},
      title = {Streaming Local Community Detection through Approximate Conductance},
      month = oct,
      year = {2021},
      arxiv = {2110.14972},
      link = {http://arxiv.org/pdf/2110.14972},
      status = {unrefereed}
    }
    

    Abstract:

    Community is a universal structure in various complex networks, and community detection is a fundamental task for network analysis. With the rapid growth of network scale, networks are massive, changing rapidly and could naturally be modeled as graph streams. Due to the limited memory and access constraint in graph streams, existing non-streaming community detection methods are no longer applicable. This raises an emerging need for online approaches. In this work, we consider the problem of uncovering the local community containing a few query nodes in graph streams, termed streaming local community detection. This is a new problem raised recently that is more challenging for community detection and only a few works address this online setting. Correspondingly, we design an online single-pass streaming local community detection approach. Inspired by the “local” property of communities, our method samples the local structure around the query nodes in graph streams, and extracts the target community on the sampled subgraph using our proposed metric called the approximate conductance. Comprehensive experiments show that our method remarkably outperforms the streaming baseline on both effectiveness and efficiency, and even achieves similar accuracy comparing to the state-of-the-art non-streaming local community detection methods that use static and complete graphs.

  4. D. Qi, D. Bindel, and A. Vladimirsky, “Surveillance Evasion through Bayesian Reinforcement Learning,” Sep. 2021.
    @techreport{2021-surveillance,
      author = {Qi, Dongping and Bindel, David and Vladimirsky, Alex},
      title = {Surveillance Evasion through {Bayesian} Reinforcement Learning},
      month = sep,
      year = {2021},
      arxiv = {2109.14811},
      link = {http://arxiv.org/pdf/2109.14811},
      status = {unrefereed}
    }
    

    Abstract:

    We consider a 2D continuous path planning problem with a completely unknown intensity of random termination: an Evader is trying to escape a domain while minimizing the cumulative risk of detection (termination) by adversarial Observers. Those Observers’ surveillance intensity is a priori unknown and has to be learned through repetitive path planning. We propose a new algorithm that utilizes Gaussian process regression to model the unknown surveillance intensity and relies on a confidence bound technique to promote strategic exploration. We illustrate our method through several examples and confirm the convergence of averaged regret experimentally.

  5. D. Eriksson, D. Bindel, and C. Shoemaker, “pySOT and POAP: An event-driven asynchronous framework for surrogate optimization,” Aug. 2019. Submitted to ACM Transactions on Mathematical Software.
    @techreport{2019-pysot,
      author = {Eriksson, David and Bindel, David and Shoemaker, Christine},
      title = {{pySOT} and {POAP}: An event-driven asynchronous framework for surrogate optimization},
      month = aug,
      year = {2019},
      arxiv = {1908.00420},
      link = {https://arxiv.org/pdf/1908.00420},
      status = {unrefereed},
      submit = {Submitted to ACM Transactions on Mathematical Software.}
    }
    

    Abstract:

    This paper describes Plumbing for Optimization with Asynchronous Parallelism (POAP) and the Python Surrogate Optimization Toolbox (pySOT). POAP is an event-driven framework for building and combining asynchronous optimization strategies, designed for global optimization of expensive functions where concurrent function evaluations are useful. POAP consists of three components: a worker pool capable of function evaluations, strategies to propose evaluations or other actions, and a controller that mediates the interaction between the workers and strategies. pySOT is a collection of synchronous and asynchronous surrogate optimization strategies, implemented in the POAP framework. We support the stochastic RBF method by Regis and Shoemaker along with various extensions of this method, and a general surrogate optimization strategy that covers most Bayesian optimization methods. We have implemented many different surrogate models, experimental designs, acquisition functions, and a large set of test problems. We make an extensive comparison between synchronous and asynchronous parallelism and find that the advantage of asynchronous computation increases as the variance of the evaluation time or number of processors increases. We observe a close to linear speed-up with 4, 8, and 16 processors in both the synchronous and asynchronous setting.

  6. 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{2016-transient-tr,
      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.}
    }
    
  7. C. Ponce and D. Bindel, “FLiER: Practical Topology Update Detection Using Sparse PMUs,” Jul. 2016. Accepted by IEEE Transactions on Power Systems.
    @techreport{2016-flier-tr,
      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 sparsely-deployed 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 brute-force 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 57-bus, IEEE 118-bus, and Polish 1999-2000 winter peak networks.

  8. J. Chadwick and D. Bindel, “An Efficient Solver for Sparse Linear Systems Based on Rank-Structured Cholesky Factorization,” Jul. 2015.
    @techreport{2015-rsc,
      author = {Chadwick, Jeffrey and Bindel, David},
      title = {An Efficient Solver for Sparse Linear Systems Based on
                 Rank-Structured {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, rank-structured Cholesky algorithm for solution of the positive definite linear system Ax=b when A comes from a discretized partial-differential equation. Our approach combines the efficient memory access patterns of conventional supernodal Cholesky algorithms with the memory efficiency of rank-structured direct solvers. For several test problems arising from PDE discretizations, our method takes less memory than standard sparse Cholesky solvers and less wall-clock time than standard preconditioned iterations.

  9. D. Bindel and A. Hood, “Localization Theorems for Nonlinear Eigenvalues,” Aug. 2013. Appeared in SIAM Journal on Matrix Analysis and Applications in 2013.
    @techreport{2013-nep,
      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 matrix-valued function that is analytic on some simply-connected 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 Bauer-Fike 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.

  10. 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/SEMM-2009/04, Dec. 2009. Appeared in Optimization and Engineering in 2012
    @techreport{2009-topology,
      author = {He, Wei and Bindel, David and Govindjee, Sanjay},
      title = {Topology Optimization in Micromechanical Resonator Design},
      number = {UCB/SEMM-2009/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 eigen-frequencies 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.

  11. D. Bindel, “Structured and Parameter-Dependent Eigensolvers for Simulation-Based Design of Resonant MEMS,” PhD thesis, University of California, Berkeley, 2006. Appears as Tech Report EECS-2006-109.
    2008 Householder Award (best NLA thesis over three years)
    @phdthesis{2006-dissertation,
      author = {Bindel, David},
      title = {Structured and Parameter-Dependent Eigensolvers for
                 Simulation-Based Design of Resonant {MEMS}},
      school = {University of California, Berkeley},
      month = aug,
      year = {2006},
      status = {unrefereed},
      submit = {Appears as Tech Report EECS-2006-109.},
      notable = {2008 Householder Award (best NLA thesis over three years)}
    }
    

    Abstract:

    This dissertation is about computational tools to aid in the design of resonant Micro-Electro-Mechanical 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 time-consuming 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 non-Hermitian, and depend nonlinearly on frequency, we use the equation structure to develop efficient structured Krylov subspace projection methods for computing free vibrations and reduced-order models. We also provide efficient continuation methods for re-computing 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 previously-unknown mode interference phenomenon, subsequently observed in experiments, which dramatically affects the amount of damping near certain critical values of geometric parameters.

  12. D. Bindel and J. Demmel, “Continuation of Invariant Subspaces for Large Bifurcation Problems,” UC Berkeley Computer Science Division, EECS-2006-13, Feb. 2006. Appeared in SIAM Journal on Scientific Computing in 2008.
    @techreport{2006-cis,
      author = {Bindel, David and Demmel, James},
      title = {Continuation of Invariant Subspaces for Large Bifurcation Problems},
      number = {EECS-2006-13},
      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 parameter-dependent 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.

  13. D. Bindel, S. Chandresekaran, J. Demmel, D. Garmire, and M. Gu, “A Fast and Stable Nonsymmetric Eigensolver for Certain Structured Matrices,” May 2005.
    @techreport{2005-compan,
      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 semi-separable 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.

  14. 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/SEMM-2005/01, Feb. 2005. Appeared in International Journal on Numerical Methods in Engineering in 2005.
    @techreport{2005-pml-tr,
      author = {Bindel, David and Govindjee, Sanjay},
      title = {Elastic {PML}s for Resonator Anchor Loss Simulation},
      number = {UCB/SEMM-2005/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 surface-acoustic wave devices, are important signal-processing 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 micro-resonators 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 semi-infinite elastic half-space. 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 non-zero angle of incidence. We exploit the interpretation of the PML as a complex-valued 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 mode-mixing phenomenon which can substantially affect the quality of resonance.

  15. Y. Chen, D. Bindel, H. Song, and R. Katz, “Tomography-Based Overlay Network Monitoring,” UC Berkeley Computer Science Division, CSD-03-1252, Jun. 2003. Appeared in SIGCOMM IMC 2003
    @techreport{2003-tomography-tr,
      author = {Chen, Yan and Bindel, David and Song, Hanhee and Katz, Randy},
      title = {Tomography-Based Overlay Network Monitoring},
      number = {CSD-03-1252},
      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 end-to-end 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.

  16. 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{2001-givens,
      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 Ultra-10, 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.

  17. 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 Global-Scale Persistent Storage,” UC Berkeley Computer Science Division, CSD-00-1102, Mar. 2000. Appeared in ASPLOS 2000.
    @techreport{2000-oceanstore-tr,
      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 Global-Scale Persistent Storage},
      number = {CSD-00-1102},
      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 pro-active movement of data. A prototype implementation is currently under development.

External Talks

Colloquium and Seminar Talks

  1. Optimizing Magnetic Confinement Devices for Fusion Plasmas
    2024 Nov • Emory University CODES seminar
  2. New Approaches to Computing with Kernels
    2024 Nov • Clemson University
    colloquium
  3. Optimizing Magnetic Confinement Devices for Fusion Plasmas
    2023 Dec • Mathematical Sciences Institute Colloquium, Australian National University
    colloquium
  4. The Structure and Interpretation of Graph Spectral Densities
    2022 Apr • Michigan Applied Interdisciplinary Mathematics (AIM) seminar
  5. Inducing Point Approximations of Kernel Matrices
    2022 Jan • eNLA seminar, online
  6. Understanding Graphs through Spectral Densities
    2020 Mar • University of Buffalo Applied Math Seminar
  7. Understanding Graphs through Spectral Densities
    2019 Oct • WMU math colloquium
    colloquium
  8. Numerical Methods for Data Science: Spectral Network Analysis, Part II
    2019 Jun • Special lecture series at University of Chicago
  9. Numerical Methods for Data Science: Spectral Network Analysis, Part I
    2019 Jun • Special lecture series at University of Chicago
  10. Numerical Methods for Data Science: Kernel Methods, Part II
    2019 Jun • Special lecture series at University of Chicago
  11. Numerical Methods for Data Science: Kernel Methods, Part I
    2019 Jun • Special lecture series at University of Chicago
  12. Numerical Methods for Data Science: Latent Factor Models, Part II
    2019 Jun • Special lecture series at University of Chicago
  13. Numerical Methods for Data Science: Latent Factor Models, Part I
    2019 Jun • Special lecture series at University of Chicago
  14. Understanding Graphs through Spectral Densities
    2019 May • CS Colloquium, William and Mary
    colloquium
  15. Understanding Graphs through Spectral Densities
    2019 May • Math Colloquium, Virginia Tech
    colloquium
  16. Numerical Methods for Data Science: Spectral Network Analysis, Part II
    2019 May • Special lecture series at University of Maryland, College Park
  17. Numerical Methods for Data Science: Spectral Network Analysis, Part I
    2019 Apr • Special lecture series at University of Maryland, College Park
  18. Numerical Methods for Data Science: Kernel Methods, Part II
    2019 Apr • Special lecture series at University of Maryland, College Park
  19. Numerical Methods for Data Science: Kernel Methods, Part I
    2019 Apr • Special lecture series at University of Maryland, College Park
  20. Numerical Methods for Data Science: Latent Factor Models, Part II
    2019 Apr • Special lecture series at University of Maryland, College Park
  21. Numerical Methods for Data Science: Latent Factor Models, Part I
    2019 Apr • Special lecture series at University of Maryland, College Park
  22. Stochastic Linear Algebra for Scalable Gaussian Processes
    2019 Jan • Applied Mathematics Colloquium, Illinois Institute of Technology
    colloquium
  23. Stochastic Linear Algebra for Scalable Gaussian Processes
    2019 Jan • CAM Colloquium, University of Chicago
    colloquium
  24. Stochastic Linear Algebra for Scalable Gaussian Processes
    2018 Oct • IEMS Seminar, Northwestern University
  25. Understanding Graphs through Spectral Densities
    2018 Jun • Seminar at Huazhong University of Science and Tech
  26. Understanding Graphs through Spectral Densities
    2018 Jun • ZY-INS Colloquium, Shanghai Jiao Tong University
    colloquium
  27. Model Reduction for Edge-Weighted Personalized PageRank
    2017 Feb • Berkeley CS Colloquium
    colloquium
  28. Nonlinear Eigenvalue Problems: Theory and Applications
    2017 Jan • Berkeley Applied Math Seminar
  29. Model Reduction for Edge-Weighted Personalized PageRank
    2016 Dec • NYU Numerical Analysis and Scientific Computing Seminar
  30. Fast Fingerprints for Power System Events
    2016 Oct • Argonne National Lab
  31. Fast Fingerprints for Power System Events
    2016 Aug • Lawrence Berkeley Lab
  32. Model Reduction for Edge-Weighted Personalized PageRank
    2016 Apr • Purdue Computational and Applied Mathematics Seminar
  33. Model Reduction for Edge-Weighted Personalized PageRank
    2016 Mar • Hong Kong Baptist University
  34. Nonlinear Eigenvalue Problems: Theory and Applications
    2016 Mar • University of Arizona Math Colloquium
    colloquium
  35. Model Reduction for Edge-Weighted Personalized PageRank
    2015 Oct • Stanford LA/Opt Seminar
  36. Model Reduction for Edge-Weighted Personalized PageRank
    2015 Oct • Berkeley Matrix Computations Seminar
  37. Music of the Microspheres
    2014 Apr • Oxford University NA Seminar
  38. Music of the Microspheres
    2014 Jan • UMCP NA Seminar
  39. Music of the Microspheres
    2013 Nov • Seminar at UTRC
  40. Music of the Microspheres
    2013 Oct • Tufts/Schlumberger Scientific Computing Seminar
  41. Computer Aided Design of Micro-Electro-Mechanical Systems
    2013 Apr • Civil Engineering Seminar at Duke
  42. Communities, Spectral Clustering, and Random Walks
    2011 Nov • University of Chicago Scientific Computing Seminar
  43. Applications and Analysis of Nonlinear Eigenvalue Problems
    2009 Nov • Simon Fraser University NA Seminar
  44. Computer-Aided Design for Micro-Electro-Mechanical Systems
    2008 Nov • Stanford LA/Opt Seminar
  45. Computer-Aided Design for Micro-Electro-Mechanical Systems
    2008 Nov • MIT Applied Math Colloquium
    colloquium
  46. Bounds and Error Estimates for Nonlinear Eigenvalue Problems
    2008 Oct • Berkeley Applied Math Seminar
  47. Computer-Aided Design for Micro-Electro-Mechanical Systems
    2008 Jan • Rice University Applied Math Colloquium
    colloquium
  48. Computer-Aided Design for Micro-Electro-Mechanical Systems
    2007 Nov • Temple University NA Seminar
  49. Computer-Aided Design for Micro-Electro-Mechanical Systems
    2007 Nov • Cornell CS Colloquium
    colloquium
  50. Computer-Aided Design for Micro-Electro-Mechanical Systems
    2007 Mar • Columbia Applied Math Colloquium
    colloquium
  51. Spectral Inclusion Regions for Bifurcation Analysis
    2006 Aug • Stanford NA Seminar
  52. Computer-Aided Design for Micro-Electro-Mechanical Systems
    2006 Apr • CU Boulder CS Colloquium
    colloquium
  53. Computer-Aided Design for Micro-Electro-Mechanical Systems
    2006 Mar • UC Davis CS Colloquium
    colloquium
  54. Computer-Aided Design for Micro-Electro-Mechanical Systems
    2006 Feb • Caltech CS Colloquium
    colloquium
  55. Computer-Aided Design of MEMS
    2004 Nov • NYU Numerical Analysis Seminar
  56. SUGAR: A MEMS Simulation Program
    2002 Jun • Sun Microsystems

Workshop and Conference Talks

  1. Bayesian Optimization Under Uncertainty with Local Refinement
    2024 Jun • Workshop on Adaptive Experimentation, Meta NYC
    invited
  2. Linear Algebra Perspectives on Inducing Point Selection
    2024 May • SIAM Applied Linear Algebra Meeting 2024, Paris
    minisymposium invited
  3. Optimizing Magnetic Confinement Devices for Fusion Plasmas
    2024 Apr • SANUM, Stellenbosch University
    invited plenary
  4. Linear Stability: Some Thoughts
    2023 Dec • Simons Collaboration Retreat, Australian National University
  5. Linear Algebra, Invariant Circles, and Fusion Plasmas
    2023 Aug • BIRS Workshop on New Directions in Applied Linear Algebra
    invited
  6. Global Stochastic Optimization of Stellarator Coils
    2023 Mar • SIAM Computational Science and Engineering 2023, Amsterdam
    minisymposium invited
  7. Inducing Point Approximations of Kernel Matrices
    2022 Jul • SIAM Annual Meeting 2022, Pittsburgh (hybrid)
    minisymposium invited
  8. Constrained, Multi-Objective, and Parameterized Optimization
    2022 Jun • Simons Collaboration Meeting, Institute for Plasma Physics, Greifswald, Germany
    invited
  9. Chebyshev Featurization
    2022 Jun • Householder Symposium XXI, Selva di Fasano
    poster invited
  10. Spectral Network Analysis: Beyond the Spectrum's Edge
    2022 Feb • Workshop on Complex Networks: Analysis, Numerics, and Applications at UMD
    invited
  11. Structured Numerical Linear Algebra for Gaussian Process Modeling
    2021 May • SIAM Applied Linear Algebra 2021, online
    plenary invited
  12. Surrogate-Based Optimization of Stellarators
    2021 Mar • SIAM Computational Science and Engineering 2021, online
    minisymposium invited
  13. Surrogate Methods for Optimizing Fusion Device Designs
    2019 Dec • SIAM Analysis of PDEs 2019, La Quinta
    minisymposium invited
  14. From Bells of Frost to Opinion's Cost: The Many Applications of Eigenvalues
    2019 Oct • WMU Fall Math Public Lecture
    invited
  15. Understanding Graphs through Spectral Densities
    2019 Jul • ICIAM 2019
    minisymposium invited
  16. Dynamics via Nonlinear Pseudospectra
    2019 Jul • ICIAM 2019
    minisymposium invited
  17. Understanding Graphs through Spectral Densities
    2019 Jul • SIAG-LA lecture at ILAS 2019
    invited plenary
  18. Global, Robust, Multi-Objective Optimization of Stellarators
    2019 Mar • Simons Collaboration on Hidden Symmetries and Fusion Energy Annual Meeting
    invited
  19. Nonlinear Eigenvalue Localization for Damping Bounds
    2019 Feb • SIAM Computational Science and Engineering 2019, Spokane
    minisymposium invited
  20. LA Support for Scalable Kernel Methods
    2018 Sep • Workshop on Approximation Theory and Machine Learning, Purdue
    invited
  21. Understanding Graphs through Spectral Densities
    2018 Jul • SIAM Network Science, Portland
    invited plenary
  22. Stochastic LA for Scaling GPs
    2018 Jun • International Workshop on Computational Math, Suzhou
    invited
  23. Multi-Objective Stochastic Optimization of Magnetic Fields
    2018 Apr • Simons Foundation Proposal Presentation
    invited
  24. Scalable Algorithms for Kernel-Based Surrogates in Prediction and Optimization
    2017 Nov • Workshop on Surrogate Models and Coarsening Techniques, UCLA IPAM
    invited
  25. Dynamics via Nonlinear Pseudospectra
    2017 Jul • Foundations of Computational Math 2017
    minisymposium invited
  26. Stochastic estimators in Gaussian process kernel learning
    2017 Jun • Householder Symposium
    invited poster
  27. Celebrating Charlie
    2016 Jul • SIAM Annual Meeting, Boston
    minisymposium organizer
  28. Density of States for Graph Analysis
    2016 Jul • SIAM Annual Meeting, Boston
    poster
  29. An Efficient Solver for Sparse Linear Systems based on Rank-Structured Cholesky Factorization
    2016 Mar • TSIMF Workshop on Structured Matrix Computations with Applications
    invited
  30. Grumbles of a Numerical Analyst
    2015 Dec • Dagstuhl Seminar on Approximate and Probabilistic Computing
    invited
  31. Localizing Nonlinear Eigenvalue Problems: Theory and Applications
    2015 Oct • SIAM LA 2015 (Prize Lecture)
    invited plenary
  32. RBF Response Surfaces with Inequality Constraints
    2015 Mar • SIAM CSE
    minisymposium organizer
  33. FLiER: Practical Topology Error Correction Using Sparse PMUs
    2015 Feb • ARPAe Innovation Summit, National Harbor, MD
    poster
  34. Music of the Microspheres
    2014 Jun • Householder Symposium
    invited plenary
  35. Eigenvalue Localization and Applications
    2014 Apr • NEP14 Workshop
    invited
  36. An Efficient Solver for Sparse Linear Systems based on Rank-Structured Cholesky Factorization
    2013 Jul • Workshop on Forty Years of Nested Dissection, University of Waterloo
  37. Some perturbation theorems for nonlinear eigenvalue problems
    2013 Jan • Workshop on Dissipative Spectral Theory, Cardiff
    invited
  38. Computer Aided Design of Micro-Electro-Mechanical Systems
    2012 Dec • SCMS Workshop on Recent Advances in Scientific Computing, Fudan University
    invited
  39. Computer Aided Design of Micro-Electro-Mechanical Systems
    2012 Dec • FIST Workshop at Shanghai Tech
    invited
  40. From Networks to Numerical Linear Algebra
    2012 Oct • NYCAM
    organizer
  41. Numerical Analysis of Resonances
    2012 Sep • Weyl at 100 Workshop (Fields Institute)
    invited
  42. AxFEM: Micro-Gyro Simulation and Modeling
    2012 Jul • DARPA MRIG Program Meeting
  43. Analyzing Resonances via Nonlinear Eigenvalues
    2011 Jul • ICIAM
    minisymposium invited
  44. Matrix Factorizations for Computer Network Tomography
    2011 Jul • Householder Symposium
    invited plenary
  45. Integrating Multiphysics and Multiscale Modeling Environment Together
    2011 May • DSRC Meeting, Alexandria
    invited
  46. Structure-Preserving Model Reduction for MEMS
    2011 Mar • SIAM CSE Meeting
    minisymposium invited
  47. Resonances: Interpretation, Computation, and Perturbation
    2010 Jul • Workshop in honor of Pete Stewart at UT Austin
    invited
  48. Structure-Preserving Model Reduction for MEMS Modeling
    2010 Jul • SIAM Annual Meeting
    minisymposium invited
  49. Finite Element Software for Bone Deformation and Failure
    2010 Apr • BTHSCA1 Workshop, UCLA IPAM
    invited
  50. Bounds and Error Estimates for Resonance Problems
    2009 Jul • SIAM Annual Meeting
    minisymposium invited
  51. Numerical Methods for Resonance Calculations
    2009 Jul • MSRI Workshop on Resonances
    invited
  52. Numerical Methods for Resonance Calculations
    2008 Oct • BIRS Resonance Workshop
    invited
  53. Computer-Aided Design for Micro-Electro-Mechanical Systems
    2008 Jun • Householder Symposium (Householder Award Talk)
    invited plenary
  54. Error Bounds and Error Estimates for Nonlinear Eigenvalue Problems
    2008 Jun • Householder Symposium
    minisymposium invited
  55. Structure Preserving Model Reduction for Damped Resonant MEMS
    2007 Jul • USNCCM
    minisymposium invited
  56. Continuation of Sparse Eigendecompositions
    2007 Feb • SIAM CSE
    minisymposium organizer
  57. Model Reduction and Mode Computation for Damped Resonant MEMS
    2007 Feb • SIAM CSE
    minisymposium invited
  58. Modeling Resonant Microsystems
    2006 May • Abel Symposium
    invited
  59. Elastic PMLs for Resonator Anchor Loss Simulation
    2005 Jul • US National Conference on Computational Mechanics
    minisymposium invited
  60. Eigenproblems in Resonant MEMS Design
    2005 Jul • SIAM Annual Meeting
    minisymposium invited
  61. Continuation of Invariant Subspaces of Sparse Parameter-Dependent Matrices
    2005 May • Householder Symposium
    invited plenary
  62. Fast Hessenberg QR Iteration for Companion Matrices
    2004 Jul • SIAM Annual Meeting
    minisymposium invited
  63. Reduced Order Models in Microsystems and RF MEMS
    2004 Jun • PARA 2004
    minisymposium invited
  64. Simulating RF MEMS
    2004 Mar • Bay Area Scientific Computing Day
    invited
  65. Fast QR Iteration for Companion Matrices
    2003 Jul • SIAM Linear Algebra Meeting
    minisymposium invited
  66. SUGAR: A MEMS Simulation Program
    2002 Apr • MSM 2002
    tutorial

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 Rank-structured Cholesky for fast PDE solves
AxFEM Fast simulation of near-axisymmetric 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 MATLAB-like mini-language for fast inner loops in C
HiQLab Finite element analysis of damping in high-frequency MEMS
SUGAR System-level simulation software for MEMS
CLAPACK 3.0 C interfaces to the LAPACK linear algebra library

Teaching

F24: CS 5220 Applications of Parallel Computers
F23: CS 6241 Numerical Methods for Data Science
S23: CS 4220/5223 / MATH 4260 Numerical Analysis: Linear and Nonlinear Problems
F22: CS 6210 Matrix Computations
S22: CS 4220/5223 / MATH 4260 Numerical Analysis: Linear and Nonlinear Problems
S21: CS 6241 Numerical Methods for Data Science
F20: CS 5220 Applications of Parallel Computers
S20: CS 4220/5223 / MATH 4260 Numerical Analysis: Linear and Nonlinear Problems
F19: CS 6210 Matrix Computations
Summer19: SJTU CS 259 Numerical Methods for Data Science
Summer18: SJTU CS 259 Numerical Methods for Data Science
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 ILAS (International Linear Algebra Society)
Member AMS (American Mathematical Society)
Member ACM (Association for Computing Machinery)
Member IEEE (Institute of Electrical and Electronics Engineers)

Service

External Activities

2024 Area Chair NeurIPS 2024
2024-present Editor NA Digest
2023-2024 Committee chair 2024 SIAG/DATA Career and Early Career Prize committee
2025 Committee member Local organizing committee, Householder XXII Meeting
2025 Co-chair Program committee, SIAM Computational Science and Engineering 2025
2023-2024 Committee member SIAM Nominating Committee
2022 Reviewer ICLR 2023
2022 Program committee member MLSys 2023
2022 Committee member Program committee, SIAM Network Science 2022
2022 Committee member 2023 SIAG/CSE Early Career Prize Selection Committee
2022 Committee member Organizing Committee, SIAM Mathematics of Data Science 2022
2022 Senior PC member ACM KDD
2022 Reviewer ICML 2022
2022 Reviewer AISTATS 2022
2021-2023 Associate editor SIAM Journal of Scientific Computing
2021 Reviewer ICLR 2022
2021 Reviewer ICML 2021
2021 PC member UAI 2021
2021 Senior PC member ACM KDD
2020 Reviewer ICLR 2020 reviewer
2020 Reviewer NeurIPS 2020 reviewer
2020 Reviewer ICML 2020 reviewer
2019 Committee member Program committee for SIAM CSC
2019 Reviewer NeurIPS 2019 reviewer
2019 Reviewer ICML 2019 reviewer
2018 Program committee member 2nd Black in AI Workshop
2018 Scientific committee co-chair SIAM Applied Linear Algebra Conference
2017 Program committee member IEEE International Parallel and Distributed Processing Symposium
2016 Minisymposium organizer SIAM Annual Meeting
2016 Program committee member IEEE International Parallel and Distributed Processing Symposium
2015 Program committee member IEEE International Parallel and Distributed Processing Symposium
2015 Organizing committee member Workshop on Development of Modern Methods for Linear Algebra
2015-present Scientific committee member Householder Symposium on Numerical Linear Algebra
2014 Poster commitee member Supercomputing
2013 Local organizer Fourth New York Conference on Applied Mathematics
2013 Technical program committee member Supercomputing
2012-2015 Secretary SIAM Activity Group on Linear Algebra
2012 Organizing committee member Third New York Conference on Applied Mathematics
2011 Organizing committee member Second New York Conference on Applied Mathematics
2017-2020 Associate editor Journal of Computational Mathematics
2010-present Editor Numerical Linear Algebra with Applications
2008-present Managing editor Electronic Transactions on Numerical Analysis
2007 Minisymposium organizer SIAM Computational Science and Engineering Meeting
2002-2004 Secretary IEEE 754R Standard Revision Committee

Local Activities

2024-2025 Committee member CS Graduate Admissions Committee
2024 Faculty lead ACSU Research Night
2022 Committee member Grad Student Advisor Feedback Task Force phase 2
2022 Committee member Cornell Engineering Teaching Award Committee
2022 Committee member Implementation committee, Cornell undergrad educational requirements on race and equity
2021-2022 Committee member CS recruiting committee
2021 Committee member COE Research Excellence Awards Committee
2021 Committee member Grad Student Advisor Feedback Task Force
2021 Reviewer CIDA RIF reviewer
2021 Committee member Part-Time Bachelor's Degree Committee
2021-2023 Associate Dean for DEI College of Computing and Information Science
2020-2025 Director Center for Applied Mathematics
2020 Committee member CIDA Website Dev Committee
2020 Reviewer CIDA RIF reviewer
2019-2021 Committee member Cornell English Language Support Office Advisory Board
2019-2020 Committee member CIS Dean Search Committee
2019-2020 Committee member Applied Math Graduate Admissions Committee
2019-present Committee member Applied Math Membership Committee
2019-2020 Committee chair CS Graduate Admissions Committee
2019-present Committee member CS Diversity, Inclusion, and Climate Committee
2017-2018 External committee member ECE/CAM Faculty Recruiting Committee
2017-2018 Committee member CS Chair Search Committee
2017-2018 Committee chair CS Graduate Admissions Committee
2017-2017 Committee member CS Colloquium Committee
2017-2017 Committee Member Applied Math Graduate Admissions Committee
2016-2017 Committee member CS Faculty Recruiting Committee
2015-2016 Committee member CS Graduate Admissions
2015 Committee member Applied Math Curriculum Review Committee
2014 Judge BigRed Hacks
2013-2014 Committee member Applied Math Graduate Admissions
2011-2012 Committee member Applied Math Graduate Admissions
2011-2014 Committee member Cornell Faculty Advisory Board on Information Technology
2010-2011 Committee member CS Graduate Admissions
2010-2011 Committee member Applied Math Graduate Admissions
2009-2010 Committee member CS Graduate Admissions
2009-2010 Committee member Applied Math Graduate Admissions
2009-present Organizer Cornell Scientific Computing and Numeric Seminar

Review Activity

ACM Journal on Emerging Technologies in Computing Systems 2014
ACM Transactions on Mathematical Software 2021 2020 2017 2016 2015 2014 2013
American Mathematical Monthly 2015
Autonomous Agents and Multi-Agent Systems 2022
SIAM Journal on Applied Mathematics 2016
SIAM Journal on Matrix Analysis 2019 2018 2015 2014 2012 2009 2008 2007 2006 2005
SIAM Journal on Multiscale Modeling and Simulation 2012
SIAM Journal on Scientific Computing 2019 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
Data Mining and Knowledge Discovery 2019 2018
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 2023 2022 2021 2016 2015 2012 2011
Journal of Experimental Algorithms 2019
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 2022 2021 2020 2018 2017 2015 2014 2013 2010 2009 2003
Mathematics of Computation 2007
Multiscale Modeling and Simulation 2013
Numerical Linear Algebra with Applications 2023 2022 2021 2019 2018 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 Domain-Specific 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 2022
Proposal referee for NSF 2023 2021 2019 2018 2017 2016 2012
Proposal referee for NASA 2017
Proposal referee for NSERC 2023 2019

Students and Postdoctoral Associates

Postdoctoral associates

Silke Glas
Ph.D., Ulm University, 2018
Optimization of stellarators

PhD students

Caira Anderson
Applied Math
MHD stability in stellarators
Michael Czekanski
Statistics
Monte Carlo transport calculations for stellarators
Darian Nwankwo
Computer Science
Transformed kernel methods for prediction and optimization
Calvin Tolbert
ORIE
Bayesian optimization
Ariel Kellison
Computer Science
Ph.D., 2024
Typed-Based Approaches to Rounding Error Analysis
Co-advised (secondary advisor: Andrew Appel)
Max Ruth
Applied Math
Ph.D., 2024
Numerical Methods for Identifying Integrability with Applications in Plasma Confinement
Xinran Zhu
Applied Math
Ph.D., 2024
Scalable Gaussian processes and Bayesian optimization with application to hyperparameter tuning
Misha Padidar
Applied Math
Ph.D., 2023
Challenges in the optimization-aided design of magnetic confinement systems
Eric Lee
Computer Science
Ph.D., 2020
Budget-Constrained Bayesian Optimization
Kun Dong
Applied Math
Ph.D., 2019
Randomized Numerical Linear Algebra for Large-Scale Matrix Data
David Eriksson
Applied Math
Ph.D., 2018
Scalable kernel methods and their use in black-box optimization
Co-advised (secondary advisor: Christine Shoemaker)
Moontae Lee
Computer Science
Ph.D., 2018
Joint-stochastic spectral inference for robust co-occurrence modeling and latent topic analysis
Co-advised (primary advisor: David Mimno)
Amanda Hood
Applied Math
Ph.D., 2017
Localizing the eigenvalues of matrix-valued functions: analysis and applications
Colin Ponce
Computer Science
Ph.D., 2016
Network-Structured Error Flattening for Power Grids and Other Real-World Networks
Erdal Yilmaz
Applied Physics
Ph.D., 2016
Design, Analysis and Simulation of Microscale Solid-Wave Gyroscopes
Research advisor (formally advised by Richard Lovelace)

Masters students

Cyrus Rohani
Computer Science
M.Eng.,
Ankit Lakkapragada
Computer Science
M.Eng.,
Rohan Shah
Computer Science
M.Eng.,
Rohit Valiveti
Computer Science
M.Eng.,
Felix Hohne
Computer Science
M.Eng., 2023
Interfacing DESC with Julia
Sahil Dev
Computer Science
M.Eng., 2022
Streamlining Spark Cluster Setup with Flintrock
Junyoung Lim
Computer Science
M.Eng., 2021
Learning to Cluster
Erik Louie
Computer Science
M.Eng., 2021
Learning to Cluster
Kevin Chaudhuri
Computer Science
M.Eng., 2020
Matrix exponentials in modeling electron spin resonance spectra
Yuanxi Shen
Computer Science
M.Eng., 2020
Fast Bayesian Transformed Gaussian Prediction
Sungjun Cho
Computer Science
M.S., 2020
Robust and Scalable Spectral Topic Modeling for Large Vocabularies
Bingqing Ma
Computer Science
M.Eng., 2018
Web Interface to a Finite Element Analysis Program
Alvin Zhu
Computer Science
M.Eng., 2018
Fast non-negative 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 Pre-Emptible VMs
Joel Lubitinsky
Computer Science
M.Eng., 2017
Resource-Coupled Evolutionary Games
Ioana-Maria Tamas
Computer Science
M.Eng., 2017
Resource-Coupled 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
Etch-a-Sketch 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
Edge-Weighted Parameterized PageRank: A Demo
Markus Salasoo
Computer Science
M.Eng., 2016
Edge-Weighted 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
Edge-Weighted Parameterized PageRank: A Demo
Chen Ting-Hao
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
Chen-Yi 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

Ethan Hersch Multifidelity Bayesian Optimization (2024)
Alkis Bouklas Nonlinear Eignvalues for Periodic Potential Eigenvalue Problems (2023)
Chad Yu Walk on Spheres (2023)
Yeuk Yin (Roy) Lam Varying GP Length Scales with Height Fields (2023)
Austin Zhao Stellarator Computations (2023)
Tejal Nair Variational Gaussian Processes (2023)
Tony Xu Stability-Constrained Optimization for Stellarators (2023)
Sean Yang Near-Axis Expansion of Stellarators in Julia (2023)
Stella Dang Soliton Stability (2022)
Paco Rilloraza Stellarator Optimization (2020)
Catherine Horng Learning to Cluster (2020)
Shengye Zang Learning to Cluster (2020)
Andrew Yates Nonlinear Eigenvalue Problems and Traveling Wave Stability (2020)
Ziwei Gu Learning to Cluster (2020)
Leo Huang Fast Bayesian Transformed Gaussian Prediction (2019)
Cameron Ibrahim Fast Bayesian Transformed Gaussian Prediction (2019)
Sungjun Cho Spectral Topic Modeling (2017)
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 (2015-16)
Jooyoung Park Maximum Entropy Method Implementation in MATLAB (2015)
Sheroze Sherifdeen MatScat for Python (2015-16)
Nimit Sohoni Review of the FEAST Eigensolver (2015)
Leon Davis Diagonal Completion for Low-Rank Matrices (2015)
Greg Rosenthal PageRank with Random Edge Weights (2015)
Eric Ma Graph Analysis via Spectral Histograms (2015)
Brandon Hartz Fast PageRank on Parameter-Dependent Graphs (2014)
Marshall Jiang Randomly Projected GMRES (2014-15)
Kyu-Young Kim Evaluating Overlapping Community Detection via Matrix Factorizations (2011-12)
Jiexun Xu Fast Factorizations for Network Tomography (2008)
Iva Vukicevic Error Bounds and Estimates for a Discrete Sine-Gordon 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

  1. Julian Bellavita (Computer Science)
  2. Jonah Botvinivk-Greenhouse (Applied Math)
  3. Jacob Brown (Applied Math)
  4. Poompol Buathong (Applied Math)
  5. Aditya Chetan (Computer Science)
  6. Michael Czeskanski (Statistics)
  7. Yuanqi Du (Computer Science)
  8. Youssef Fahmy (Statistics)
  9. Tayler Fernandes Nuñez (Applied Math)
  10. Mallory Gaspard (Applied Math)
  11. Arnav Gupta (Theoretical and Applied Mechanics)
  12. Alon Jacobson (ORIE)
  13. Kapil Khanal (Systems Engineering)
  14. Si Yi Meng (Computer Science)
  15. Vaibhav Mehta (Computer Science)
  16. Mohammad Mousavi (Mechanical Engineering)
  17. Darian Nwankwo (Computer Science)
  18. Shawn Ong (Applied Math)
  19. Cade Sbrocco (Physics)
  20. Jiatian Sun (Computer Science)
  21. Katerina Tang (Applied Math)
  22. Calvin Tolbert (ORIE)
  23. Albert Tseng (Computer Science)
  24. Qian Xie (Operations Research)
  25. Yi Xu (Computer Science)
  26. Yunxiang Zhang (Operations Research)
  27. Jennifer Zvonek (Applied Math)

Graduated

Tushaar Gangavarapu
Computer Science
M.S., 2024
Linear recurrent models for robust and interpretable long-context modeling
Ariel Kellison
Computer Science
Ph.D., 2024
Typed-Based Approaches to Rounding Error Analysis
Junxiong Wang
Computer Science
Ph.D., 2024
Tuning Data System using Reinforcement Learning
Xinchen Xu
Applied Math
Ph.D., 2024
Interaction Patterns and Collective Outcomes in Network Systems
Aaron Wheeler
Chemical Engineering
Ph.D., 2024
Generative Models for Financial Market Simulation
Shriya Nagpal
Applied Math
Ph.D., 2024
Synchronization in Networks of Coupled Phase Oscillators: From Designing for Robustness to Exploring Emergent Patterns
Chiatai Chen
Applied Physics
Ph.D., 2024
Effects of Pulsed Magnetic Mirror on Wire Array Z-Pinch Precursor Dynamics and X-Ray Generation
Max Ruth
Applied Math
Ph.D., 2024
Numerical Methods for Identifying Integrability with Applications in Plasma Confinement
Xinran Zhu
Applied Math
Ph.D., 2024
Scalable Gaussian processes and Bayesian optimization with application to hyperparameter tuning
Yujia Zhang
Applied Math
Ph.D., 2024
Safe University Instruction During COVID-19: Simulation, Statistics, and Uncertainty Quantification
Yandong Li
Applied Physics
Ph.D., 2023
Towards Robust Photonic Information Processing -- Fundamentals, Designs, Limitations, and Improvements
Yuchen Xu
Statistics
Ph.D., 2023
Statistical Advances in Simultaneous Diagonalization and Joint Object Detection
Dongping Qi
Applied Math
Ph.D., 2023
Challenges in Continuous Path Planning: Rarefactions, Uncertainty, and Reinforcement Learning
Yurong You
Computer Science
Ph.D., 2023
Enhancing 3D Perception with Unlabeled Repeated Historical Data for Autonomous Vehicles
Misha Padidar
Applied Math
Ph.D., 2023
Challenges in the optimization-aided design of magnetic confinement systems
Christophe Bonneville
Civil Engineering
Ph.D., 2023
Bayesian Machine Learning Algortihms for Uncertainty Quantification, Optimization, and Equation Discoveries in Engineering Physics
Max Lipton
Mathematics
Ph.D., 2023
Dynamical Systems in Pure Mathematics
Jikun Wang
Mechanical Engineering
Ph.D., 2023
Time-dependent Damage of Soft Materials with Bond Breaking and Healing Kinetics
Raul Astudillo Marban
Operations Research
Ph.D., 2022
Exploting Composite Functions in Bayesian Optimization
Mengqi Xia
Computer Science
Ph.D., 2022
Physically Realistic Rendering of Complex Materials Using Wave Optics
Qinru Shi
Applied Math
Ph.D., 2022
Combinatorial Optimization and Decision-Making with Applications in Computational Sustainability
Sebastian Ament
Computer Science
Ph.D., 2022
Advances in Bayesian and Sparse Optimization for Autonomous Scientific Discovery
John Ryan
Computer Science
Ph.D., 2022
Fast Kernel Matrix Approximations by Series Expansions
Hubert Lin
Computer Science
Ph.D., 2022
Towards Robust Visual Perception Systems in Real-World Environments
Tianyi Shi
Applied Math
Ph.D., 2022
Tensor Computations with Dimensionality Manipulations
Andrew Horning
Applied Math
Ph.D., 2021
Computing Spectral Properties of Infinite-Dimensional Operators
Fujun Luan
Computer Science
Ph.D., 2021
Forward and Inverse Rendering with Gradient-Based Optimization
Ankita Mukhtyar
Chemical Engineering
Ph.D., 2021
Towards Understanding the Disorder to Order Transitions in Soft Materials
Junteng Jia
Computer Science
Ph.D., 2021
Modeling and Learning Attributed Graphs
Gabriela Calinao Correa
Material Science
M.S., 2020
Direct electron detectors: architecture and algorithms
Aasim Ayaz Wani
Chemical Engineering
M.S., 2020
Computer Aided Retrosynthesis for Metabolic Pathways
Eric Lee
Computer Science
Ph.D., 2020
Budget-Constrained Bayesian Optimization
Chaitali Joshi
Physics
Ph.D., 2020
Frequency Domain Quantum Processing via Four-Wave Mixing
Enrique Rojas
Atmospheric Science
Ph.D., 2020
Farley-Buneman instabilities in the auroral region: Continuous hybrid simulations and empirical modeling.
Saul Toscano
Operations Research
Ph.D., 2019
Grey-Box Bayesian Optimization: Improving Performance by Looking Inside the Black-Box
Calvin Wylie
Operations Research
Ph.D., 2019
Partly Smooth Models and Algorithms
Kun Dong
Applied Math
Ph.D., 2019
Randomized Numerical Linear Algebra for Large-Scale Matrix Data
Marc Gilles
Applied Math
Ph.D., 2019
At the intersection of differential equations and optimization: inverse problems, path planning and Krylov subspaces
Shreyas Honrao
Material Science
Ph.D., 2018
DFT study of the complex diffusion of oxygen in cobalt and machine learning of ab-initio energy landscapes for crystal structure predictions.
David Eriksson
Applied Math
Ph.D., 2018
Scalable kernel methods and their use in black-box optimization
Sheng Wang
Mechanical Engineering
Ph.D., 2018
Towards large-scale simulations of two-phase flows with moving contact lines in complex geometries
Yu Su
Chemical Engineering
Ph.D., 2018
Modeling many-body hydrodynamic interactions in concentrated colloidal suspensions via large-scale dynamic simulations
Moontae Lee
Computer Science
Ph.D., 2018
Joint-stochastic spectral inference for robust co-occurrence modeling and latent topic analysis
Jiayi Guo
Operations Research
Ph.D., 2018
Smooth Quasi-Newton Methods for Nonsmooth Optimization
Benjamin Revard
Material Science
Ph.D., 2017
Development of an Evolutionary Algorithm for the Ab Initio Discovery of Two-Dimensional Materials
Nicholas Savva
Computer Science
M.S., 2017
A Practical Framework for Measuring and Modeling the Appearance of Strongly Anisotropic Materials
Zachary Clawson
Applied Math
Ph.D., 2017
Shortest Path Problems: Domain Restriction, Anytime Planning, and Multi-Objective Optimization
Amanda Hood
Applied Math
Ph.D., 2017
Localizing the eigenvalues of matrix-valued functions: analysis and applications
Sepehr Saroukhani
Civil Engineering
Ph.D., 2017
Atomistic Modeling of Dislocation Motion at Experimental Time-Scales
Michael Meyer
Computational Biology
Ph.D., 2017
Methods for Functional Inference in the Proteome and Interactome
William Nicholson
Statistics
Ph.D., 2016
Tools For Modeling Sparse Vector Autoregressions
Kyle Wilson
Applied Math
Ph.D., 2016
Robustly Modeling The World From Photos
Danielle Toupo
Applied Math
Ph.D., 2016
Nonlinear Dynamics Of Cycles In Evolutionary Games
Colin Ponce
Computer Science
Ph.D., 2016
Network-Structured Error Flattening For Power Grids And Other Real-World Networks
Erdal Yilmaz
Applied and Engineering Physics
Ph.D., 2016
Design, Analysis And Simulation Of Microscale Solid-Wave Gyroscopes
Shuo Chen
Computer Science
Ph.D., 2016
Representation Learning For Sequence And Comparison Data
Manuel Diaz
Civil Engineering
Ph.D., 2015
A Modified Error In Constitutive Equation Approach For Viscoelasticity Imaging With Interior Data
Parvez Sukheswalla
Mechanical Engineering
Ph.D., 2015
Computational Investigation Of The Dynamics Of Inertial Particles In Homogeneous Turbulent Shear Flow
Hyung Joo Park
Applied Math
Ph.D., 2015
Topics In Structure Determination Of Submicron Sized Objects
Wenlei Xie
Computer Science
Ph.D., 2015
Iterative Graph Computation In The Big Data Era
Tao Zou
Computer Science
Ph.D., 2015
Optimizing Response Time For Distributed Applications In Public Clouds
Santoshkalyan Rayadhurgam
Chemical Engineering
M.S., 2015
Computational Study Of Charge Conducting Spacer Molecules In Leadchalcogenide Quantum Dots
Shashank Adimulam
Electrical Engineering
M.S., 2015
Hardware Model Of A Mixed Radix Fast Fourier Transform For LTE 3Gpp
Laura Fegely
Electrical Engineering
Ph.D., 2014
Goblits To OMG: 3D Fabrication Techniques For An Opto-Mechanical Gyroscope
James Warner
Civil Engineering
Ph.D., 2014
Advances In Uncertainty Quantification And Inverse Problems In Computational Mechanics
Adam Chacon
Applied Math
Ph.D., 2014
Eikonal Equations: New Two-Scale Algorithms And Error Analysis
Anthony Sabelli
Applied Math
Ph.D., 2013
Novel Methods For Source Localization And Material Identification
Ilias Bilionis
Applied Math
Ph.D., 2013
Bayesian Methods For Uncertainty Quantification
Guozhang Wang
Computer Science
Ph.D., 2013
Automatic Scaling Iterative Computations
Jeffrey Chadwick
Computer Science
Ph.D., 2013
Sound Synthesis For Physics-Based Computer Animation
David Rowinski
Mechanical Engineering
Ph.D., 2013
Calculations Of Turbulent Reacting Flows Using PDF Methods
Ananth Kaushik
Chemical Engineering
Ph.D., 2013
A Computational Study Of The Molecular And Electronic Structure Of Self-Assembled Nanocrystal Superlattices
Ryan Peterson
Computer Science
Ph.D., 2012
Efficient Content Distribution With Managed Swarms