HPC Group
HighPerformance Computing Research Group

GPUAccelerated Jacobilike Algorithm for Eigendecomposition of General Complex Matrices
Jacobilike methods, though introduced in 1846, were not popular as they were computationally expensive for sequential computing. With the advent of parallel computing, however, it has become feasible to implement such algorithms on supercomputers. The Jacobi method of calculating eigenvalues, in addition to be highly parallelizable, has been shown to be a very stable numerical which computes small eigenvalues with a better accuracy compared to other popular algorithms such as QR. In this research, we revisit Shroff’s Jacobilike algorithm for eigendecomposition of general complex matrices and present a novel parallel implementation of the algorithm on the GPU. We present performance results that show significant improvement over a serial counterpart. Our performance results show that our GPU implementation runs up to 94 times faster than a single threaded CPU for a dense matrix of size 1024.

Group Steiner Problem on the GPU
The problem of VLSI routing and wiring estimation typically assumes a onetoone correspondence between the terminals and ports. In practice, however, each terminal consists of a large collection of electrically equivalent ports, a fact that is not accounted for in layout steps such as wiring estimation. Each terminal can be represented as a group of vertices in a graph where each vertex corresponds to a port. The task is to find a minimumcost tree that contains at least one node from each group. This problem of interconnecting a net with multiport terminals is a direct generalization of the Group Steiner Problem. This problem is known to be intractable, making it impractical to be used in realworld VLSI applications. To that end, our work focuses on developing an efficient parallel algorithm for the GSP that will be suitable for inexpensive commodity accelerators such as the GPUs.

Accelerating Tridiagonal Matrix Inversion on the GPU
Inverting a matrix is a more computationally challenging process than solving a linear system. However, in fields such as structural engineering, dynamic systems, and cryptography, computing the inverse of a matrix is inevitable. In this poster, we present an accelerated procedure for computing the inverse of diagonally dominant tridiagonal matrices on the GPU. The algorithm is based on the recursive application of the ShermanMorrison formula for tridiagonal matrices. The preliminary experimental results on Nvidia Tesla K20c GPUs show that our GPU implementation of the inversion procedure outperforms the conventional CPUbased implementations with a speedup of up to 24x.

Parallel Homotopy Method for Symmetric Eigenvalue Problems
The Homotopy method can be applied to solve eigenvalueeigenvector problems for symmetric tridiagonal matrices. It is often not of any interest to compute every eigenvalue of a matrix. Because the Homotopy method possess the order preserving property, the algorithm is able to compute any specific eigenvalue without the need for computing any other eigenvalues. In addition to this advantage, the Homotopy method is also a highly parallel algorithm. The Homotopy method is highly efficient for eigenvalue computation, especially for graded matrices. Our implementation exploits the inherent parallelism of the Homotopy method using CUDA to achieve significant speedups in computation time.

Image Classification Using Hypergraphs
A standard method of classifying images is pairwise comparison. We compare images onetoone and encode pairwise similarities in a graph. There has been an extensive study on optimal partitioning of graphs. Unfortunately, ordinary graphs prove inadequate for some realworld datasets. We could gain better insight by comparing multiple images at once rather than comparing only two at a time. To this end, hypergraphs offer a promising alternative, encoding multiway similarities. Recent works make use of hypergraphs to achieve better classification. Despite its advantage over ordinary graphs, hypergraph partitioning is computationally demanding. To that end, this research focuses on developing an efficient hypergraph partitioning algorithm that will be suitable for accelerators such as GPUs.

MultiGPU Implementation of Bisection Algorithm for Symmetric Tridiagonal Eigenvalue Problem
Bisection Method is a numerically stable algorithm commonly used to find the eigenvalues of symmetric tridiagonal matrices. Its simplicity and ability to compute eigenvalues at high precision makes it one of the most popular methods used in matrix computations. The method is also suitable for many types of muitiprocessors because of its highly parallelizable nature. In this research we develop a highly scalable algorithm to compute eigenvalues of symmetric tridiagonal matrices based on the conventional Bisection Method on a multiGPU system.

Image Matching Using Hypergraphs
A hypergraph is a generalization of an ordinary graph in which edges can connect any number of vertices. Hypergraphs can be used to effectively represent sophisticated relations among the datasets. The process of determining correspondence between the nodes in two hypergraphs, called hypergraph matching, helps solve problems such as image matching and object recognition. However, it is computationally demanding, making it impractical in realworld applications. Our main contribution in this research is to accelerate the process on the GPUs, so it can be used in today’s timecritical applications. Based on a probabilistic approach, our approach takes edgeweight matrices and produces both soft matching and hard matching. Our preliminary result shows that a high accuracy can be achieved when try to matching two datasets using hypergraphs when running on the GPU. We are also investigating an alternative way of computing the probability matrix with the minimal memory requirements and a way of incorporating tensors to accommodate highdegree hypergraphs.

An Accelerated Procedure for Discrete Shuffled Frog Leaping Algorithm
The Knapsack Problem is a popular combinatorial optimization problem which assumes a case where there is a knapsack which can hold a maximum weight W. There is a set of items N from which each item has its own weight and value. The task is to pack the knapsack with the maximum possible value while staying under the weight limit of W. The 0/1 Knapsack Problem is a unique case of the classic Knapsack Problem in which each item from the set is either included or excluded in its entirety. A brute force approach can be used which would generate all the subsets of N and compare them to get the most optimal solution. But as the input size increases, the number of subsets also increases exponentially making this approach computationally impractical. In this research we investigate a GPUbased approach to the Discrete Shuffled Frog Leaping Algorithm as a computationally more efficient procedure to solve the problem.
Sponsors
Past Members
 Bemnet Demere, ’19 (Software Developer at TicketNetwork)
 Ebenezer Hormenou, ’18 (Business Analyst at Casey Quirk and Associates)
 Kalyan Parajuli, ’18 (Business Intelligence Developer at TicketNetwork)
 Rahul Chandrashekhar, ’17 (Business Intelligence Engineer at TicketNetwork)
 Basileal Imana, ’17 (Ph.D. candidate at University of Southern California)
 Kevin Liu, ’17 (Software Engineer at Altair)
 Venkata Suhas Maringanti, ’17 (Ph.D. candidate at University of Massachusetts, Dartmouth)
 Peter Reheis, ’16 (Software Developer at Leidos)
 Barok Imana, ’16 (Ph.D. candidate at University of Maryland)
 Pranav Bhandari, ’17 (Ph.D. candidate at Emory University)
 Sybil Bingqing Li, ’17 (Software Engineer at Facebook)
 Reid Delaney, ’16 (Systems Engineer at Cisco)
 Sam Johnson, ’17 (Investment Banking Analyst at Canaccord Genuity)
 Philip Cho, ’15 (Applied Scientist at Amazon Web Services)
 Nicky Thai, ’15 (Software Engineer at Microsoft)
 Alexandre Zhang, ’14 (Software Engineer at Actio Software Corporation)
 Vlad Burca, ’14 (Software Engineer at Meetup)
 Liam Doran, ’14 (Software Engineer at Minibar Delivery)
 Jin Liu, ’14 (Software Developer at ZT Systems)
 Seongju Park (Software Engineer at Cruise Automation)
 Emy Lin (Technical Business Analyst at Intel Corporation)
 Jiajia Zhao (Software Engineer at MemSQL)
 Peter Won (Software Engineer at Samsung Electronics America)
 Todor Mitev, ’12 (Software Engineer at Google)
 Gong Chen, ’12 (Director of Quantitative Research at Bradley, Foster & Sargent)
 Ben Hartung, ’12 (Software Engineer at Amazon)
 Dimitar Gochev, ’11 (Ph.D. candidate at University of Massachusetts at Amhert)
 Kalin Gochev ’09 (Senior Software Engineer at Uber)
 Adam Williams ’04 (Software Engineering Manager at Apple)
 Meghan Emilio ’04 (Math teacher at The Potomac School)
 Bryan Dion, ’02 (Web Developer and IT Specialist at Professional Photographers of America)