- You are here:
- GT Home
- Home
- News & Events

Thursday, April 23, 2009 - 13:00 ,
Location: Skiles 255 ,
Per-Gunnar Martinsson ,
Dept of Applied Mathematics, University of Colorado ,
Organizer: Haomin Zhou

Note special day

Linear boundary value problems occur ubiquitously in many areas of
science and engineering, and the cost of computing approximate
solutions to such equations is often what determines which problems
can, and which cannot, be modelled computationally. Due to advances in
the last few decades (multigrid, FFT, fast multipole methods, etc), we
today have at our disposal numerical methods for most linear boundary
value problems that are "fast" in the sense that their computational
cost grows almost linearly with problem size. Most existing "fast"
schemes are based on iterative techniques in which a sequence of
incrementally more accurate solutions is constructed. In contrast, we
propose the use of recently developed methods that are capable of
directly inverting large systems of linear equations in almost linear
time. Such "fast direct methods" have several advantages over
existing iterative methods:
(1) Dramatic speed-ups in applications involving the repeated solution
of similar problems (e.g. optimal design, molecular dynamics).
(2) The ability to solve inherently ill-conditioned problems (such as
scattering problems) without the use of custom designed preconditioners.
(3) The ability to construct spectral decompositions of differential
and integral operators.
(4) Improved robustness and stability.
In the talk, we will also describe how randomized sampling can be used
to rapidly and accurately construct low rank approximations to matrices.
The cost of constructing a rank k approximation to an m x n matrix A
for which an O(m+n) matrix-vector multiplication scheme is available
is O((m+n)*k). This cost is the same as that of the well-established
Lanczos scheme, but the randomized scheme is significantly more robust.
For a general matrix A, the cost of the randomized scheme is O(m*n*log(k)),
which should be compared to the O(m*n*k) cost of existing deterministic
methods.

Series: Graph Theory Seminar

A well know theorem of Kuratowski states that a graph is planar graph iff it contains no TK_5 or TK_{3,3}. In 1970s Seymour conjectured that every 5-connected nonplanar graph contains a TK_5. In the talk we will discuss several special cases of the conjecture, for example the graphs containing K_4^- (K_4 withour an edge). A related independent paths theorem also will be covered.

Series: Analysis Seminar

We will discuss a new method of asymptotic analysis of matrix-valued Riemann-Hilbert problems that involves dispensing with analyticity in favor of measured deviation therefrom. This method allows the large-degree analysis of orthogonal polynomials on the real line with respect to varying nonanalytic weights with external fields having two Lipschitz-continuous derivatives, as long as the corresponding equilibrium measure has typical support properties. Universality of local eigenvalue statistics of unitary-invariant ensembles in random matrix theory follows under the same conditions. This is joint work with Ken McLaughlin.

Series: ACO Student Seminar

We construct efficient and natural encryption schemes that remain
secure (in the standard model) even when used to encrypt messages that
may depend upon their secret keys. Our schemes are based on
well-studied "noisy learning" problems. In particular, we design
1) A symmetric-key cryptosystem based on the "learning parity with
noise" (LPN) problem, and
2) A public-key cryptosystem based on the "learning with errors"
(LWE) problem, a generalization of LPN that is at least as hard as
certain worst-case lattice problems (Regev, STOC 2005; Peikert, STOC
2009).
Remarkably, our constructions are close (but non-trivial) relatives of
prior schemes based on the same assumptions --- which were proved
secure only in the usual key-independent sense --- and are nearly as
efficient. For example, our most efficient public-key scheme encrypts
and decrypts in amortized O-tilde(n) time per message bit, and has
only a constant ciphertext expansion factor. This stands in contrast
to the only other known standard-model schemes with provable security
for key-dependent messages (Boneh et al., CRYPTO 2008), which incur a
significant extra cost over other semantically secure schemes based on
the same assumption. Our constructions and security proofs are simple
and quite natural, and use new techniques that may be of independent
interest.
This is joint work with Chris Peikert and Amit Sahai.

Series: Research Horizons Seminar

The eigenvalues of the Laplacian are the squares of the frequencies of
the normal modes of vibration, according to the wave equation. For this
reason, Bers and Kac referred to the problem of determining the shape of
a domain from the eigenvalue spectrum of the Laplacian as the question of
whether one can "hear" the shape. It turns out that in general the answer
is "no." Sometimes, however, one can, for instance in extremal cases
where a domain, or a manifold, is round. There are many "isoperimetric"
theorems that allow us to conclude that a domain, curve, or a manifold,
is round, when enough information about the spectrum of the Laplacian
or a similar operator is known. I'll describe a few of these theorems
and show how to prove them by linking geometry with functional analysis.

Series: Graph Theory Seminar

I will discuss some new results, as well as new interpretations of some old results, concerning reduced divisors (a.k.a. G-parking functions) on graphs, metric graphs, and tropical curves.

Series: ACO Colloquium

The past 10 years have seen a confluence of research in sparse approximation amongst computer science, mathematics, and electrical engineering. Sparse approximation encompasses a large number of mathematical, algorithmic, and signal processing problems which all attempt to balance the size of a (linear) representation of data and the fidelity of that representation. I will discuss several of the basic algorithmic problems and their solutions, focusing on special classes of matrices. I will conclude with an application in biological testing.

Series: CDSNS Colloquium

In the talk I will discuss the periodicity of solutions to the classical forced pendulum equation y" + A sin y = f(t) where A= g/l is the ratio of the gravity constant and the pendulum length, and f(t) is an external periodic force with a minimal period T. The major concern is to characterize conditions on A and f under which the equation admits periodic solutions with a prescribed minimal period pT, where p>1 is an integer. I will show how the new approach, based on the critical point theory and an original decomposition technique, leads to the existence of such solutions without requiring p to be a prime as imposed in most previous approaches. In addition, I will present the first non-existence result of such solutions which indicates that long pendulum has a natural resistance to oscillate periodically.

Series: Analysis Seminar

Note special time

In 1908 Hadamard conjectured that the biharmonic Green function must be positive. Later on, several counterexamples to Hadamard's conjecture have been found and a variety of upper estimates were obtained in sufficiently smooth domains. However, the behavior of the Green function in general domains was not well-understood until recently. In a joint work with V. Maz'ya we derive sharp pointwise estimates for the biharmonic and, more generally, polyharmonic Green function in arbitrary domains. Furthermore, we introduce the higher order capacity and establish an analogue of the Wiener criterion describing the precise correlation between the geometry of the domain and the regularity of the solutions to the polyharmonic equation.

Series: Geometry Topology Seminar

In this talk we will introduce the notion of a cube diagram---a surprisingly subtle, extremely powerful new way to represent a knot or link. One of the motivations for creating cube diagrams was to develop a 3-dimensional "Reidemeister's theorem''. Recall that many knot invariants can be easily be proven by showing that they are invariant under the three Reidemeister moves. On the other hand, simple, easy-to-check 3-dimensional moves (like triangle moves) are generally ineffective for defining and proving knot invariants: such moves are simply too flexible and/or uncontrollable to check whether a quantity is a knot invariant or not. Cube diagrams are our attempt to "split the difference" between the flexibility of ambient isotopy of R^3 and specific, controllable moves in a knot projection. The main goal in defining cube diagrams was to develop a data structure that describes an embedding of a knot in R^3 such that (1) every link is represented by a cube diagram, (2) the data structure is rigid enough to easily define invariants, yet (3) a limited number of 5 moves are all that are necessary to transform one cube diagram of a link into any other cube diagram of the same link. As an example of the usefulness of cube diagrams we present a homology theory constructed from cube diagrams and show that it is equivalent to knot Floer homology, one of the most powerful known knot invariants.