More Like this

1. Shortest Paths in the Plane with Obstacle Violations

   https://doi.org/s00453-020-00673-y  

   Hershberger, J.; Kumar, N.; Suri, S. (January 2020, Algorithmica)

   We study the problem of finding shortest paths in the plane among h convex obstacles, where the path is allowed to pass through (violate) up to k obstacles, for 𝑘≤ℎ. Equivalently, the problem is to find shortest paths that become obstacle-free if k obstacles are removed from the input. Given a fixed source point s, we show how to construct a map, called a shortest k-path map, so that all destinations in the same region of the map have the same combinatorial shortest path passing through at most k obstacles. We prove a tight bound of 𝛩(𝑘𝑛) on the size of this map, and show that it can be computed in 𝑂(𝑘2𝑛log𝑛) time, where n is the total number of obstacle vertices. 

   more » « less
2. Efficient One-Shot Technique for Adjoint-Based Unsteady Optimization

   https://doi.org/10.2514/1.J060142  

   Djeddi, Reza; Ekici, Kivanc (June 2021, AIAA Journal)

   null (Ed.)

   A computationally efficient one-shot approach with a low memory footprint is presented for unsteady optimization. The proposed technique is based on a novel and unique approach that combines local-in-time and fixed-point iteration methods to advance the unconverged primal and adjoint solutions forward and backward in time to evaluate the sensitivity of the globally time-integrated objective function. This is in some ways similar to the piggyback iterations in which primal and adjoint solutions are evaluated at a frozen design. During each cycle, the primal, adjoint, and design update problems are solved to advance the optimization problem. This new coupled approach is shown to provide significant savings in the memory footprint while reducing the computational cost of primal and adjoint evaluations per design cycle. The method is first applied to an inverse design problem for the unsteady lid-driven cavity. Following this, vortex suppression and mean drag reduction for a circular cylinder in crossflow is considered. Both of these objectives are achieved by optimizing the rotational speeds for steady or periodically oscillating excitations. For all cases presented in this work, the proposed technique is shown to provide significant reductions in memory as well as computational time. It is also shown that the unsteady optimization problem converges to the same optimal solution obtained using a conventional approach. 

   more » « less
3. Computationally- and Memory-Efficient One-Shot Approach for Unsteady Adjoint-Based Design Optimization

   https://doi.org/10.2514/6.2020-3129  

   Djeddi, Reza; Ekici, Kivanc (June 2020, 2020 AIAA AVIATION Forum)

   A computationally efficient "one-shot" approach with a low memory footprint is presented for unsteady design optimization. The proposed technique is based on a novel and unique approach that combines "local-in-time" and fixed-point iteration methods to advance the unconverged primal and adjoint solutions forward and backward in time to evaluate the sensitivity of the globally time-integrated objective function. This is in some ways similar to the "piggyback" iterations where primal and adjoint solutions are evaluated at a frozen design. During each cycle, the primal, adjoint, and design update problems are solved to advance the optimization problem. This new coupled approach is shown to provide significant savings in the memory footprint while reducing the computational cost of primal and adjoint evaluations per design cycle. The method is first applied to an inverse design problem for the unsteady lid-driven cavity. Following this, vortex suppression and mean drag reduction for a circular cylinder in cross-flow is considered. Both of these objectives are achieved by optimizing the rotational speeds for steady or periodically oscillating excitations. For all cases presented in this work, the proposed technique is shown to provide significant reductions in memory as well as computational time. It is also shown that the unsteady design optimization problem converges to the same optimal solution obtained using a conventional approach. 

   more » « less
4. Discrete symmetry breaking defines the Mott quartic fixed point

   https://doi.org/10.1038/s41567-022-01529-8  

   Huang, Edwin W.; Nave, Gabriele La; Phillips, Philip W. (July 2022, Nature physics)

   Because Fermi liquids are inherently non-interacting states of matter, all electronic levels below the chemical potential are doubly occupied. Consequently, the simplest way of breaking the Fermi-liquid theory is to engineer a model in which some of those states are singly occupied, keeping time-reversal invariance intact. We show that breaking an overlooked1 local-in-momentum space ℤ2 symmetry of a Fermi liquid does precisely this. As a result, although the Mott transition from a Fermi liquid is correctly believed to arise without breaking any continuous symmetry, a discrete symmetry is broken. This symmetry breaking serves as an organizing principle for Mott physics whether it arises from the tractable Hatsugai–Kohmoto model or the intractable Hubbard model. Through a renormalization-group analysis, we establish that both are controlled by the same fixed point. An experimental manifestation of this fixed point is the onset of particle–hole asymmetry, a widely observed2,3,4,5,6,7,8,9,10 phenomenon in strongly correlated systems. Theoretically, the singly occupied region of the spectrum gives rise to a surface of zeros of the single-particle Green function, denoted as the Luttinger surface. Using K-homology, we show that the Bott topological invariant guarantees the stability of this surface to local perturbations. Our proof demonstrates that the strongly coupled fixed point only corresponds to those Luttinger surfaces with co-dimension p + 1 with odd p. We conclude that both Hubbard and Hatsugai–Kohmoto models lie in the same high-temperature universality class and are controlled by a quartic fixed point with broken ℤ2 symmetry. 

   more » « less
5. A Converse to Banach's Fixed Point Theorem and its CLS Completeness

   Daskalakis, Constantinos; Tzamos, Christos; Zampetakis, Manolis (January 2018, 50th Annual ACM Symposium on the Theory of Computing)

   Banach's fixed point theorem for contraction maps has been widely used to analyze the convergence of iterative methods in non-convex problems. It is a common experience, however, that iterative maps fail to be globally contracting under the natural metric in their domain, making the applicability of Banach's theorem limited. We explore how generally we can apply Banach's fixed point theorem to establish the convergence of iterative methods when pairing it with carefully designed metrics. Our first result is a strong converse of Banach's theorem, showing that it is a universal analysis tool for establishing global convergence of iterative methods to unique fixed points, and for bounding their convergence rate. In other words, we show that, whenever an iterative map globally converges to a unique fixed point, there exists a metric under which the iterative map is contracting and which can be used to bound the number of iterations until convergence. We illustrate our approach in the widely used power method, providing a new way of bounding its convergence rate through contraction arguments. We next consider the computational complexity of Banach's fixed point theorem. Making the proof of our converse theorem constructive, we show that computing a fixed point whose existence is guaranteed by Banach's fixed point theorem is CLS-complete. We thus provide the first natural complete problem for the class CLS, which was defined in [Daskalakis, Papadimitriou 2011] to capture the complexity of problems such as P-matrix LCP, computing KKT-points, and finding mixed Nash equilibria in congestion and network coordination games. 

   more » « less