More Like this

1. Doubly-adaptive artificial compression methods for incompressible flow

   https://doi.org/10.1515/jnma-2019-0015  

   Layton, William; McLaughlin, Michael (September 2020, Journal of Numerical Mathematics)

   null (Ed.)

   Abstract This report presents adaptive artificial compression methods in which the time-step and artificial compression parameter ε are independently adapted. The resulting algorithms are supported by analysis and numerical tests. The first and second-order methods are embedded. As a result, the computational, cognitive, and space complexities of the adaptive ε , k algorithms are negligibly greater than that of the simplest, first-order, constant ε , constant k artificial compression method. 

   more » « less
2. Adaptive partitioned methods for the time-accurate approximation of the evolutionary Stokes–Darcy system

   https://doi.org/doi.org/10.1016/j.cma.2020.112923  

   LI, Y.; HOU, Y. LAYTON; ZHAO, H. (June 2020, Computer methods in applied mechanics and engineering)

   This paper develops, analyzes and tests a time-accurate partitioned method for the Stokes-Darcy equations. The method combines a time filter and Backward Euler scheme, is second order accurate and provide, at no extra complexity, an estimated the temporal error. This approach post-processes the solutions of Backward Euler scheme by adding three lines to original codes to increase the time accuracy from first order to second order. We prove long time stability and error estimates of Backward Euler plus time filter with constant time stepsize. Moreover, we extend the approach to variable time stepsize and construct adaptive algorithms. Numerical tests show convergence of our method and support the theoretical analysis. 

   more » « less
3. Parallel Nearest Neighbors in Low Dimensions with Batch Updates

   Blelloch, Guy E.; Dobson, Magdalen (January 2022, 2022 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX))

   We present a set of parallel algorithms for computing exact k-nearest neighbors in low dimensions. Many k-nearest neighbor algorithms use either a kd-tree or the Morton ordering of the point set; our algorithms combine these approaches using a data structure we call the zd-tree. We show that this combination is both theoretically efficient under common assumptions, and fast in practice. For point sets of size n with bounded expansion constant and bounded ratio, the zd-tree can be built in O(n) work with O(n^ε) span for constant ε < 1, and searching for the k-nearest neighbors of a point takes expected O(k log k) time. We benchmark our k-nearest neighbor algorithms against existing parallel k-nearest neighbor algorithms, showing that our implementations are generally faster than the state of the art as well as achieving 75x speedup on 144 hyperthreads. Furthermore, the zd-tree supports parallel batch-dynamic insertions and deletions; to our knowledge, it is the first k-nearest neighbor data structure to support such updates. On point sets with bounded expansion constant and bounded ratio, a batch-dynamic update of size k requires O(k log n/k) work with O(k^ε + polylog(n)) span. 

   more » « less
4. Improved Algorithms for Maximum Coverage in Dynamic and Random Order Streams

   https://doi.org/10.4230/LIPICS.ESA.2024.40  

   Chakrabarti, Amit; McGregor, Andrew; Wirth, Anthony (January 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Chan, Timothy; Fischer, Johannes; Iacono, John; Herman, Grzegorz (Ed.)

   The maximum coverage problem is to select k sets, from a collection of m sets, such that the cardinality of their union, in a universe of size n, is maximized. We consider (1-1/e-ε)-approximation algorithms for this NP-hard problem in three standard data stream models. 1) Dynamic Model. The stream consists of a sequence of sets being inserted and deleted. Our multi-pass algorithm uses ε^{-2} k ⋅ polylog(n,m) space. The best previous result (Assadi and Khanna, SODA 2018) used (n +ε^{-4} k) polylog(n,m) space. While both algorithms use O(ε^{-1} log m) passes, our analysis shows that, when ε ≤ 1/log log m, it is possible to reduce the number of passes by a 1/log log m factor without incurring additional space. 2) Random Order Model. In this model, there are no deletions, and the sets forming the instance are uniformly randomly permuted to form the input stream. We show that a single pass and k polylog(n,m) space suffices for arbitrary small constant ε. The best previous result, by Warneke et al. (ESA 2023), used k² polylog(n,m) space. 3) Insert-Only Model. Lastly, our results, along with numerous previous results, use a sub-sampling technique introduced by McGregor and Vu (ICDT 2017) to sparsify the input instance. We explain how this technique and others used in the paper can be implemented such that the amortized update time of our algorithm is polylogarithmic. This also implies an improvement of the state-of-the-art insert only algorithms in terms of the update time: polylog(m,n) update time suffices, whereas the best previous result by Jaud et al. (SEA 2023) required update time that was linear in k. 

   more » « less
5. Adaptive and Optimal Second-order Optimistic Methods for Minimax Optimization

   Jiang, R; Kavis, A; Jin, Q; Sanghavi, S; Mokhtari, A (November 2024, https://doi.org/10.48550/arXiv.2406.02016)

   We propose adaptive, line search-free second-order methods with optimal rate of convergence for solving convex-concave min-max problems. By means of an adaptive step size, our algorithms feature a simple update rule that requires solving only one linear system per iteration, eliminating the need for line search or backtracking mechanisms. Specifically, we base our algorithms on the optimistic method and appropriately combine it with second-order information. Moreover, distinct from common adaptive schemes, we define the step size recursively as a function of the gradient norm and the prediction error in the optimistic update. We first analyze a variant where the step size requires knowledge of the Lipschitz constant of the Hessian. Under the additional assumption of Lipschitz continuous gradients, we further design a parameter-free version by tracking the Hessian Lipschitz constant locally and ensuring the iterates remain bounded. We also evaluate the practical performance of our algorithm by comparing it to existing second-order algorithms for minimax optimization. 

   more » « less