26 papers · ranked by Valyu relevance
Ashley I. Teufel, Claus O. Wilke
We present an accelerated algorithm to forward-simulate origin--fixation models. Our algorithm requires on average only about two fitness evaluations per fixed mutation, whereas traditional algorithms require, per one fixed mutation, a number of fitness evaluations on the order of the effective population size Ne. Our…
Ji Liu, Stephen J. Wright
The randomized Kaczmarz (RK) algorithm is a simple but powerful approach for solving consistent linear systems Ax = b. This paper proposes an accelerated randomized Kaczmarz (ARK) algorithm with better convergence than the standard RK algorithm on ill conditioned problems. The per-iteration cost of RK and ARK are…
Peter L. Bartlett, Chris Junchi Li, Jingfeng Wu, Bin Yu
In the field of optimization, developing accelerated methods for solving minimax and fixed-point problems remains a fundamental challenge. This paper presents a novel family of dual accelerated algorithms that achieve optimal convergence rates for both minimax and fixed-point problems. By exploring new anchoring…
Gang Mei, Nengxiong Xu, Liangliang Xu
This paper presents an efficient parallel Adaptive Inverse Distance Weighting (AIDW) interpolation algorithm on modern Graphics Processing Unit (GPU). The presented algorithm is an improvement of our previous GPU-accelerated AIDW algorithm by adopting fast k-nearest neighbors (kNN) search. In AIDW, it needs to find…
Xuan Zuo, Hui-Yan Li, Shan Gao, Pu Zhang + 2 more
Adaptive gradient algorithms have been successfully used in deep learning. Previous work reveals that adaptive gradient algorithms mainly borrow the moving average idea of heavy ball acceleration to estimate the first- and second-order moments of the gradient for accelerating convergence. However, Nesterov acceleration…
Michael Muehlebach, Michael I. Jordan
We exploit analogies between first-order algorithms for constrained optimization and non-smooth dynamical systems to design a new class of accelerated first-order algorithms for constrained optimization. Unlike Frank-Wolfe or projected gradients, these algorithms avoid optimization over the entire feasible set at each…
Felix Kallenborn, Fawaz Dabbaghie, Martin Steinegger, Bertil Schmidt
The continually increasing volume of sequence data results in a growing demand for fast implementations of core algorithms. Computation of pairwise alignments based on dynamic programming is an important part in many bioinformatics pipelines and a major contributor to overall runtime due to the associated quadratic…
Palma London, Shai Vardi, Adam Wierman, Hanling Yi
This paper presents an acceleration framework for packing linear programming problems where the amount of data available is limited, i.e., where the number of constraints m is small compared to the variable dimension n. The framework can be used as a black box to speed up linear programming solvers dramatically, by two…
Yu-Wen Chen, Antonio Orvieto, Aurélien Lucchi
Derivative-free optimization (DFO) has recently gained a lot of momentum in machine learning, spawning interest in the community to design faster methods for problems where gradients are not accessible. While some attention has been given to the concept of acceleration in the DFO literature, existing stochastic…
Yaniv Swiel, Jean-Tristan Brandenburg, Mahtaab Hayat, Wenlong Carl Chen + 2 more
Genome-wide association studies (GWASs) analyse genetic variation over the genomes of many individuals in an attempt to identify single nucleotide polymorphisms (SNPs) associated with complex phenotypes. To capture a large amount of genetic variation and increase the chance of detecting associated SNPs, modern GWASs…
Soheil Shahrouz, Saber Salehkaleybar, Matin Hashemi
—Given a social network modeled as a weighted graph G, the influence maximization problem seeks k vertices to become initially influenced, to maximize the expected number of influenced nodes under a particular diffusion model. The influence maximization problem has been proven to be NP-hard, and most proposed solutions…
Xin Wang, Bin Zhang, Xu Cao, Fei Liu + 2 more
Fluorescence molecular tomography (FMT) with early-photons can improve the spatial resolution and fidelity of the reconstructed results. However, its computing scale is always large which limits its applications. In this paper, we introduced an acceleration strategy for the early-photon FMT with graphics processing…
Yangyang Xu
Motivated by big data applications, first-order methods have been extremely popular in recent years. However, naive gradient methods generally converge slowly. Hence, much efforts have been made to accelerate various first-order methods. This paper proposes two accelerated methods towards solving structured linearly…
Tim Anderson, Travis J. Wheeler
Sequence alignment lies at the heart of genome sequence annotation. While the BLAST suite of alignment tools has long held an important role in alignment-based sequence database search, greater sensitivity is achieved through the use of profile hidden Markov models (pHMMs). The Forward algorithm that provides much of…
Pranay Reddy Kommera, Vinay Ramakrishnaiah, Christine Sweeney, Jeffrey Donatelli + 1 more
'Jeffrey Donatelli' 'Petrus H. Zwart'] The paper presents efforts to accelerate the multitiered iterative phasing (MTIP) algorithm on contemporary graphics processing units (GPUs). Application portability is demonstrated by accelerating the MTIP algorithm on NVIDIA and AMD GPUs using a single codebase.
David S. Lawrie
Forward Wright-Fisher simulations are powerful in their ability to model complex demography and selection scenarios, but suffer from slow execution on the CPU, thus limiting their usefulness. The single-locus Wright-Fisher forward algorithm is, however, exceedingly parallelizable, with many steps which are so-called…
Paulo E. P. Burke, Luciano da F. Costa
Simulation of reaction systems has been employed along decades for a better understanding of such systems. However, the ever-growing gathering of biological data implied in larger and more complex models that are computationally challenging for current discrete-stochastic simulation methods. In this work, we propose a…
Zixuan Li, Mingxing Duan, Huizhang Luo, Wangdong Yang + 2 more
Using GPU Tensor Cores Authors: ['Zixuan Li' 'Mingxing Duan' 'Huizhang Luo' 'Wangdong Yang' 'Kenli Li' 'Keqin Li'] Abstract—Sparse tensors are prevalent in real-world applications, often characterized by their large-scale, high-order, and highdimensional nature. Directly handling raw tensors is impractical due to the…
Authors not listed
Stochastic Simulation Algorithms (SSA) are a cornerstone in simulating Free Radical Polymerization (FRP) due to their accuracy and reliability. However, computational inefficiency remains a challenge for large-scale and complex polymerization systems. This work introduces a novel stochastic simulation algorithm…
Authors not listed
Modeling multimetallic systems efficiently enables faster prediction of desirable chemical properties and design of new materials. This work describes an initial implementation for performing multireference wave function method localized active space self-consistent field (LASSCF) calculations through the use of…
Steen Lysgaard, Paul C. Jennings, Jens Strabo Hummelshøj, Thomas Bligaard + 1 more
A machine learning (ML) model is trained on-the-fly as a computationally inexpensive energy predictor before analyzing how to augment convergence in Genetic Algorithm (GA)-based approaches by using the ML model as a surrogate. This leads to a machine learning accelerated genetic algorithm (MLaGA) combining robust…
Shubhendra Pal Singhal, M. Srıdevı
—Optimization of searching the best possible action depending on various states like state of environment, system goal etc. has been a major area of study in computer systems. In any search algorithm, searching best possible solution from the pool of every possibility known can lead to the construction of the whole…
Jonas Latt, Christophe Coreixas, Joël Beny, Fang-Bao Tian
We present a novel, hardware-agnostic implementation strategy for lattice Boltzmann (LB) simulations, which yields massive performance on homogeneous and heterogeneous many-core platforms. Based solely on C++17 Parallel Algorithms, our approach does not rely on any language extensions, external libraries…
Yann Garniron, Thomas Applencourt, Kevin Gasperich, Anouar Benali + 15 more
Quantum Package is an open-source programming environment for quantum chemistry specially designed for wave function methods. Its main goal is the development of determinant-driven selected configuration interaction (sCI) methods and multi-reference second-order perturbation theory (PT2). The determinant-driven…
Madushanka Manathunga, Hasan Metin Aktulga, Andreas W. Goetz, Kenneth M. Merz + 1 more
We have ported and optimized the GPU accelerated QUICK and AMBER based ab initio QM/MM implementation on AMD GPUs. This encompasses the entire Fock matrix build and force calculation in QUICK including one-electron integrals, two-electron repulsion integrals, exchange-correlation quadrature, and linear algebra…
Pier Paolo Poier, Louis Lagardère, Jean-Philip Piquemal
We propose a new strategy to solve the Tkatchenko-Scheffler Many-Body Dispersion (MBD) model’s equations. Our approach overcomes the original O(N**3) computational complexity that limits its applicability to large molecular systems within thecontext of O(N) Density Functional Theory (DFT). First, in order to generate…