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.
; ; ; ; ;
Award ID(s):
Publication Date:
Journal Name:
Proceedings of the Seventh SIAM Workshop on Combinatorial Scientific Computing
Page Range or eLocation-ID:
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract Background

    As sap flow research expands, new challenges such as fast sap flows or flows co-occurring with freeze/thaw cycles appear, which are not easily addressed with existing methods. In order to address these new challenges, sap flow methods capable of measuring bidirectional, high and slow sap flux densities (Fd, cm3cm−2 h−1), thermal properties and stem water content with minimum sensitivity to stem temperature are required.


    In this study we assessed the performance of a new low-power ratio-based algorithm, the maximum heat ratio (MHR) method, and compare it with the widely known heat ratio (HR) method using a cut-tree study to test it under high flows usingEucalyptus grandistrees, and a freeze/thaw experiment usingAcer saccharumtrunks to test its response to fast changing stem temperatures that result in freeze/thaw cycles.


    Our results indicate that MHR and HR had a strong (R2 = 0.90) linear relationship within aFdrange of 0–45 cm3 cm−2 h−1. Using the MHR algorithm, we were able to estimate wood thermal properties and water content, while extending the measuring range of HR to approximately 0–130 (cm3cm−2 h−1). In our freeze/thaw experiment, the main discrepancy between MHR and HR was observed during freezing, where HR had consistently lowerFd(up to 10 cm3 cm−2 h−1), with respect to MHR. However, both algorithmsmore »identified similar zero flows.


    Consequently, MHR can be an easy-to-implement alternative algorithm/method capable of handling extreme climatic conditions, which can also run simultaneously with HR.

    « less
  2. Cycle representatives of persistent homology classes can be used to provide descriptions of topological features in data. However, the non-uniqueness of these representatives creates ambiguity and can lead to many different interpretations of the same set of classes. One approach to solving this problem is to optimize the choice of representative against some measure that is meaningful in the context of the data. In this work, we provide a study of the effectiveness and computational cost of several ℓ 1 minimization optimization procedures for constructing homological cycle bases for persistent homology with rational coefficients in dimension one, including uniform-weighted and length-weighted edge-loss algorithms as well as uniform-weighted and area-weighted triangle-loss algorithms. We conduct these optimizations via standard linear programming methods, applying general-purpose solvers to optimize over column bases of simplicial boundary matrices. Our key findings are: 1) optimization is effective in reducing the size of cycle representatives, though the extent of the reduction varies according to the dimension and distribution of the underlying data, 2) the computational cost of optimizing a basis of cycle representatives exceeds the cost of computing such a basis, in most data sets we consider, 3) the choice of linear solvers matters a lot to themore »computation time of optimizing cycles, 4) the computation time of solving an integer program is not significantly longer than the computation time of solving a linear program for most of the cycle representatives, using the Gurobi linear solver, 5) strikingly, whether requiring integer solutions or not, we almost always obtain a solution with the same cost and almost all solutions found have entries in { ‐ 1,0,1 } and therefore, are also solutions to a restricted ℓ 0 optimization problem, and 6) we obtain qualitatively different results for generators in Erdős-Rényi random clique complexes than in real-world and synthetic point cloud data.« less
  3. Abstract

    We present two accurate and efficient algorithms for solving the incompressible, irrotational Euler equations with a free surface in two dimensions with background flow over a periodic, multiply connected fluid domain that includes stationary obstacles and variable bottom topography. One approach is formulated in terms of the surface velocity potential while the other evolves the vortex sheet strength. Both methods employ layer potentials in the form of periodized Cauchy integrals to compute the normal velocity of the free surface, are compatible with arbitrary parameterizations of the free surface and boundaries, and allow for circulation around each obstacle, which leads to multiple-valued velocity potentials but single-valued stream functions. We prove that the resulting second-kind Fredholm integral equations are invertible, possibly after a physically motivated finite-rank correction. In an angle-arclength setting, we show how to avoid curve reconstruction errors that are incompatible with spatial periodicity. We use the proposed methods to study gravity-capillary waves generated by flow around several elliptical obstacles above a flat or variable bottom boundary. In each case, the free surface eventually self-intersects in a splash singularity or collides with a boundary. We also show how to evaluate the velocity and pressure with spectral accuracy throughout the fluid,more »including near the free surface and solid boundaries. To assess the accuracy of the time evolution, we monitor energy conservation and the decay of Fourier modes and compare the numerical results of the two methods to each other. We implement several solvers for the discretized linear systems and compare their performance. The fastest approach employs a graphics processing unit (GPU) to construct the matrices and carry out iterations of the generalized minimal residual method (GMRES).

    « less
  4. 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 atmore »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.« less
  5. Uwe Sauer, Dirk (Ed.)
    ABSTRACT State of Charge (SoC) and discharge capacity of the batteries are parameters that cannot be determined directly from the battery monitoring and control system and requires estimation. Current and voltage sensors have inherent error and delay leading to inaccurate measurements leading to inaccurate SoC and discharge capacity estimations. These sensors also have an additional cost to the battery system. This paper proposes a sensorless approach to estimate parameters of Vanadium Redox Flow Batteries (VRFBs) for both CC and CV charging methods by estimating battery current in CV mode and terminal voltage in CC mode. The results of estimations by the sensorless approach show a maximum relative error of 0.0035 in estimating terminal voltage in CC charging and a maximum relative error of 0.045 in estimating charging current in CV mode. Furthermore, long- term operation of vanadium redox flow batteries causes ion diffusions across the membrane and the depletion of active materials, which leads to capacity fading in VRFBs and inaccurate SoC estimation. To address the inaccuracy of SoC estimation in the long-term use of the battery, the capacity fading model is also considered for VRFBs in this paper. Experimental results show a 19% electrolyte volume change in the positivemore »and negative tanks after 200 cycles of charge/discharge due to the bulk electrolyte transfer between the positive and negative sides of the battery system. This change of electrolyte volume results in 13.73% capacity fading after 200 cycles of charging/discharging. The SoC also changes by 7.1% after 200 cycles, due to the capacity and electrolyte volume loss, which shows the necessity of considering capacity fading in long-term use of the battery.« less