A&S Graduate Studies
This calendar presented by
A&S Graduate Studies
[PAST EVENT] Lingfei Wu, Computer Science - Defense for the Ph.D.
June 20, 2016
9:30am - 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, we develop efficient and robust iterative methods and software 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 propose a hybrid two stage SVD method for efficiently and accurately computing a few extreme singular triplets, especially the ones corresponding to the smallest singular values. The first stage achieves fast convergence while the second achieves the final accuracy. Furthermore, we develop a high-performance preconditioned SVD software based on the proposed method on top of the state-of-the-art eigensolver PRIMME. The method can be used with or without preconditioning, on parallel computers, and is superior to other state-of-the-art SVD methods in both efficiency and robustness.
In the second part of this work, we provide insights and develop practical algorithms to accomplish efficient and accurate computation of interior eigenpairs using refined projection techniques in non-Krylov iterative methods. We first compare different implementations of the refined projection, and analyze their numerical accuracy and computational costs. Based on the advantages of different approaches, we propose a new hybrid method to efficiently find interior eigenpairs without compromising accuracy. An extensive set of experiments illustrate the efficiency and robustness of the proposed method.
In the third part of the work, we present a novel method to estimate the trace of matrix inverse that exploits the pattern correlation between the diagonal of the inverse of the matrix and that of some approximate inverse. We leverage various sampling and fitting techniques to fit the diagonal of the approximation to that of the inverse. Depending on the quality of the approximate inverse, our method may serve as a standalone kernel for providing a fast trace estimate with a small number of samples or as a variance reduction method for Monte Carlo in some cases. An extensive set of experiments demonstrate the potential of our method.
In the fourth part of this research, we provide first results on applying outlier detection techniques to effectively tackle the fusion blob detection problem on extremely large parallel machines. We present a real-time region outlier detection
algorithm to efficiently find blobs in fusion experiments and simulations. In addition, we propose an efficient scheme to track the movement of region outliers over time. We have implemented our algorithms with hybrid MPI/OpenMP and demonstrated we can achieve linear time speedup up to 1024 MPI processes and complete blob detection in two or three milliseconds.
Bio:
Lingfei Wu is a 6th year Ph.D. candidate in the computer science department at William & Mary, advised by Dr. Andreas Stathopoulos. His research interests are in the areas of high-performance scientific computing, large-scale machine learning, and big data analytics. In summer 2014, Lingfei was a computing sciences summer student at Lawrence Berkeley National Laboratory. In summer 2015, Lingfei was a summer research intern at IBM T.J.Watson Research Center. Before joining William & 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, we develop efficient and robust iterative methods and software 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 propose a hybrid two stage SVD method for efficiently and accurately computing a few extreme singular triplets, especially the ones corresponding to the smallest singular values. The first stage achieves fast convergence while the second achieves the final accuracy. Furthermore, we develop a high-performance preconditioned SVD software based on the proposed method on top of the state-of-the-art eigensolver PRIMME. The method can be used with or without preconditioning, on parallel computers, and is superior to other state-of-the-art SVD methods in both efficiency and robustness.
In the second part of this work, we provide insights and develop practical algorithms to accomplish efficient and accurate computation of interior eigenpairs using refined projection techniques in non-Krylov iterative methods. We first compare different implementations of the refined projection, and analyze their numerical accuracy and computational costs. Based on the advantages of different approaches, we propose a new hybrid method to efficiently find interior eigenpairs without compromising accuracy. An extensive set of experiments illustrate the efficiency and robustness of the proposed method.
In the third part of the work, we present a novel method to estimate the trace of matrix inverse that exploits the pattern correlation between the diagonal of the inverse of the matrix and that of some approximate inverse. We leverage various sampling and fitting techniques to fit the diagonal of the approximation to that of the inverse. Depending on the quality of the approximate inverse, our method may serve as a standalone kernel for providing a fast trace estimate with a small number of samples or as a variance reduction method for Monte Carlo in some cases. An extensive set of experiments demonstrate the potential of our method.
In the fourth part of this research, we provide first results on applying outlier detection techniques to effectively tackle the fusion blob detection problem on extremely large parallel machines. We present a real-time region outlier detection
algorithm to efficiently find blobs in fusion experiments and simulations. In addition, we propose an efficient scheme to track the movement of region outliers over time. We have implemented our algorithms with hybrid MPI/OpenMP and demonstrated we can achieve linear time speedup up to 1024 MPI processes and complete blob detection in two or three milliseconds.
Bio:
Lingfei Wu is a 6th year Ph.D. candidate in the computer science department at William & Mary, advised by Dr. Andreas Stathopoulos. His research interests are in the areas of high-performance scientific computing, large-scale machine learning, and big data analytics. In summer 2014, Lingfei was a computing sciences summer student at Lawrence Berkeley National Laboratory. In summer 2015, Lingfei was a summer research intern at IBM T.J.Watson Research Center. Before joining William & 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]]