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):
1637564
NSF-PAR ID:
10040899
Author(s) / Creator(s):
; ; ; ; ;
Date Published:
Journal Name:
Proceedings of the Seventh SIAM Workshop on Combinatorial Scientific Computing
Page Range / eLocation ID:
33-41
Format(s):
Medium: X
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.

    Purpose

    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.

    Results

    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 algorithms identified similar zero flows.

    Conclusion

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

     
    more » « less
  2. Minimum flow decomposition (MFD) is the NP-hard problem of finding a smallest decomposition of a network flow/circulationXon a directed graphGinto weighted source-to-sink paths whose weighted sum equalsX. We show that, for acyclic graphs, considering thewidthof the graph (the minimum number of paths needed to cover all of its edges) yields advances in our understanding of its approximability. For the version of the problem that uses only non-negative weights, we identify and characterise a new class ofwidth-stablegraphs, for which a popular heuristic is aO(logVal(X))-approximation (Val(X) being the total flow ofX), and strengthen its worst-case approximation ratio from\(\Omega (\sqrt {m})\)to Ω (m/logm) for sparse graphs, wheremis the number of edges in the graph. We also study a new problem on graphs with cycles, Minimum Cost Circulation Decomposition (MCCD), and show that it generalises MFD through a simple reduction. For the version allowing also negative weights, we give a (⌈ log ‖ X ‖ ⌉ +1)-approximation (‖X‖ being the maximum absolute value ofXon any edge) using a power-of-two approach, combined with parity fixing arguments and a decomposition of unitary circulations (‖X‖ ≤ 1), using a generalised notion of width for this problem. Finally, we disprove a conjecture about the linear independence of minimum (non-negative) flow decompositions posed by Kloster et al. [2018], but show that its useful implication (polynomial-time assignments of weights to a given set of paths to decompose a flow) holds for the negative version.

     
    more » « less
  3. 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 the 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. 
    more » « less
  4. Abstract Objectives

    Ecological similarity between species can lead to interspecific trophic competition. However, when ecologically similar species coexist, they may differ in foraging strategies and habitat use, which can lead to niche partitioning. As the body tissues of consumers contain a stable isotope signature that reflects the isotopic composition of their diet, stable isotope analysis is a useful tool to study feeding behavior. We measured the isotopic niche width, which is a proxy for trophic niche width, of mantled (Alouatta palliata) and black (A. pigra) howler monkeys. Specifically, studied populations in allopatry and sympatry to assess whether these species showed niche partitioning.

    Materials and Methods

    Between 2008 and 2012, we collected hair samples from 200 subjects (113 black and 87 mantled howler monkeys) and used continuous flow isotope ratio mass spectrometry to estimateδ13C andδ15N. We described the isotopic niche width of each species in allopatry and sympatry with the Bayesian estimation of the standard ellipse areas.

    Results

    In allopatry, isotopic niche width and isotopic variation were similar in both species. In sympatry, black howler monkeys had a significantly broader isotopic niche, which was mainly determined by highδ15N values, and included the majority of mantled howler monkeys' isotopic niche. The isotopic niche of mantled howler monkeys did not differ between sympatry and allopatry.

    Conclusions

    The coexistence of these ecologically similar species may be linked to trophic niche adjustments by one species, although the particular features of such adjustments (e.g., dietary, spatial, or sensory partitioning) remain to be addressed.

     
    more » « less
  5. Abstract

    Soil‐mantled landscapes subjected to rainfall, runoff events, and downstream base level adjustments will erode and evolve in time and space. Yet the precise mechanisms for soil erosion also will vary, and such variations may not be adequately captured by soil erosion prediction technology. This study sought to monitor erosion processes within an experimental landscape filled with packed homogenous soil, which was exogenically forced by rainfall and base level adjustments, and to define the temporal and spatial variation of the erosion regimes. Close‐range photogrammetry and terrain analysis were employed as the primary methods to discriminate these erosion regimes. Results show that (1) four distinct erosion regimes can be identified (raindrop impact, sheet flow, rill, and gully), and these regimes conformed to an expected trajectory of landscape evolution; (2) as the landscape evolved, the erosion regimes varied in areal coverage and in relative contribution to total sediment efflux measured at the outlet of the catchment; and (3) the sheet flow and rill erosion regimes dominated the contributions to total soil loss. Disaggregating the soil erosion processes greatly facilitated identifying and mapping each regime in time and space. Such information has important implications for improving soil erosion prediction technology, for assessing landscape degradation by soil erosion, for mapping regions vulnerable to future erosion, and for mitigating soil losses and managing soil resources. Copyright © 2017 John Wiley & Sons, Ltd.

     
    more » « less