Hillar C.J.,Mathematical science Research Institute |
Lim L.-H.,University of Chicago
Journal of the ACM | Year: 2013
We prove that multilinear (tensor) analogues of many efficiently computable problems in numerical linear algebra are NP-hard. Our list includes: determining the feasibility of a system of bilinear equations, deciding whether a 3-tensor possesses a given eigenvalue, singular value, or spectral norm; approximating an eigenvalue, eigenvector, singular vector, or the spectral norm; and determining the rank or best rank-1 approximation of a 3-tensor. Furthermore, we show that restricting these problems to symmetric tensors does not alleviate their NP-hardness. We also explain how deciding nonnegative definiteness of a symmetric 4-tensor is NP-hard and how computing the combinatorial hyperdeterminant is NP-, #P-, and VNP-hard. Categories and Subject Descriptors: G.1.3 [Numerical Analysis]: Numerical Linear Algebra General Terms: Algorithms, Theory Additional Key Words and Phrases: Numerical multilinear algebra, tensor rank, tensor eigenvalue, tensor singular value, tensor spectral norm, system of multilinear equations, hyperdeterminants, symmetric tensors, nonnegative definite tensors, bivariate matrix polynomials, NP-hardness, #P-hardness, VNP-hardness, undecidability, polynomial time approximation schemes. © 2013 ACM.
Leach J.,Mathematical science Research Institute
Classical and Quantum Gravity | Year: 2016
We prove the existence of a large class of initial data for the vacuum Einstein equations which possess a finite number of asymptotically Euclidean and asymptotically conformally cylindrical or periodic ends. Aside from being asymptotically constant, only mild conditions on the mean curvature of these initial data sets are imposed. © 2016 IOP Publishing Ltd.
Schlue V.,University of Cambridge |
Schlue V.,Mathematical science Research Institute
Communications in Mathematical Physics | Year: 2015
In this global study of solutions to the linear wave equation on Schwarzschild de Sitter spacetimes we attend to the cosmological region of spacetime which is bounded in the past by cosmological horizons and to the future by a spacelike hypersurface at infinity. We prove an energy estimate capturing the expansion of that region, which combined with earlier results for the static region, yields a global boundedness result for linear waves. It asserts that a general finite energy solution to the global initial value problem has a limit on the future boundary at infinity that can be viewed as a function on the standard cylinder with finite energy, and that, moreover, any decay along the cosmological horizon is inherited along the future boundary. In particular, we exhibit an explicit nonvanishing quantity on the future boundary of the spacetime consistent with our expectations for the nonlinear stability problem. Our results apply to a large class of expanding cosmologies near the Schwarzschild de Sitter geometry, in particular subextremal Kerr de Sitter spacetimes. © 2014, Springer-Verlag Berlin Heidelberg.
Agency: NSF | Branch: Standard Grant | Program: | Phase: OFFICE OF MULTIDISCIPLINARY AC | Award Amount: 93.22K | Year: 2015
The meeting Partnerships: Workshop on Non-profit/NSF Collaborations will take place at the National Science Foundation on May 28-29, 2015. The National Science Foundation (NSF) and non-profit organizations each provide critical support to the U.S. basic research enterprise in the mathematical and physical sciences. While the missions of these funders differ, many of their goals align and the grantee communities have significant overlap. In recent years, efforts of private organizations have played a more and more significant part of the whole picture of the funding of science. There are great opportunities: private support can be very flexible and allow discovery-driven investigation beyond what public funding can tolerate. This workshop will explore the ways in which the Directorate of Mathematical and Physical Sciences at the NSF and private foundations can form useful partnerships.
This workshop will examine partnerships between the Directorate of Mathematical and Physical Sciences (MPS) at NSF and non-profit funders in MPS-related disciplines to
- understand different models of collaboration (the how);
- understand different motivations for collaboration (the why); and
- develop opportunities for future communication and/or collaboration.
After examining partnerships of various types, participants will discuss creative opportunities for future coordination. Discussions will entail both scientific focus and logistical considerations. The central events of the workshop will be a series of case studies, and a series of small-group discussions with reports back to the workshop as a whole. A technical writer will take notes and synthesize take-away themes for a report that will be made widely available.
Agency: NSF | Branch: Standard Grant | Program: | Phase: | Award Amount: 674.67K | Year: 2010
The project has three main aspects. First, it addresses the infrastructure of symbolic computation as a research tool supported by Macaulay2. This includes the implementation of new features, bug fixes, user support, further documentation, and multiplatform releases of new versions that will maintain and develop Macaulay2 as a major tool used for research in a broad range of fields. Second, it addresses manpower needs, by training young people in the use of Macaulay2, and by engaging and expanding the collaborations that have been a hallmark of Macaulay2 development. In this way it will enable more of the research community to develop competence in this kind of experimental mathematics. Third, research done under this project will develop better algorithms for some key computational problems, such as computing normalization. Other goals of the research are to improve the implementation of the core Groebner basis algorithms, uncover new methods for the study of biological networks, and develop better and more reliable methods in the emerging field of numerical algebraic geometry.
Macaulay2 is a free computer algebra software system dedicated to the qualitative investigation of systems of polynomial equations in many variables. The computations it can perform have uses in many fields of mathematics and science, from algebraic geometry to genomics. The research to be done under this grant extends the computational methods built into Macaulay2. In addition, the grant will provide many opportunities to train young mathematicians and other scientists in the use of these tools, and to bring other experts? knowledge to bear on them through conferences, schools, and Intense Collaboration Workshops centered on the important issues in this field. The project will enable new collaborations between Macaulay2 software developers from the research community and scientists from physics and biology as well as pure mathematicians. It will introduce graduate students, postdocs, and junior and senior mathematicians to the use of computers in research mathematics and help them acquire powerful skills in programming and development of algorithms that will enhance their own research. Experimental results found with Macaulay2 have helped in the formulation, development, and solution of many conjectures. Through the improvement of computational tools, the proposed research will impact many fields of mathematics and science.