The FEAST algorithm proposed in 2009 by Eric Polizzi of the University of Massachusetts Amherst Electrical and Computer Engineering (ECE) Department – an algorithm that represents a radical departure from "textbook approaches" to solving the legendary eigenvalue problem – received a major endorsement in early February when it was integrated into the Intel® Math Kernel Library, one of the world’s leading and most used mathematical libraries. Polizzi’s FEAST algorithm is now featured as the Intel library’s main eigenvalue solver, and it can be found under the name "MKL Extended EigenSolver."
“The eigenvalue problem is a central topic in science and engineering arising from a wide range of applications and posing major numerical challenges,” Polizzi explained. “For decades, it has been the focus of numerous research activities for developing various efficient numerical algorithms and library packages.”
The first publication of Polizzi’s FEAST algorithm was selected as an editors’ suggestion by the American Physical Society journal, Physical Review B [Phys. Rev. B. Vol. 79, 115112 (2009)]. In addition to the algorithm, FEAST is also the name of a free, state-of-the-art, numerical library package (http://www.ecs.umass.edu/~polizzi/feast/), which Polizzi developed and released in September of 2009 and upgraded with a second-generation version in March of 2012.
"FEAST is a genuinely new, innovative, simple, and highly parallel eigenvalue algorithm,” said Intel Senior Principal Engineer Dr. Ping Tak Peter Tang.
Intel Fellow Dr. David Kuck added that “Polizzi has made an outstanding contribution with the FEAST algorithm and solver, the latter of which has now been integrated into the Intel® Math Kernel Library.”
The Intel®Math Kernel Library is a highly optimized, extensively threaded, and thread-safe library of mathematical functions for engineering, scientific, and financial applications that require maximum performance (http://software.intel.com/en-us/intel-mkl). The library includes a wealth of routines to accelerate application performance and reduce development time. Today’s processors have increasing core counts, wider vector units, and more varied architectures. The easiest way to take advantage of all of that processing power is to use a carefully optimized computing math library designed to harness that potential.
The eigenvalue problem is of considerable theoretical interest and wide-ranging application. For example, this problem is crucial in solving systems of differential equations, analyzing population-growth models, and calculating powers of matrices. Other areas such as physics, chemistry, sociology, biology, economics, and statistics have focused considerable attention on "eigenvalues" and "eigenvectors," their applications, and their computations.
The prefix eigen is the German word for innate, distinct, or self. In linear algebra, eigenvalues, eigenvectors, and eigenspaces are properties of a matrix. Linear algebra studies linear transformations, which are represented by matrices acting on vectors. In general, a matrix acts on a vector by changing both its magnitude and its direction. However, a matrix may act on certain vectors by changing only their magnitude, and leaving their direction unchanged (or possibly reversing it). These vectors are the eigenvectors of the matrix.
Polizzi solves the eigenvalue problem by taking his inspiration from the density-matrix representation and contour-integration technique in quantum mechanics. “The FEAST algorithm combines simplicity and efficiency and offers many important and unique capabilities for achieving high performance, robustness, accuracy, and linear scalability on parallel architectures,” said Polizzi.
The FEAST numerical library solver package, based on Polizzi’s innovative, fast, and stable numerical FEAST algorithm, is a free high-performance numerical library for solving the standard or generalized eigenvalue problem and obtaining all the eigenvalues and eigenvectors within a given search interval.
Since 2009, both the algorithm and library package have gained significant international visibility in the science and engineering communities. FEAST has been downloaded more than 1,400 times from 55 countries worldwide, and it is regularly ranked at the very top for search results on "eigenvalue solver" on Google, Bing, and Yahoo.
Now FEAST is set to go viral. Its integration into the Intel®Math Kernel Library will give Polizzi’s eigenvalue solver an enormous international pool of users.
“ECE Professor Eric Polizzi has made a significant research achievement with his FEAST algorithm recently being included in Intel’s Math Kernel Library,” said Dean Christopher Hollot of the UMass College of Engineering. “This is a very big deal.”
Polizzi and his research group are currently working to finalize a third-generation FEAST version for solving both the non-Hermitian eigenvalue problem and the non-linear eigenvector problem, which arise in electronic structure calculations.
“I’d like to acknowledge my Intel collaborators,” said Polizzi, “including Dr. Sergey Kuznetsov, for his invaluable feedback and efforts for testing various versions of the FEAST software rigorously, and Dr. Ping Tak Peter Tang, who has recently provided a robust mathematical framework for the FEAST algorithm. I’d also like to credit Dr. Bob Kuhn and Dr. David Kuck for their constant support.” (February 2013)