Home  << 1 >> 
BenitezLlambay, P., Krapp, L., Ramos, X. S., & Kratter, K. M. (2023). RAM: Rapid Advection Algorithm on Arbitrary Meshes. Astron. J., 952(2), 106.
Abstract: The study of many astrophysical flows requires computational algorithms that can capture high Mach number flows, while resolving a large dynamic range in spatial and density scales. In this paper we present a novel method, RAM: Rapid Advection Algorithm on Arbitrary Meshes. RAM is a timeexplicit method to solve the advection equation in problems with large bulk velocity on arbitrary computational grids. In comparison with standard upwind algorithms, RAM enables advection with larger time steps and lower truncation errors. Our method is based on the operator splitting technique and conservative interpolation. Depending on the bulk velocity and resolution, RAM can decrease the numerical cost of hydrodynamics by more than one order of magnitude. To quantify the truncation errors and speedup with RAM, we perform one and twodimensional hydrodynamics tests. We find that the order of our method is given by the order of the conservative interpolation and that the effective speedup is in agreement with the relative increment in time step. RAM will be especially useful for numerical studies of disksatellite interaction, characterized by high bulk orbital velocities and nontrivial geometries. Our method dramatically lowers the computational cost of simulations that simultaneously resolve the global disk and potential well inside the Hill radius of the secondary companion.
Keywords: ORBITAL ADVECTION; MAGNETOHYDRODYNAMICS CODE; SCHEME; FLOWS; MHD; SIMULATIONS; FARGO; PPM

Feuilloley, L., Fraigniaud, P., Montealegre, P., Rapaport, I., Remila, E., & Todinca, I. (2021). Compact Distributed Certification of Planar Graphs. Algorithmica, 83(7), 2215–2244.
Abstract: Naor M., Parter M., Yogev E.: (The power of distributed verifiers in interactive proofs. In: 31st ACMSIAM symposium on discrete algorithms (SODA), pp 1096115, 2020. https://doi.org/10.1137/1.9781611975994.67) have recently demonstrated the existence of a distributed interactive proof for planarity (i.e., for certifying that a network is planar), using a sophisticated generic technique for constructing distributed IP protocols based on sequential IP protocols. The interactive proof for planarity is based on a distributed certification of the correct execution of any given sequential lineartime algorithm for planarity testing. It involves three interactions between the prover and the randomized distributed verifier (i.e., it is a dMAM protocol), and uses small certificates, on O(log n) bits in nnode networks. We show that a single interaction with the prover suffices, and randomization is unecessary, by providing an explicit description of a prooflabeling scheme for planarity, still using certificates on just O(log n) bits. We also show that there are no prooflabeling schemesin fact, even no locally checkable proofsfor planarity using certificates on o(log n) bits.

Feuilloley, L., Fraigniaud, P., Montealegre, P., Rapaport, I., Remila, E., & Todinca, I. (2023). Local certification of graphs with bounded genus. Discret Appl. Math., 325, 9–36.
Abstract: Naor, Parter, and Yogev [SODA 2020] recently designed a compiler for automatically translating standard centralized interactive protocols to distributed interactive protocols, as introduced by Kol, Oshman, and Saxena [PODC 2018]. In particular, by using this compiler, every lineartime algorithm for deciding the membership to some fixed graph class can be translated into a dMAM(O(log n)) protocol for this class, that is, a distributed interactive protocol with O(log n)bit proof size in nnode graphs, and three interactions between the (centralized) computationallyunbounded but nontrustable prover Merlin, and the (decentralized) randomized computationallylimited verifier Arthur. As a corollary, there is a dMAM(O(log n)) protocol for recognizing the class of planar graphs, as well as for recognizing the class of graphs with bounded genus.We show that there exists a distributed interactive protocol for recognizing the class of graphs with bounded genus performing just a single interaction, from the prover to the verifier, yet preserving proof size of O(log n) bits. This result also holds for the class of graphs with bounded nonorientable genus, that is, graphs that can be embedded on a nonorientable surface of bounded genus. The interactive protocols described in this paper are actually prooflabeling schemes, i.e., a subclass of interactive protocols, previously introduced by Korman, Kutten, and Peleg [PODC 2005]. In particular, these schn be computed a priori, at low cost, by the nodes themselves. Our results thus extend the recent prooflabeling scheme for planar graphs by Feuilloley et al. [PODC 2020], to graphs of bounded genus, and to graphs of bounded nonorientable genus.

Fraigniaud, P., Montealegre, P., Rapaport, I., & Todinca, I. (2023). Alert Results A MetaTheorem for Distributed Certification 5 of 28 A MetaTheorem for Distributed Certification. Algorithmica, Early Access.
Abstract: Distributed certification, whether it be prooflabeling schemes, locally checkable proofs, etc., deals with the issue of certifying the legality of a distributed system with respect to a given boolean predicate. A certificate is assigned to each process in the system by a nontrustable oracle, and the processes are in charge of verifying these certificates, so that two properties are satisfied: completeness, i.e., for every legal instance, there is a certificate assignment leading all processes to accept, and soundness, i.e., for every illegal instance, and for every certificate assignment, at least one process rejects. The verification of the certificates must be fast, and the certificates themselves must be small. A large quantity of results have been produced in this framework, each aiming at designing a distributed certification mechanism for specific boolean predicates. This paper presents a “metatheorem”, applying to many boolean predicates at once. Specifically, we prove that, for every boolean predicate on graphs definable in the monadic secondorder (MSO) logic of graphs, there exists a distributed certification mechanism using certificates on O(log(2) n) bits in nnode graphs of bounded treewidth, with a verification protocol involving a single round of communication between neighbors

Goles, E., & Montealegre, P. (2014). Computational complexity of threshold automata networks under different updating schemes. Theor. Comput. Sci., 559, 3–19.
Abstract: Given a threshold automata network, as well as an updating scheme over its vertices, we study the computational complexity associated with the prediction of the future state of a vertex. More precisely, we analyze two classes of local functions: the majority and the ANDOR rule (vertices take the AND or the OR logic functions over the state of its neighborhoods). Depending on the updating scheme, we determine the complexity class (NC, P, NP, PSPACE) where the prediction problem belongs. (C) 2014 Elsevier B.V. All rights reserved.

Goles, E., & Ruz, G. A. (2015). Dynamics of neural networks over undirected graphs. Neural Netw., 63, 156–169.
Abstract: In this paper we study the dynamical behavior of neural networks such that their interconnections are the incidence matrix of an undirected finite graph G = (V, E) (i.e., the weights belong to {0, 1}). The network may be updated synchronously (every node is updated at the same time), sequentially (nodes are updated one by one in a prescribed order) or in a blocksequential way (a mixture of the previous schemes). We characterize completely the attractors (fixed points or cycles). More precisely, we establish the convergence to fixed points related to a parameter alpha(G), taking into account the number of loops, edges, vertices as well as the minimum number of edges to remove from E in order to obtain a maximum bipartite graph. Roughly, alpha(G') < 0 for any G' subgraph of G implies the convergence to fixed points. Otherwise, cycles appear. Actually, for very simple networks (majority functions updated in a blocksequential scheme such that each block is of minimum cardinality two) we exhibit cycles with nonpolynomial periods. (C) 2014 Elsevier Ltd. All rights reserved.

Krapp, L., GarridoDeutelmoser, J., BenítezLlambay, P., & Kratter, K. M. (2024). A Fast Secondorder Solver for Stiff Multifluid Dust and Gas Hydrodynamics. Astrophys. J. Suppl. Ser., 271(1), 7.
Abstract: We present MDIRK: a multifluid secondorder diagonally implicit RungeKutta method to study momentum transfer between gas and an arbitrary number (N) of dust species. The method integrates the equations of hydrodynamics with an implicitexplicit scheme and solves the stiff source term in the momentum equation with a diagonally implicit, asymptotically stable RungeKutta method (DIRK). In particular, DIRK admits a simple analytical solution that can be evaluated with O(N) operations, instead of standard matrix inversion, which is O(N)3 . Therefore, the analytical solution significantly reduces the computational cost of the multifluid method, making it suitable for studying the dynamics of systems with particlesize distributions. We demonstrate that the method conserves momentum to machine precision and converges to the correct equilibrium solution with constant external acceleration. To validate our numerical method we present a series of simple hydrodynamic tests, including damping of sound waves, dusty shocks, a multifluid dusty Jeans instability, and a steadystate gasdust drift calculation. The simplicity of MDIRK lays the groundwork to build fast highorder, asymptotically stable multifluid methods.

Nisse, N., Rapaport, I., & Suchan, K. (2012). Distributed computing of efficient routing schemes in generalized chordal graphs. Theor. Comput. Sci., 444, 17–27.
Abstract: Efficient algorithms for computing routing tables should take advantage of particular properties arising in large scale networks. Two of them are of special interest: low (logarithmic) diameter and high clustering coefficient. High clustering coefficient implies the existence of few large induced cycles. Considering this fact, we propose here a routing scheme that computes short routes in the class of kchordal graphs, i.e., graphs with no induced cycles of length more than k. In the class of kchordal graphs, our routing scheme achieves an additive stretch of at most k – 1, i.e., for all pairs of nodes, the length of the route never exceeds their distance plus k – 1. In order to compute the routing tables of any nnode graph with diameter D we propose a distributed algorithm which uses O(log n)bit messages and takes O(D) time. The corresponding routing scheme achieves the stretch of k – 1 on kchordal graphs. We then propose a routing scheme that achieves a better additive stretch of 1 in chordal graphs (notice that chordal graphs are 3chordal graphs). In this case, distributed computation of routing tables takes O(min{Delta D, n}) time, where Delta is the maximum degree of the graph. Our routing schemes use addresses of size log n bits and local memory of size 2(d1) log n bits per node of degree d. (c) 2012 Elsevier B.V. All rights reserved.
Keywords: Routing scheme; Stretch; Chordal graph; Distributed algorithm

Villalobos, C., NegretePincetic, M., Figueroa, N., Lorca, A., & Olivares, D. (2021). The impact of shortterm pricing on flexible generation investments in electricity markets. Energy Econ., 98, 105213.
Abstract: The massive growth in the integration of variable renewable energy sources is producing several challenges in the operation of power systems and its associated markets. In this context, flexibility has become a critical attribute to allow the system to react to changes in generation or demand levels. Thus, it is critical for market signals at both short and long term scales to include flexibility features, to align agents' incentives with systemic flexibility requirements. In this paper, different pricing schemes for shortterm markets are studied, based on various relaxations of the unit commitment problem, including convexhull approximations, with the aim of representing operational flexibility requirements in a more explicit way. Extensive simulations illustrate the performance of the proposed schemes, as compared to conventional ones, in terms of the capability of the system to properly incentivize flexibility attributes, resulting in better agents' cost recovery and more variable renewable energy utilization. The results show that shortterm pricing schemes considered improve the longterm signals for flexible investments but additional changes to market design are still required. Thus, there is a need to revisit historical practices for pricing rules by incorporating additional flexibilityrelated attributes into them. Several alternatives are discussed and policy recommendations based on these considerations are provided.
