More Like this

1. Algorithm 1035: A Gradient-based Implementation of the Polyhedral Active Set Algorithm

   https://doi.org/10.1145/3583559  

   Hager, William W.; Zhang, Hongchao (June 2023, ACM Transactions on Mathematical Software)

   The Polyhedral Active Set Algorithm (PASA) is designed to optimize a general nonlinear function over a polyhedron. Phase one of the algorithm is a nonmonotone gradient projection algorithm, while phase two is an active set algorithm that explores faces of the constraint polyhedron. A gradient-based implementation is presented, where a projected version of the conjugate gradient algorithm is employed in phase two. Asymptotically, only phase two is performed. Comparisons are given with IPOPT using polyhedral-constrained problems from CUTEst and the Maros/Meszaros quadratic programming test set. 

   more » « less
2. Parallel Suffix Sorting for Large String Analytics

   https://doi.org/10.1007/978-3-031-30442-2_6  

   Zhihui Du; Sen Zhang; David Bader (September 2022, 14th International Conference on Parallel Processing and Applied Mathematics (PPAM))

   The suffix array is a fundamental data structure to support string analysis efficiently. It took about 26 years for the sequential suffix array construction algorithm to achieve O(n) time complexity and inplace sorting. In this paper, we develop the DLPI (D Limited Parallel Induce) algorithm, the first O( n p ) time parallel suffix array construction algorithm. The basic idea of DLPI includes two aspects: dividing the O(n) size problem into p reduced sub-problems with size O( n/p ) so we can handle them on p processors in parallel; developing an efficient parallel induce sorting method to achieve correct order for all the reduced sub-problems. The complete algorithm description is given to show the implementation method of the proposed idea. The time and space complexity analysis and proof are also given to show the correctness and efficiency of the proposed algorithm. The proposed DLPI algorithm can handle large strings with scalable performance. 

   more » « less
3. Linear convergence of the subspace constrained mean shift algorithm: from Euclidean to directional data

   https://doi.org/10.1093/imaiai/iaac005  

   Zhang, Yikun; Chen, Yen-Chi (April 2022, Information and Inference: A Journal of the IMA)

   Abstract This paper studies the linear convergence of the subspace constrained mean shift (SCMS) algorithm, a well-known algorithm for identifying a density ridge defined by a kernel density estimator. By arguing that the SCMS algorithm is a special variant of a subspace constrained gradient ascent (SCGA) algorithm with an adaptive step size, we derive the linear convergence of such SCGA algorithm. While the existing research focuses mainly on density ridges in the Euclidean space, we generalize density ridges and the SCMS algorithm to directional data. In particular, we establish the stability theorem of density ridges with directional data and prove the linear convergence of our proposed directional SCMS algorithm. 

   more » « less
4. Quantum algorithm for the simulation of non-Markovian quantum dynamics using Feynman–Vernon influence functional

   https://doi.org/10.1063/5.0258227  

   Seneviratne, Avin; Walters, Peter_L; Wang, Fei (May 2025, The Journal of Chemical Physics)

   In this work, we developed a quantum algorithm for the simulation of non-Markovian quantum dynamics based on the Feynman–Vernon’s path integral formulation. The algorithm performs the full path sum and proves to be polynomial either in time or in space, compared to the same classical algorithm, which is exponential in time. In addition, the algorithm has no classical overhead and is equally applicable regardless of whether the temporal entanglement due to non-Markovianity is low or high, making it a unified framework for simulating non-Markovian dynamics in open quantum systems. 

   more » « less
5. Parallel Minimum Cuts in O ( m log ² n ) Work and Low Depth

   https://doi.org/10.1145/3565557  

   Anderson, Daniel; Blelloch, Guy E (December 2023, ACM Transactions on Parallel Computing)

   We present a randomizedO(mlog²n) work,O(polylogn) depth parallel algorithm for minimum cut. This algorithm matches the work bounds of a recent sequential algorithm by Gawrychowski, Mozes, and Weimann [ICALP’20], and improves on the previously best parallel algorithm by Geissmann and Gianinazzi [SPAA’18], which performsO(mlog⁴n) work inO(polylogn) depth. Our algorithm makes use of three components that might be of independent interest. First, we design a parallel data structure that efficiently supports batched mixed queries and updates on trees. It generalizes and improves the work bounds of a previous data structure of Geissmann and Gianinazzi and is work efficient with respect to the best sequential algorithm. Second, we design a parallel algorithm for approximate minimum cut that improves on previous results by Karger and Motwani. We use this algorithm to give a work-efficient procedure to produce a tree packing, as in Karger’s sequential algorithm for minimum cuts. Last, we design an efficient parallel algorithm for solving the minimum 2-respecting cut problem. 

   more » « less