Ali Taghibakhshi

Clustering is a commonplace problem in many areas of data science, with applications in biology and bioinformatics, understanding chemical structure, image segmentation, building recommender systems, and many more fields. While there are many different clustering variants (based on given distance or graph structure, probability distributions, or data density), we consider here the problem of clustering nodes in a graph, motivated by the problem of aggregating discrete degrees of freedom in multigrid and domain decomposition methods for solving sparse linear systems. Specifically, we consider the challenge of forming balanced clusters in the graph of a sparse matrix for use in algebraic multigrid, although the algorithm has general applicability. Based on an extension of the Bellman-Ford algorithm, we generalize Lloyd's algorithm for partitioning subsets of Rn to balance the number of nodes in each cluster; this is accompanied by a rebalancing algorithm that reduces the overall energy in the system. The algorithm provides control over the number of clusters and leads to "well centered" partitions of the graph. Theoretical results are provided to establish linear complexity and numerical results in the context of algebraic multigrid highlight the benefits of improved clustering.

10.48550/arxiv.2303.01667

Cite

Citations (0)

Optimized Sparse Matrix Operations for Reverse Mode Automatic Differentiation

arXiv (Cornell University) (2022)

Nicolas Nytko Ali Taghibakhshi Tareq Uz Zaman Scott MacLachlan Luke N. Olson

Sparse matrix representations are ubiquitous in computational science and machine learning, leading to significant reductions in compute time, in comparison to dense representation, for problems that have local connectivity. The adoption of sparse representation in leading ML frameworks such as PyTorch is incomplete, however, with support for both automatic differentiation and GPU acceleration missing. In this work, we present an implementation of a CSR-based sparse matrix wrapper for PyTorch with CUDA acceleration for basic matrix operations, as well as automatic differentiability. We also present several applications of the resulting sparse kernels to optimization problems, demonstrating ease of implementation and performance measurements versus their dense counterparts.

Automatic differentiation

Representation

Matrix (chemical analysis)

Matrix representation

10.48550/arxiv.2212.05159

Cite

Citations (1)

Optimization-Based Algebraic Multigrid Coarsening Using Reinforcement Learning.

arXiv (Cornell University) (2021)

Ali Taghibakhshi Scott MacLachlan Luke N. Olson Matthew West

Large sparse linear systems of equations are ubiquitous in science and engineering, such as those arising from discretizations of partial differential equations. Algebraic multigrid (AMG) methods are one of the most common methods of solving such linear systems, with an extensive body of underlying mathematical theory. A system of linear equations defines a graph on the set of unknowns and each level of a multigrid solver requires the selection of an appropriate coarse graph along with restriction and interpolation operators that map to and from the coarse representation. The efficiency of the multigrid solver depends critically on this selection and many selection methods have been developed over the years. Recently, it has been demonstrated that it is possible to directly learn the AMG interpolation and restriction operators, given a coarse graph selection. In this paper, we consider the complementary problem of learning to coarsen graphs for a multigrid solver. We propose a method using a reinforcement learning (RL) agent based on graph neural networks (GNNs), which can learn to perform graph coarsening on small training graphs and then be applied to unstructured large graphs. We demonstrate that this method can produce better coarse graphs than existing algorithms, even as the graph size increases and other properties of the graph are varied. We also propose an efficient inference procedure for performing graph coarsening that results in linear time complexity in graph size.

Multigrid method

Solver

Source

Cite

Citations (0)

Generalizing Reduction-Based Algebraic Multigrid

arXiv (Cornell University) (2022)

Tareq Uz Zaman Nicolas Nytko Ali Taghibakhshi Scott MacLachlan Luke N. Olson

Algebraic Multigrid (AMG) methods are often robust and effective solvers for solving the large and sparse linear systems that arise from discretized PDEs and other problems, relying on heuristic graph algorithms to achieve their performance. Reduction-based AMG (AMGr) algorithms attempt to formalize these heuristics by providing two-level convergence bounds that depend concretely on properties of the partitioning of the given matrix into its fine- and coarse-grid degrees of freedom. MacLachlan and Saad (SISC 2007) proved that the AMGr method yields provably robust two-level convergence for symmetric and positive-definite matrices that are diagonally dominant, with a convergence factor bounded as a function of a coarsening parameter. However, when applying AMGr algorithms to matrices that are not diagonally dominant, not only do the convergence factor bounds not hold, but measured performance is notably degraded. Here, we present modifications to the classical AMGr algorithm that improve its performance on matrices that are not diagonally dominant, making use of strength of connection, sparse approximate inverse (SPAI) techniques, and interpolation truncation and rescaling, to improve robustness while maintaining control of the algorithmic costs. We present numerical results demonstrating the robustness of this approach for both classical isotropic diffusion problems and for non-diagonally dominant systems coming from anisotropic diffusion.

Diagonally dominant matrix

Multigrid method

Robustness

Condition number

10.48550/arxiv.2212.08371

Cite

Citations (0)

Optimization-Based Algebraic Multigrid Coarsening Using Reinforcement Learning

arXiv (Cornell University) (2021)

Ali Taghibakhshi Scott MacLachlan Luke N. Olson Matthew West

Large sparse linear systems of equations are ubiquitous in science and engineering, such as those arising from discretizations of partial differential equations. Algebraic multigrid (AMG) methods are one of the most common methods of solving such linear systems, with an extensive body of underlying mathematical theory. A system of linear equations defines a graph on the set of unknowns and each level of a multigrid solver requires the selection of an appropriate coarse graph along with restriction and interpolation operators that map to and from the coarse representation. The efficiency of the multigrid solver depends critically on this selection and many selection methods have been developed over the years. Recently, it has been demonstrated that it is possible to directly learn the AMG interpolation and restriction operators, given a coarse graph selection. In this paper, we consider the complementary problem of learning to coarsen graphs for a multigrid solver. We propose a method using a reinforcement learning (RL) agent based on graph neural networks (GNNs), which can learn to perform graph coarsening on small training graphs and then be applied to unstructured large graphs. We demonstrate that this method can produce better coarse graphs than existing algorithms, even as the graph size increases and other properties of the graph are varied. We also propose an efficient inference procedure for performing graph coarsening that results in linear time complexity in graph size.

Multigrid method

Solver

Source

Cite

Citations (0)

Local Navigation and Docking of an Autonomous Robot Mower Using Reinforcement Learning and Computer Vision

Ali Taghibakhshi Nathan Ogden Matthew West

We demonstrate a successful navigation and docking control system for the John Deere Tango autonomous mower, using only a single camera as the input. This vision-only system is of interest because it is inexpensive, simple for production, and requires no external sensing. This is in contrast to existing systems that rely on integrated position sensors and global positioning system (GPS) technologies. To produce our system we combined a state-of-the-art object detection architecture, You Look Only Once (YOLO), with a reinforcement learning (RL) architecture, Double Deep Q-Networks (Double DQN). The object detection network identifies features on the mower and passes its output to the RL network, providing it with a low-dimensional representation that enables rapid and robust training. Finally, the RL network learns how to navigate the machine to the desired spot in a custom simulation environment. When tested on mower hardware, the system is able to dock with centimeter-level accuracy from arbitrary initial locations and orientations.

Machine Vision

10.1109/iccae51876.2021.9426091

Cite

Citations (7)

Determination of surface properties and elastic constants of FCC metals: a comparison among different EAM potentials in thin film and bulk scale

Materials Research Express (2018)

Hossein Nejat Pishkenari Fartash Samie Yousefi Ali Taghibakhshi

Three independent elastic constants C11, C12, and C44 were calculated and compared using available potentials of eight different metals with FCC crystal structure; Gold, Silver, Copper, Nickel, Platinum, Palladium, Aluminum and Lead. In order to calculate the elastic constants, the second derivative of the energy density of each system was calculated with respect to different directions of strains. Each set of the elastic constants of the metals in bulk scale was compared with experimental results, and the average relative error was for each was calculated and compared with other available potentials. Then, using the Voigt-Reuss-Hill method, approximated values for Young and shear moduli and Poisson's ratio of the FCC metals in the bulk scale were found for each potential. Furthermore, to observe the surface effects on the metals in nanoscale, surface elastic constants of the thin films of the metals have been calculated. In the study of the thin films of materials in nanoscale, the number of surface atoms is considerable compared to all atoms of the object. This leads to an increase in the surface effects, which influence the elastic properties. By considering this fact and employing related definitions and equations, the properties of the thin films of the metals were calculated, and the surface effects for different crystallographic directions were compared. Subsequently, in some cases, comparisons among characteristics of the metals in the thin film and bulk material were made.

10.1088/2053-1591/aae49b

Cite

Citations (24)

Local Navigation and Docking of an Autonomous Robot Mower Using Reinforcement Learning and Computer Vision.

Ali Taghibakhshi Nathan Ogden Matthew West

We demonstrate a successful navigation and docking control system for the John Deere Tango autonomous mower, using only a single camera as the input. This vision-only system is of interest because it is inexpensive, simple for production, and requires no external sensing. This is in contrast to existing systems that rely on integrated position sensors and global positioning system (GPS) technologies. To produce our system we combined a state-of-the-art object detection architecture, You Look Only Once (YOLO), with a reinforcement learning (RL) architecture, Double Deep Q-Networks (Double DQN). The object detection network identifies features on the mower and passes its output to the RL network, providing it with a low-dimensional representation that enables rapid and robust training. Finally, the RL network learns how to navigate the machine to the desired spot in a custom simulation environment. When tested on mower hardware, the system is able to dock with centimeter-level accuracy from arbitrary initial locations and orientations.

Machine Vision

Source

Cite

Citations (0)

Local Navigation and Docking of an Autonomous Robot Mower using Reinforcement Learning and Computer Vision

arXiv (Cornell University) (2021)

Ali Taghibakhshi Nathan Ogden Matthew West

We demonstrate a successful navigation and docking control system for the John Deere Tango autonomous mower, using only a single camera as the input. This vision-only system is of interest because it is inexpensive, simple for production, and requires no external sensing. This is in contrast to existing systems that rely on integrated position sensors and global positioning system (GPS) technologies. To produce our system we combined a state-of-the-art object detection architecture, You Only Look Once (YOLO), with a reinforcement learning (RL) architecture, Double Deep QNetworks (Double DQN). The object detection network identifies features on the mower and passes its output to the RL network, providing it with a low-dimensional representation that enables rapid and robust training. Finally, the RL network learns how to navigate the machine to the desired spot in a custom simulation environment. When tested on mower hardware, the system is able to dock with centimeter-level accuracy from arbitrary initial locations and orientations.

Machine Vision

Source

Cite

Citations (0)

Study and Simulation of Nanoparticle Translocation Through Cell Membrane

Iranian Journal of Science and Technology Transactions of Mechanical Engineering (2019)

Hossein Nejat Pishkenari Mohammad Reza Barzegar Ali Taghibakhshi

Cell membrane

10.1007/s40997-019-00326-8

Cite

Citations (4)