Linear least squares/regression problems are of primary importance in Applied Mathematics, Theoretical Computer Science, Statistics and Data Science; either standalone on their own, or as part of a sequence in the outer iterations of an optimization method. Intellectual Merit. The PIs propose to accelerate the solution of least squares problems with dynamic randomized preconditioners that can change across iterations, and focus on three research directions: (1) Design and analysis of local preconditioners, that change across inner iterations inside a least squares solver; (2) Design and analysis of global preconditioners, that change across least squares problems in outer iterations of an optimization method; (3) Novel perturbation theory for the analysis of randomized preconditioned least squares problems. Specific optimization methods to be investigated include: (i) Iteratively Reweighted Least Squares for solving Generalized Linear Models, including logistic and Poisson regression; (ii) interior point methods for linear and semidefinite programs; (iii) nonlinear least squares for training overparameterized neural networks; and (iv) high-order order orthogonal iteration for computing low-rank tensor decompositions. Broader Impacts. Due to the ubiquity of least squares/regression, the proposed work on dynamical randomized preconditioners will impact many domains; we will pay particular attention to their impact in human genetics, an area of expertise for some of the PIs. The effectiveness of the proposed algorithms will be validated on the standard test suites, as well as large-scale matrices from the UK Biobank dataset. The proposed dynamical preconditoning will speed up randomized algorithms, and will be of benefit in newly emerging multiple-precision environments, which call for fast methods to deliver low accuracy, and powerful but expensive methods to deliver high accuracy. The proposed perturbation theory will produce informative bounds for randomized algorithms, while also advancing the wider areas of pure and applied mathematics. The PIs will target their open source implementations for impact in applied research, industry, and educational engagement; and will make them available to the general public, with close attention paid to reproducibility.

Quantifying the effects of input variations on computed outputs is critical in scientific computing; it is generally referred to as sensitivity analysis (SA). SA plays a key role in the verification, the understanding and, central to this proposal, the simplification of models. Indeed, models are often "simplified" by constructing mathematical surrogates whose properties approximate some������������������but not all������������������of the properties of the original model with the goal of enabling computational study. We propose to develop computational methods to (i) identify of the ���������������"important parts" of a model and (ii) quantify the effects of ignoring the "less important parts." In other words, our work will contribute to dimension reduction and sensitivity analysis. The research is organized around three complementary thrusts in numerical linear algebra, nonlinear solvers and global sensitivity analysis. The RTG participants will not just "be trained," they will play an essential role in our research activities. Group dynamic and esprit de corps will be generated through working groups. Every year, we will organize three working groups consisting of undergraduates, graduate trainees, postdocs and faculty. Each group will be active for one semester and be led by a member of the senior personnel, possibly jointly with one of the postdoctoral fellows. The working groups will concentrate on specific aspects of randomized numerical analysis through hands-on exploratory activities of either computational or analytical nature. Advanced graduate students will be in charge of introducing the undergraduates to basic concepts through short presentations. The project will support 5 undergraduates per year as well as, over the duration of the award, 9 graduate students and 2 postdocs. The project will have a lasting impact on curriculum and departmental activities. It also has significant outreach components to (i) industry and national labs, (ii) to high school (North Carolina School of Science and Mathematics) and (iii) to the public as well as through the development on graduate distance education courses. Our public outreach efforts will take place in collaboration with the NC State Office of Public Science.

The success of Randomized Numerical Linear Algebra (RandNLA) relies on efficient low-dimensional representations by means of sketching and sampling ������������������ techniques that have mostly not been���������������validated������������������ according to the standards of traditional scientific computing. This lack of scientific computing validation creates a significant gap for application of RandNLA in DoE������������������s heterogeneous extreme-scale computing environments, where operation counts are often less important than data movement; the judicious use of mixed precision (at the 64, 32, 16 bit and possibly lower levels) is critical for performance,and fault resilience and reproducibility are of paramount importance. State-of-the-art RandNLA sketching and sampling methods do not address these issues, in either theory or practice. The proposed research is motivated by the following broad agenda: How to de-sign RandNLA solvers for heterogeneous extreme-scale computing environments, that incorporate fault resilience, reproducibility, numerical accuracy, and numerical stability in the context of:randomization,stochastic and statistical uncertainty, mixed precision arithmetic, and various target accuracies (a specificn umber of significant digits, a correct sign, a correct ordinal ranking, the eyeball norm, etc.) We propose to develop randomized least squares (LS) solvers whose accuracy is certified by a contextually aware sensitivity analysis, with applications to optimization and ill-posed problems. The proposed contextually aware sensitivity analysis will guide the design of solvers for over- or under-determined problems in their most general form, including: (i) iteratively reweighted LS problems in Gener-alized Linear Models (GLMs); (ii) LS sequences in interior point methods (IPMs) for linear programs; (iii) regularized LS problems in inverse problems. The purpose of randomization will be two-fold: (i) dimension reduction via sketching/sampling of rows, columns, and elements of the matrix (sparsification); and (ii) preconditioning, both static and dynamic (flexible) at two levels:local preconditioners that accelerate the inner iterations inside a least squares solver; and global preconditioners that accelerate the outer iterations of GLM or IPM optimization methods.

Within the framework of Randomized Numerical Linear Algebra (RandNLA, the PIs propose to establish "a principled foundation for fast prototyping via randomization", where fast randomized matrix algorithms act as non-invasive and robust black-box accelerators for existing methods and software, and implementations take the form of warm starts; preconditioners; and surrogate or reduced-order models. We propose the novel use of randomization to combine complementary algorithmic and statistical perspectives: The statistical viewpoint attributes randomness to an inherent and desirable property of the data, while the algorithmic viewpoint claims randomness as a computational resource to be exploited. The coupling of these complementary approaches poses challenging mathematical problems to be investigated in the proposed work. Intellectual Merit. The proposed work will establish the foundations for fast prototyping in two directions: A "Multi-Pronged Direction" to bring RandNLA to the next level and explore what is technically feasible; and an overarching "Synergy Direction" that fuses the results for prototyping. The "Multi-Pronged Direction" includes the following topics: (i) Matrix perturbation theory, to bridge the gap between traditional worst-case bounds for asymptotically small perturbations on the one hand; and perturbations caused by stochastic noise, and missing or highly corrupted matrix entries on the other hand. (ii) Implicit versus explicit regularization, where randomness as a computational resource for speeding up algorithms additionally contributes to implicit statistical regularization, thereby improving statistical and numerical robustness. (iii) Krylov space methods for fast computation of good warm-starts and computation of surrogate models in the form of low-rank approximations, and specifically a better understanding of these methods in an algorithm-independent setting. (iv) Randomized basis construction methods that use matrix factorizations to compute low-rank approximations at low to moderate levels of accuracy. The "Synergy Direction" will explore topics like ultra-low accuracy matrix computations in machine learning applications, where merely a correct sign or exponent is sufficient. As a group, the PIs possess unrivalled and complementary expertise in applying fundamental mathematical tools to numerical applications in machine learning, data mining and scientific computing. Broader Impacts. The proposed methods will have significant impact in big data analysis, scientific computing, data mining and machine learning, where matrix computations are of paramount importance. The proposed work in rapid prototyping is fundamentally interdisciplinary and will enable fast, yet user-friendly extraction of insight from large-scale data these societally-important scientific domains. Specifically, the proposed work will (i) create a numerically reliable and robust footing for fast prototyping; (ii) advance mathematics at the interface of computer science and statistics, one of the objectives being a synergy of numerical and statistical robustness; and (iii) advance the development of an interdisciplinary community with RandNLA as a pillar for the mathematics of data. The award will allow the PIs to increase their active engagement in reaching out to undergraduate and graduate students, and research communities in numerical linear algebra, theoretical computer science, and machine learning. The PIs will continue their long-standing commitment to involve underrepresented students in research and educational activities at both, the undergraduate and graduate levels.

North Carolina State University will define fundamental algorithms and algorithmic techniques for the project, do small-scale proof-of-principle experiments and performance evaluations, and work with system builders to define experiments and evaluations. The XDATA program seeks to develop computational techniques and software tools for analyzing large volumes of data, both semi-structured (e.g., tabular, relational, categorical, meta-data) and unstructured (e.g., text documents, message traffic). Central challenges to be addressed include a) developing scalable algorithms for processing imperfect data in distributed data stores, and b) creating effective human-computer interaction tools for facilitating rapidly customizable visual reasoning for diverse missions.

In the summer of 2015 (June 15-June 26, 2015), we will organize the Gene Golub SIAM Summer School on the topic of Randomization in Numerical Linear Algebra (RandNLA) at the European Cultural Centre of Delphi(ECCD). (See the Summer School web site at http://www.cs.rpi.edu/~drinep/G2S3_RandNLA_2015/ for up-to-date information.) In this proposal, we are requesting travel support for approximately 25 US-based PhD students that we expect to admit at the summer school, at an average cost of $1,000 per person, for a total of $25,000. We have already secured support from SIAM via the Gene Golub SIAM Summer School program to support all local expenses for the students (accomodation, meals, facility use, etc.). The organizers of the summer school are (in alphabetical order): Petros Drineas (Rensselaer Polytechnic Institute, USA), Efstratios Gallopoulos (University of Patras, Greece), Ilse Ipsen (North Carolina State University, USA), and Michael W. Mahoney (University of California Berkeley, USA).

Funds are requested to support the participation of US based early-career scientists and Ph.D. students at the Householder Symposium XIX on Numerical Linear Algebra. The Symposium will take place 8-13 June 2014 in Spa, Belgium. The Symposium is very informal, with the intermingling of early career and established researchers a high priority. Participants are expected to attend the entire meeting. The fifteenth Householder Prize for the best thesis in numerical linear algebra since 1 January 2011 will be awarded. Numerical linear algebra plays a central role in scientific computing. For the 2014 Symposium the Householder Committee aims for a healthy balance of theoretical, computational and applied presentations. There is an emphasis on broad relevance, rather than results that are of interest only in a narrow subfield. Since abstract submission is only 6 months in advance of the meeting date, the Symposium always features ``hot'' research topics and emerging areas. For the upcoming meeting, a large number of submissions on the following topics are expected: Nonlinear eigenvalue problems, tensor algorithms and analysis, domain decomposition and multilevel methods, Krylov space methods for linear systems and eigenvalue problems, algorithms for structured matrices, computation of matrix functions, randomized algorithms, as well as application to optimization, differential equations, signal and image processing, control, electronic structure calculations, data analysis, information retrieval, bioinformatics, and structural, mechanical and aerospace engineering. This proposal is submitted on behalf of the Householder Committee, to ensure the attendance of well qualified Ph.D. students at US institutions, as well as early-career scientists who received their Ph.D.'s after 1 January 2011 and are currently working in the US. Support of this group will have a positive impact on the continued strong competitiveness of the US in this crucial discipline, with its connections to a large number of scientific computing topics. Individual benefits for early career researchers who have attended a Householder Symposium include: career advice from established researchers, enhanced visibility in the community, ideas for REU programs, and several NSF funded research projects that arose directly from collaborations established or advice received at the Householder Symposium. Previous NSF funding for the Householder Symposia has enabled the participation of early-career researchers from institutions that do not have a history of research funding.

The PI proposes to investigate the numerical accuracy and robustness of randomized algorithms for matrix multiplication and overdetermined least squares problems. APPROPRIATENESS FOR EAGER. The proposed research is appropriate for EAGER funding because it lies on the intersection of different areas, including numerical analysis, theoretical computer science, and probability, and does not neatly fit into a single program. Randomized algorithms for matrix computations are being developed mainly by the theoretical computer science and geometric functional analysis communities, with faster asymptotic time and space complexity in mind. However, numerical analysts are distrustful of randomized algorithms because randomization makes it impossible to produce replicable results; because the error bounds are only probabilistic and contain unknown constants; and because the numerical behavior of the algorithms is completely unknown. The proposed research tries to bridge the gap by investigating numerical properties of randomized algorithms in floating point arithmetic, their sensitivity to perturbations in the inputs, their robustness, and their numerical accuracy. The proposed research is exploratory and highly novel, because we have to invent new approaches and concepts to capture the numerical behavior of randomized algorithms. It is not at all clear what "numerical stability'' means in this context, let alone how it should be defined. How does one distinguish variability caused by randomization from variability caused by finite precision? Where should parameters like failure probability, choice of probabilities, and amount of sampling be accounted for? INTELLECTUAL MERIT. Existing analyses of randomized algorithms are mostly concerned with asymptotic time and space complexity in exact arithmetic, and very little is known about their numerical behavior in floating point arithmetic. The PI proposes to develop a numerical perturbation and stability theory for randomized algorithms for matrix multiplication and least squares problems. Proposed approaches will include matrix perturbation analysis, probability theory, and methods on matrix manifolds. Extensive numerical experiments will be performed to corroborate the analyses. BROADER IMPACTS. The motivation for randomized algorithms is the need for streaming massive data sets that are too large for traditional deterministic algorithms. Randomized algorithms have been implemented successfully for applications such as pattern recognition, social network analysis, population genetics, circuit testing, and text classification. The proposed research will help to determine for which application domains a randomized algorithm is suitable. The proposed research will also result in practical bounds and recommendations for parameter choices to achieve a user-specified accuracy. The proposed research is highly relevant because randomized algorithms will be indispensable for exascale computing, in applications like high energy physics and astronomy, where peta bytes of data are expected to stream in daily and tasks like rare event detection make it imperative that we have a good understanding of numerical accuracy and robustness.

This renewal proposal represents the North Carolina State University component of a consortium comprised of Duke University, North Carolina State University, UNC Chapel Hill and the National Institute of Statistical Sciences (NISS) to expand and provide five year's support for the Statistical and Applied Mathematical Sciences Institute (SAMSI). This institute, which is housed in a portion of the NISS building in RTP, is a national institute with semester and year-long programs to foster and promote scientific investigations combining in unique ways both statistics and applied mathematics. Ralph C. Smith will serve as the SAMSI Associate Director from North Carolina State University. He will participate fully in research efforts, directing of postdoctoral fellows and graduate students, and collaborating with junior and senior visitors on specific research programs. The requested funds will support the efforts of Smith in education and outreach activities (workshops, tutorials, etc.) as well as the management of SAMSI. Funds are also requested to support as yet unnamed senior researchers, postdocs and graduate students. To promote education and outreach for K-12, SAMSI will sponsor two Kenan Fellows per year to develop curricula which incorporate mathematical and statistical concepts associated with SAMSI programs. The Kenan Fellows Program is designed to promote teacher leadership and advance K-12 science and mathematics education through the sponsorship of public school teachers competitively selected to participate in two-year fellowships while remaining active in the classroom. During the program, the selected teachers will collaborate with SAMSI mentors, for approximately five weeks during the summer and periodically during the academic year, on curriculum development. To the extent possible, the SAMSI mentors will also be invited to participate in classroom activities. Presently, Kenan Fellows are selected from North Carolina and the resulting curriculum is employed in-state. However, the North Carolina curriculum standards are consistent with national standards and we will work with the Kenan Foundation to disseminate the SAMSI-motivated curricula at the national level. We will also work toward national advertising and recruitment of teachers so that the teacher training, curriculum development and curriculum dissemination all evolve to the national level.

Funds are requested to support the participation of USA-based early career scientists and Ph.D. students at the Householder Symposium XVIII on Numerical Linear Algebra. The Symposium will take place on June 12-17, 2011, at the Granlibakken Conference Center in Tahoe City, California. The Symposium is very informal, with the intermingling of early career and established researchers a high priority. Participants are expected to attend the entire meeting. The fourteenth Householder Prize for the best thesis in numerical linear algebra since January 1, 2008 will be awarded. Intellectual Merit: Numerical linear algebra plays a central role in scientific computing. For the 2011 Symposium the Householder Program Committee aims for a healthy balance of theoretical, computational and applied presentations. There is an emphasis on broad relevance, in contrast to results that are of interest only in a narrow subfield. Since abstract submission is only 6 months in advance of the meeting date, the Symposium always features "hot" research topics and emerging areas. For the upcoming meeting, a large number of submissions on the following topics are expected: Nonlinear eigenvalue problems, tensor algorithms and analysis, domain decomposition and multilevel methods, Krylov space methods for linear systems and eigenvalue problems, algorithms for structured matrices, computation of matrix functions, randomized algorithms, as well as application to optimization, differential equations, signal and image processing, control, electronic structure calculations, data analysis, information retrieval, bioinformatics, and structural, mechanical and aerospace engineering. Broader Impacts: This proposal is submitted on behalf of the Householder Program Committee, to ensure the attendance of well qualified Ph.D. students at US institutions, as well as early career scientists who received their Ph.D.?s after January 1, 2008 and are currently working in the US. Support of this group will have a positive impact on the continued strong competitiveness of the US in this crucial discipline, with its connections to a large number of scientific computing topics. Individual benefits for early career researchers who have attended a Householder Symposium include: career advice from established researchers, enhanced visibility in the community, ideas for REU programs, and several NSF funded research projects that arose directly from collaborations established or advice received at the Householder Symposium. Previous NSF funding for the Householder Symposia has enabled the participation of early career researchers from institutions that do not have a history of research funding.