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
Lopez, Jose Gutierrez; Pypker, Thomas; Licata, Julian; Burgess, Stephen S. O.; Asbjornsen, Heidi(
, Plant and Soil)
AbstractBackground
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.
Cáceres, Manuel; Cairo, Massimo; Grigorjew, Andreas; Khan, Shahbaz; Mumey, Brendan; Rizzi, Romeo; Tomescu, Alexandru I.; Williams, Lucia(
, ACM Transactions on Algorithms)
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.
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.
Flores‐Escobar, Elizabeth; Sanpera, Carolina; Jover, Lluís; Cortés‐Ortiz, Liliana; Rangel‐Negrín, Ariadna; Canales‐Espinosa, Domingo; Dias, Pedro Américo D.(
, American Journal of Physical Anthropology)
AbstractObjectives
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.
Deweese, Kevin, Gilbert, John R, Miller, Gary, Peng, Richard, Xu, Hao Ran, and Xu, Shen Chen. An Empirical Study of Cycle Toggling Based Laplacian Solvers. Retrieved from https://par.nsf.gov/biblio/10040899. Proceedings of the Seventh SIAM Workshop on Combinatorial Scientific Computing . Web. doi:10.1137/1.9781611974690.ch4.
Deweese, Kevin, Gilbert, John R, Miller, Gary, Peng, Richard, Xu, Hao Ran, & Xu, Shen Chen. An Empirical Study of Cycle Toggling Based Laplacian Solvers. Proceedings of the Seventh SIAM Workshop on Combinatorial Scientific Computing, (). Retrieved from https://par.nsf.gov/biblio/10040899. https://doi.org/10.1137/1.9781611974690.ch4
Deweese, Kevin, Gilbert, John R, Miller, Gary, Peng, Richard, Xu, Hao Ran, and Xu, Shen Chen.
"An Empirical Study of Cycle Toggling Based Laplacian Solvers". Proceedings of the Seventh SIAM Workshop on Combinatorial Scientific Computing (). Country unknown/Code not available. https://doi.org/10.1137/1.9781611974690.ch4.https://par.nsf.gov/biblio/10040899.
@article{osti_10040899,
place = {Country unknown/Code not available},
title = {An Empirical Study of Cycle Toggling Based Laplacian Solvers},
url = {https://par.nsf.gov/biblio/10040899},
DOI = {10.1137/1.9781611974690.ch4},
abstractNote = {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.},
journal = {Proceedings of the Seventh SIAM Workshop on Combinatorial Scientific Computing},
author = {Deweese, Kevin and Gilbert, John R and Miller, Gary and Peng, Richard and Xu, Hao Ran and Xu, Shen Chen},
}
Warning: Leaving National Science Foundation Website
You are now leaving the National Science Foundation website to go to a non-government website.
Website:
NSF takes no responsibility for and exercises no control over the views expressed or the accuracy of
the information contained on this site. Also be aware that NSF's privacy policy does not apply to this site.