skip to main content

Title: An Empirical Study of Cycle Toggling Based Laplacian Solvers
We study the performance of linear solvers for graph Laplacians based on the combinatorial cycle adjustment methodology proposed by [Kelner-Orecchia-Sidford-Zhu STOC-13]. The approach finds a dual flow solution to this linear system through a sequence of flow adjustments along cycles. We study both data structure oriented and recursive methods for handling these adjustments. The primary difficulty faced by this approach, updating and querying long cycles, motivated us to study an important special case: instances where all cycles are formed by fundamental cycles on a length n path. Our methods demonstrate significant speedups over previous implementations, and are competitive with standard numerical routines.  more » « less
Award ID(s):
Author(s) / Creator(s):
; ; ; ; ;
Date Published:
Journal Name:
Proceedings of the Seventh SIAM Workshop on Combinatorial Scientific Computing
Page Range / eLocation ID:
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract

    Addressing challenges in urban water infrastructure systems, including aging infrastructure, supply uncertainty, extreme events, and security threats, depends highly on water distribution networks modeling emphasizing the importance of realistic assumptions, modeling complexities, and scalable solutions. In this study, we propose a derivative‐free, linear approximation for solving the network water flow problem. The proposed approach takes advantage of the special form of the nonlinear head loss equations, and, after the transformation of variables and constraints, the water flow problem reduces to a linear optimization problem that can be efficiently solved by modern linear solvers. Ultimately, the proposed approach amounts to solving a series of linear optimization problems. We demonstrate the proposed approach through several case studies and show that the approach can model arbitrary network topologies and various types of valves and pumps, thus providing modeling flexibility. Under mild conditions, we show that the proposed linear approximation converges. We provide sensitivity analysis and discuss in detail the current limitations of our approach and suggest solutions to overcome these. All the codes, tested networks, and results are freely available on Github for research reproducibility.

    more » « less
  2. Abstract Standard estimators of the global average treatment effect can be biased in the presence of interference. This paper proposes regression adjustment estimators for removing bias due to interference in Bernoulli randomized experiments. We use a fitted model to predict the counterfactual outcomes of global control and global treatment. Our work differs from standard regression adjustments in that the adjustment variables are constructed from functions of the treatment assignment vector, and that we allow the researcher to use a collection of any functions correlated with the response, turning the problem of detecting interference into a feature engineering problem. We characterize the distribution of the proposed estimator in a linear model setting and connect the results to the standard theory of regression adjustments under SUTVA. We then propose an estimator that allows for flexible machine learning estimators to be used for fitting a nonlinear interference functional form. We propose conducting statistical inference via bootstrap and resampling methods, which allow us to sidestep the complicated dependences implied by interference and instead rely on empirical covariance structures. Such variance estimation relies on an exogeneity assumption akin to the standard unconfoundedness assumption invoked in observational studies. In simulation experiments, our methods are better at debiasing estimates than existing inverse propensity weighted estimators based on neighborhood exposure modeling. We use our method to reanalyze an experiment concerning weather insurance adoption conducted on a collection of villages in rural China. 
    more » « less
  3. This paper discusses opportunities for developments in spatial clustering methods to help leverage broad scale community science data for building species distribution models (SDMs). SDMs are tools that inform the science and policy needed to mitigate the impacts of climate change on biodiversity. Community science data span spatial and temporal scales unachievable by expert surveys alone, but they lack the structure imposed in smaller scale studies to allow adjustments for observational biases. Spatial clustering approaches can construct the necessary structure after surveys have occurred, but more work is needed to ensure that they are effective for this purpose. In this proposal, we describe the role of spatial clustering for realizing the potential of large biodiversity datasets, how existing methods approach this problem, and ideas for future work. 
    more » « less
  4. Abstract It is now well established that changes in the zonal wind stress over the Antarctic Circumpolar Current (ACC) do not lead to changes in its baroclinicity nor baroclinic transport, a phenomenon referred to as “eddy saturation.” Previous studies provide contrasting dynamical mechanisms for this phenomenon: on one extreme, changes in the winds lead to changes in the efficiency with which transient eddies transfer momentum to the sea floor; on the other extreme, structural adjustments of the ACC’s standing meanders increase the efficiency of momentum transfer. In this study the authors investigate the relative importance of these mechanisms using an idealized, isopycnal channel model of the ACC. Via separate diagnoses of the model’s time-mean flow and eddy diffusivity, the authors decompose the model’s response to changes in wind stress into contributions from transient eddies and the mean flow. A key result is that holding the transient eddy diffusivity constant while varying the mean flow very closely compensates for changes in the wind stress, whereas holding the mean flow constant and varying the eddy diffusivity does not. This implies that eddy saturation primarily occurs due to adjustments in the ACC’s standing waves/meanders, rather than due to adjustments of transient eddy behavior. The authors derive a quasigeostrophic theory for ACC transport saturation by standing waves, in which the transient eddy diffusivity is held fixed, and thus provides dynamical insights into standing wave adjustment to wind changes. These findings imply that representing eddy saturation in global models requires adequate resolution of the ACC’s standing meanders, with wind-responsive parameterizations of the transient eddies being of secondary importance. 
    more » « less
  5. null (Ed.)
    This paper develops an ensemble learning-based linearization approach for power flow with reactive power modeled, where the polynomial regression (PR) is first used as a basic learner to capture the linear relationships between the bus voltages as the independent variables and the active or reactive power as the dependent variable in rectangular coordinates. Then, gradient boosting (GB) and bagging as ensemble learning methods are introduced to combine all basic learners to boost the model performance. The inferred linear power flow model is applied to solve the well-known optimal power flow (OPF) problem. The simulation results on IEEE standard power systems indicate that (1) ensemble learning methods can significantly improve the efficiency of PR, and GB works better than bagging; (2) as for solving OPF, the data-driven model outperforms the DC model and the SDP relaxation in both accuracy, and computational efficiency. 
    more » « less