Results 1081 - 1090 of 23799
Randomized block Krylov iteration (RBKI) is perhaps the best algorithm we know for computing low-rank approximations and dominant singular vectors for a large matrix accessible by matrix products. Existing bounds show that RBKI achieves nearly optimal runtime scaling for rank-k approximation when executed both a large block size of k and a small block size of 1. However, in practice, the computational efficiency is often maximized by choosing the block size between these extremes, demonstrating a gap between theory in practice. This talk presents new theoretical results which justify the RBKI algorithm for any block size between 1 and k. The main technical advance is a new lower bound on the singular value of a square random block Krylov matrix.
Krylov subspace methods are one of the premier techniques to estimate the extreme eigenvalues of a matrix. While these methods are well-understood in the Hermitian setting, due, in part, to the existence of an orthonormal eigenbasis and the connection to orthogonal polynomials, many questions still remain in the non-Hermitian case. In this talk, I'll discuss some recent work on estimating the extreme eigenvalues of a non-Hermitian matrix, as well as ideas and barriers for more global estimation of the spectrum as a whole.
We present an inverse-free, randomized, and highly parallellizable algorithm for solving a structured generalized eigenvalue problem involving a Hermitian pencil (A,B) whose Crawford number is positive. The method is an efficient, structured modification of the divide-and-conquer approach for the general case, based on the idea of randomization as a regularization factor (in the manner of smoothed analysis). This is joint work with James Demmel and Ryan Schneider.
We study circuits for computing linear transforms defined by Kronecker power matrices. Depth-2 circuits are central because (1) all known low-depth constructions (e.g., the fast Walsh–Hadamard transform and Yates’ algorithm) can be derived from them, and...
Spectral graph theory within theoretical computer science has largely focused on the graph Laplacian. This workshop will consider other operators — such as Schrödinger operators, magnetic Laplacians, and Kikuchi matrices — on graphs as well as other spaces...
Click here to register for this event.
Quasicrystals are fascinating materials that sit between the extremes of highly ordered crystals and disordered matter. Their discovery, which earned Dan Shechtman the 2011 Nobel Prize in Chemistry, has fueled interest in the mathematics of aperiodic order. For a computational spectral theorist, the field is ripe with challenging problems. Even the simplest models exhibit exotic behavior: the spectrum of the one-dimensional Fibonacci Hamiltonian is a Cantor set; the spectrum of its two-dimensional analogue is the sum of Cantor sets. Can one estimate the fractal dimension of such spectra? Other two-dimensional models derive from aperiodic tilings of the plane, such as Roger Penrose’s famous kite-and-dart construction. The graph Laplacians for such models contain high-multiplicity eigenvalues having compactly supported eigenvectors, for which one seeks a tidy description. This talk will survey a variety of such problems: describing the computational challenges, acknowledging a debt to excellent mathematical software, and highlighting the need for continued algorithm development.
This talk describes collaborative work with James Chok, Matthew Colbrook, David Damanik, Jake Fillman, Anton Gorodetski, May Mei, and Charles Puelz.
Mark Embree is a professor of mathematics at Virginia Tech, where he led the undergraduate major in computational modeling and data analytics from 2015 to 2025. He served on the faculty of the Department of Computational and Applied Mathematics at Rice University from 2002 to 2013, following graduate work with Andy Wathen and a postdoc with Nick Trefethen, both at Oxford. With Trefethen, he coauthored Spectra and Pseudospectra: The Behavior of Nonnormal Matrices and Operators. His research interests include matrix computations, non-self-adjoint operators, and spectral theory.
Refreshments will be served at 3 p.m., before the event.
The Richard M. Karp Distinguished Lectures were created in Fall 2019 to celebrate the role of Simons Institute Founding Director Dick Karp in establishing the field of theoretical computer science, formulating its central problems, and contributing stunning results in the areas of computational complexity and algorithms. Formerly known as the Simons Institute Open Lectures, the series features visionary leaders in the field of theoretical computer science and is geared toward a broad scientific audience.
The lecture recording URL will be emailed to registered participants. This URL can be used for immediate access to the livestream and recorded lecture. Lecture recordings will be publicly available on SimonsTV about five days following each presentation unless otherwise noted.
The Simons Institute regularly captures photos and video of activity around the Institute for use in publications and promotional materials.
If you require special accommodation, please contact our access coordinator at simonsevents@berkeley.edu with as much advance notice as possible.