W&M Featured Events
This calendar presented by
William & Mary
[PAST EVENT] Lingfei Wu - Dissertation Defense - Computer Science
January 22, 2015
9am - 11am
Abstract:
As "big data" has increasing influence on our daily life and research activities, it poses significant challenges on various research areas. Some applications often demand a fast solution of large, sparse eigenvalue and singular value problems; In other applications, extracting knowledge from large-scale data requires many techniques such as statistical calculations, data mining, and high performance computing. In this dissertation proposal, we develop efficient and robust iterative methods for the computation of eigenvalue and singular values. We also develop practical numerical and data mining techniques to estimate the trace of a function of a large, sparse matrix and to detect in real-time blob-filaments in fusion plasma on extremely large parallel computers.
In the first part of the research, we develop a high quality SVD software on top of the state-of-the-art eigensolver PRIMME that can take advantage of preconditioning, and of PRIMME's nearly-optimal methods and full functionality to compute both largest and smallest singular triplets. Accuracy and efficiency is achieved through a hybrid, two-stage meta-method, primme_svds. It combines the advantages of the two stages, faster convergence and accuracy, respectively. The method can be used with or without preconditioning, on large problems, and is superior to other state-of-the-art SVD methods in both efficiency and robustness.
In the second part of the work, we present a novel method to estimate the trace of the matrix inverse by exploiting the pattern correlation between the diagonals of the inverse of a large, sparse matrix and some approximation. We consider a number of inexpensively computed approximations and then leverage various sampling and fitting techniques for trace estimation. Based on a dynamic evaluation of variances and the relative trace error, the proposed method can either reduce the variance of Monte Carlo or directly estimate the trace with better accuracy than Monte Carlo given a small number of samples. We plan to analyze these methods theoretically and provide bounds on the accuracy of the interpolation.
The goal of the third part of this work is to provide insights and develop practical algorithms to accomplish efficient and accurate computation of interior eigenpairs using the harmonic and refined projection techniques in Davidson type methods. We firstly compare different implementations of the refined projection, and analyze their numerical accuracy and computational costs. Then, we propose a new hybrid method to effectively find interior eigenpairs without compromising accuracy. We plan to provide a convergence analysis of the proposed method. We also plan to study similar properties for the harmonic projection.
In the fourth part of this research, we propose a real-time outlier detection algorithm to efficiently find blob-filaments in fusion experiments and numerical simulations. We have implemented this algorithm with hybrid MPI/OpenMP and show that we can complete blob detection in two or three milliseconds using a HPC cluster and achieve linear time speedup.
Bio:
Lingfei Wu is a 5th year Ph.D. candidate in the computer science department at College of William and Mary, advised by Dr. Andreas Stathopoulos. His research interests are in the areas of numerical linear algebra, scientific computing, high performance computing, and big data mining algorithm. In summer 2014, Lingfei was a computing sciences summer student at Lawrence Berkeley National Laboratory. Before joining William and Mary, Lingfei received his M.S. from University of Science and Technology of China (Hefei, 2010), following his B.E. from Auhui University (Hefei, 2007).
As "big data" has increasing influence on our daily life and research activities, it poses significant challenges on various research areas. Some applications often demand a fast solution of large, sparse eigenvalue and singular value problems; In other applications, extracting knowledge from large-scale data requires many techniques such as statistical calculations, data mining, and high performance computing. In this dissertation proposal, we develop efficient and robust iterative methods for the computation of eigenvalue and singular values. We also develop practical numerical and data mining techniques to estimate the trace of a function of a large, sparse matrix and to detect in real-time blob-filaments in fusion plasma on extremely large parallel computers.
In the first part of the research, we develop a high quality SVD software on top of the state-of-the-art eigensolver PRIMME that can take advantage of preconditioning, and of PRIMME's nearly-optimal methods and full functionality to compute both largest and smallest singular triplets. Accuracy and efficiency is achieved through a hybrid, two-stage meta-method, primme_svds. It combines the advantages of the two stages, faster convergence and accuracy, respectively. The method can be used with or without preconditioning, on large problems, and is superior to other state-of-the-art SVD methods in both efficiency and robustness.
In the second part of the work, we present a novel method to estimate the trace of the matrix inverse by exploiting the pattern correlation between the diagonals of the inverse of a large, sparse matrix and some approximation. We consider a number of inexpensively computed approximations and then leverage various sampling and fitting techniques for trace estimation. Based on a dynamic evaluation of variances and the relative trace error, the proposed method can either reduce the variance of Monte Carlo or directly estimate the trace with better accuracy than Monte Carlo given a small number of samples. We plan to analyze these methods theoretically and provide bounds on the accuracy of the interpolation.
The goal of the third part of this work is to provide insights and develop practical algorithms to accomplish efficient and accurate computation of interior eigenpairs using the harmonic and refined projection techniques in Davidson type methods. We firstly compare different implementations of the refined projection, and analyze their numerical accuracy and computational costs. Then, we propose a new hybrid method to effectively find interior eigenpairs without compromising accuracy. We plan to provide a convergence analysis of the proposed method. We also plan to study similar properties for the harmonic projection.
In the fourth part of this research, we propose a real-time outlier detection algorithm to efficiently find blob-filaments in fusion experiments and numerical simulations. We have implemented this algorithm with hybrid MPI/OpenMP and show that we can complete blob detection in two or three milliseconds using a HPC cluster and achieve linear time speedup.
Bio:
Lingfei Wu is a 5th year Ph.D. candidate in the computer science department at College of William and Mary, advised by Dr. Andreas Stathopoulos. His research interests are in the areas of numerical linear algebra, scientific computing, high performance computing, and big data mining algorithm. In summer 2014, Lingfei was a computing sciences summer student at Lawrence Berkeley National Laboratory. Before joining William and Mary, Lingfei received his M.S. from University of Science and Technology of China (Hefei, 2010), following his B.E. from Auhui University (Hefei, 2007).
Contact
vlthompsondopp@wm.edu