Results 1111 - 1120 of 23825

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.

The spectrum of a matrix compression Q*AQ can be much more sensitive to small perturbations than the original matrix A, posing a challenge to the analysis of Rayleigh-Ritz methods. This talk considers the pseudospectrum of Q*AQ for Haar randomly sampled Q, i.e. the set of eigenvalues of all perturbations to Q*AQ. We describe some mild conditions under which its expected area is small.

Motivated by the resurgence of stochastic rounding, we consider stochastic nearness rounding of tall and thin real matrices. We provide theoretical and empirical evidence showing that, with high probability, the smallest singular value of a stochastically rounded matrix is bounded away from zero -- regardless of how close the original matrix was to being rank-deficient and even if it were rank-deficient. In other words, stochastic rounding implicitly regularizes tall-and-thin matrices so that the rounded version has full rank. We will briefly discuss the implications of such results for solving regression problems.

Sparse factorization algorithms, such as incomplete Cholesky factorization, are most commonly used for sparse problems, with sparsity patterns derived from the sparsity graph of the original matrix. In this talk, I will present a probabilistic perspective for identifying sparse factorization of dense positive-definite matrices. Cholesky factors encode conditional independence. Thus, the conditional independence of densely correlated Gaussian vectors directly translates to sparse Cholesky factorizations of dense covariance matrices. In certain spatial (statistical) problems, the screening effect provides a powerful heuristic for identifying conditional independence and thus discovering fast algorithms, asymptotically and in practice.

Kyng's randomized approximate Cholesky (AC) factorization can be better preconditioners than classical incomplete factorizations (IC) for graph Laplacian matrices and related matrices. One possible advantage of AC is that it may be better, on average, at preserving row sums than IC, i.e., if A is the matrix, L is an approximate or incomplete Cholesky factor, and e is the vector of all ones, L L' e is closer to A e for AC than IC, for similar numbers of nonzero entries. This begs a comparison of AC with modified IC (MIC), which is designed to preserve row sums. AC may still be better in this case, which means that preserving row sums is not the entire story. We will attempt to give a full explanation with numerical experiments with different modified/unmodified incomplete factorizations (threshold and level-based) and different matrix orderings. We will also propose some potential applications of AC in stochastic particle simulations that take advantage of the fact that its factorization is exact in expectation.