Exploring the Conformations of Protein-Bound DNA: Adding Geometry to Known Topology
Mary Therese Padberg (IMA postdoc)
Tuesday, January 24, 2012, Lind Hall 305, 3:00-4:00

Understanding the conformation of protein-bound DNA is extremely important for biological and medical research, including improvement of drug creation and administration methods. Many protein-bound DNA conformations have been catalogued in the Protein Data Base; however the process of cataloging larger complexes can prove extremely difficult or unsuccessful. When standard lab techniques fail to determine a conformation, we turn to a branch of mathematical knot theory, tangle analysis, used in conjunction with difference topology experiments to analyze the topology of protein- bound DNA. In this talk, we will discuss these techniques and explain why topology alone is not enough. We will introduce preliminary software which can be used to determine likely DNA geometries consistent with protein-bound DNA topologies. Combining geometric and topological solutions will allow us to more accurately describe conformations for large protein-bound DNA complexes.

Computational Knot Theory with KnotPlot
Rob Scharein (Hypnagogic Software)
Thursday, February 2nd, 2012, Lind Hall 305, 3:00-4:00

Mathematical knot theory is an exciting branch of topology that is relevant to physics, chemistry and biology. After a brief introduction to knot theory, we will explore several applications where computational methods play a useful role. When experimenting with knots on a computer, it is helpful to have powerful tools for the creation of initial conformations, for performing simulations on those conformations and also to compute topological and geometric properties of any resulting products. One such tool is the software KnotPlot, developed by the speaker over a period of many years. KnotPlot permits a wide range of interesting experiments to be performed. Several of these will be discussed, one important area being the tangling and untangling of DNA. Finally, we will dip into the more esoteric realm of higher dimensional knotting.

TBD
Arthur Szlam (IMA)
Tuesday, February 7th, 2012, Lind Hall 305, 3:00-4:00

Two-stage stochastic optimization problems with stochastic ordering constraints on the recourse function
Gabriela Martinez (IMA)
Wednesday, February 22nd, 2012, Lind Hall 305, 3:00-4:00

We consider two-stage risk-averse stochastic optimization problems with a stochastic ordering constraint on the recourse function. Two new characterizations of the increasing convex order relation are provided. They are based on conditional expectations and on integrated quantile functions: a counterpart of the Lorenz function. We propose two decomposition methods to solve the problems and prove their convergence. Our methods exploit the decomposition structure of the risk-neutral two-stage problems and construct successive approximations of the stochastic ordering constraints. Numerical results confirm the efficiency of the methods

New and improved Johnson-Lindenstrauss embeddings via the Restricted Isometry Property
Felix Krahmer (Georg-August-Universität zu Göttingen)
Tuesday, March 20, 2012, Lind Hall 305, 3:00-4:00

The Johnson-Lindenstrauss (JL) Lemma states that any set of p points in high dimensional Euclidean space can be embedded into O<(δ ⁻² log(p)) dimensions, without distorting the distance between any two points by more than a factor between 1 − δ and 1 + δ . We establish a new connection between the JL Lemma and the Restricted Isometry Property (RIP), a well-known concept in the theory of sparse recovery often used for showing the success of ℓ₁-minimization.

Consider an m X N matrix satisfying the (k, δ_k)-RIP and an arbitrary set E of O(e^k) points in R^N. We show that with high probability, such a matrix with randomized column signs maps E into R^m without distorting the distance between any two points by more than a factor of 1±4δ_k. Consequently, matrices satisfying the Restricted Isometry of optimal order provide optimal Johnson-Lindenstrauss embeddings up to a logarithmic factor in N. Moreover, our results yield the best known bounds on the necessary embedding dimension m for a wide class of structured random matrices. In particular, for partial circulant, partial Fourier, and partial Hadamard matrices, our method optimizes the dependence of m on the distortion δ: We improve the recent bound m = O(δ⁻⁴ log(p) log⁴(N)) of Ailon and Liberty (2010) to m = O(δ⁻² log(p) log⁴(N)), which is optimal up to the logarithmic factors in N. Our results also have a direct application in the area of compressed sensing for redundant dictionaries.

This is joint work with Rachel Ward.

Subspace Clustering with Global Dimension Minimization And Application to Motion Segmentation
Bryan Poling (University of Minnesota)
Tuesday, April 3, 2012, Lind Hall 305, 3:00-4:00

Global Dimension Minimization is a new geometric method for Subspace Clustering. In this talk we will introduce subspace clustering (also called Hybrid Linear Modeling) and explore a motivating example. We will investigate some of the new concepts involved in Global Dimension Minimization, including an exciting new (and flexible) technique for estimating the dimension of an arbitrary data set. We will tour the Global Dimension Minimization Algorithm and see state-of-the-art results in a real-world application.

A Nonconforming Finite Element Method for an Acoustic
Jintao Cui (IMA)
Tuesday, April 10, 2012, Lind Hall 305, 3:00-4:00

In this talk we discuss a nonconforming finite element approximation of the vibration modes of an acoustic fluid-structure interaction. Displacement variables are used for both the fluid and the solid. The numerical scheme is based on the irrotational fluid displacement formulation; hence it is free of spurious eigenmodes. The method uses weakly continuous P₁ vector fields for the fluid and classical piecewise linear elements for the solid; and it satisfies optimal order error estimates on properly graded meshes. The theoretical results are confirmed by numerical experiments.

This is joint work with Susanne Brenner, Aycil Cesmelioglu and Li-yeng Sung.

Asymptotic probabilities and importance sampling for Langevin processes
David Aristoff (University of Minnesota)
Tuesday, April 17, 2012, Lind Hall 305, 3:00-4:00

It is well known that standard Monte Carlo estimates of small probabilities are unreliable in the sense that under fixed computational effort, the relative error (i.e., the sample standard deviation divided by the sample average) is expected to become unbounded as the probability being estimated approaches zero. We consider the problem of estimating small probabilities of the Langevin stochastic differential equation in various asymptotic regimes. As an example, we consider the probability of exiting a deep potential well.

Non-overlapping Clusters for Generalized Inference Over Graphical Models
Divianshu Vats (IMA)
Tuesday, May 1, 2012, Lind Hall 305, 3:00-4:00

Graphical models use graphs to compactly capture stochastic dependencies amongst a collection of random variables. Inference over graphical models corresponds to finding marginal probability distributions given joint probability distributions. In general, this is computationally intractable, which has led to a quest for finding efficient approximate inference algorithms. We propose a framework for generalized inference over graphical models that can be used as a wrapper for improving the estimates of approximate inference algorithms. Instead of applying an inference algorithm to the original graph, we apply the inference algorithm to a block-graph, defined as a graph in which the nodes are non-overlapping clusters of nodes from the original graph. This results in marginal estimates of a cluster of nodes, which we further marginalize to get the marginal estimates of each node. Our proposed block-graph construction algorithm is simple, efficient, and motivated by the observation that approximate inference is more accurate on graphs with longer cycles. We present extensive numerical simulations that illustrate our block-graph framework with a variety of inference algorithms (e.g., those in the libDAI software package). These simulations show the improvements provided by our framework. More details

Robust Locally Linear Analysis with Applications to Image Denoising and Blind Inpainting
Yi Grace Wang (University of Minesota)
Wednesday, May 16, 2012, Lind Hall 305, 3:00-4:00

I will talk about the problems of denoising images corrupted by impulsive noise and blind inpainting (i.e., inpainting when the deteriorated region is unknown). Our basic approach is to model the set of patches of pixels in an image as a union of low-dimensional subspaces, corrupted by sparse but perhaps large magnitude noise. For this purpose, we develop a robust and iterative method for single subspace modeling and extend it to an iterative algorithm for modeling multiple subspaces. I will also cover the convergence for the algorithm and demonstrate state of the art performance of our method for both imaging problems.

Robust Convex Relaxation for the Clique and Densest K-subgraph Problems
Brendan Ames (IMA postdoc)
Tuesday, May 22, 2012, Lind Hall 305, 3:00-4:00

Finding a densely connected subset of nodes in a graph is a fundamental problem in combinatorial optimization, with many practical applications. We consider the problem and of identifying the most densely connected set of k nodes of a given graph. This problem is known to be NP-hard. We propose a new convex relaxation of this problem using principal component pursuit. In the special case that the input graph contains a single dense subgraph plus noise in the form of edge additions and deletions, this relaxation is exact: the densest k-subgraph can be recovered directly from the unique optimal solution of this tractable relaxation. We provide two analyses of when the algorithm succeeds. In the first, the diversionary edges are added or deleted deterministically by an adversary. In the second, edges are placed or removed independently at random. These results can be thought of generalizations of existing recovery guarantees for the maximum clique problem. In both cases, the bounds ensuring perfect recovery match the best existing in the literature for the maximum clique problem.

Robust subspace recovery by geodesically convex optimization
Teng Zhang (IMA postdoc)
Thursday, June 28, 2012, Lind Hall 325, 1:00-2:00

We introduce Tyler's M-estimator to robustly recover the underlying linear model from a data set contaminated by outliers. We prove that the objective function of this estimator is geodesically convex on the manifold of all positive definite matrices and have a unique minimizer. Besides, we prove that when inliers (i.e., points that are not outliers) are sampled from a subspace and the percentage of outliers is bounded by some number, then under some very weak assumptions a commonly used algorithm of this estimator can recover the underlying subspace exactly. We also show that empirically this algorithm compares favorably with other convex algorithms of subspace recovery.

Finding overlapping communities in social networks
Brendan Ames (IMA postdoc)
Thursday, July 5, 2012, Lind Hall 305, 1:00-2:00

Identifying communities of densely connected nodes in a network is an important problem in the analysis of social and biological networks. These communities may overlap in many practical applications. For example, an individual may belong to many demographic groups within a social network or a particular gene may serve several biological functions within a gene-gene interaction network. However, most popular heuristics for community identification implicitly exploit the assumption that the underlying communities do not intersect.

I will present the recent paper “Finding Overlapping Communities in Social Networks: Toward a Rigorous Approach” by Arora et al. In this work, Arora et al. propose a quasipolynomial time algorithm for recovering the underlying community structure of networks satisfying particular assumptions. I will also discuss ongoing research by myself on this subject. In particular, I will discuss how a combination of Arora’s algorithm and standard clustering and graph partitioning techniques might lead to a polynomial time algorithm for networks sampled from a particular generative model.

Undirected Graphical Model Selection Using Junction Trees: Decompositions and Active Learning
Divyanshu Vats (IMA postdoc)
Thursday, July 26, 2012, Lind Hall 305, 1:00-2:00

An undirected graphical model is a joint probability distribution defined on an undirected graph $G = (V,E)$, where the nodes in the graph index a collection of random variables and the edges encode conditional independence relationships amongst random variables. The undirected graphical model selection (UGMS) problem is to estimate the graph $G$ given observations drawn from the undirected graphical model. This paper proposes a framework for decomposing the UGMS problem into multiple subproblems over clusters and separators of a junction tree. Under certain conditions, we show that the junction tree framework significantly weakens the sufficient conditions on the number of observations required for high-dimensional consistent graph estimation. When the conditions on the graphical model do not hold, we recover the standard conditions for high-dimensional consistency. This motivates the use of our framework as a wrapper around algorithms for more accurate graph estimation. Further, we show that the subproblems over the clusters and separators can be solved independently, which allows for using different regularization parameters or different UGMS algorithms to learn different parts of the graph. Finally, the junction tree framework motivates active learning for UGMS that sequentially draws observations from the graphical model based on prior observations. In the high-dimensional setting, we identify conditions under which the sufficient conditions on the number of scalar observations needed for an active algorithm is significantly less than that needed for a non-active algorithm. Intuitively, the active learning algorithm draws more observations from parts of the graph that are difficult to learn and less measurements from parts of the graph that are easy to learn. Our numerical results clearly identify the advantages of using the junction tree framework for both non-active and active learning for UGMS. This is joint work with Prof. Robert Nowak.

Percolation of Hard Disks
David Aristoff (University of Minnesota)
Thursday, August 2, 2012, Lind Hall 409, 1:00-2:00

Consider the set X of all possible arrangements of nonoverlapping disks of radius r in the plane. There is a probability measure mu_d on X which assigns equal probabilistic weight to all arrangements of the same density d. What are the qualitative properties of typical samples from mu_d when d is large? One might expect that for density d near maximum, a typical sample is a perturbation of a perfect crystalline arrangement. This turns out not to be the case (T. Richthammer, 2006). We ask a simpler question: Can one expect to see an infinite connected cluster of disks, where pairs of disks are connected if they are within distance epsilon? We give a positive response to the question in the case where epsilon > r. In particular this implies percolation of excluded volume, which has been heuristically connected to the liquid-gas phase transition in statistical mechanics (KW Kratky, 1988). The proof extends to 3 dimensions.

TBD
Gilad Lerman (University of Minnesota)
Thursday, August 9, 2012, Lind Hall 305, 1:00-2:00






The Fall semester postdoc seminar was organized by Yulia Hristova
It took place 11:15-12:15 Tuesdays in Lind Hall 305, except during IMA workshop weeks and as otherwised noted

Alternating Direction Methods for Sparse and Low-Rank Optimization
Shiqian Ma (IMA postdoc)
September 20, 2011, Lind Hall 305, 11:15-12:15

In this talk, we show how alternating direction methods are used recently in sparse and low-rank optimization problems. We also show the iteration complexity bounds for two specific types of alternating direction methods, namely alternating linearizaton and multiple splitting methods. We prove that the basic versions of both methods require $O(1/eps)$ iterations to obtain an eps-optimal solution, and the accelerated versions of these methods require $O(1/\sqrt{eps})$ iterations, while the computational effort needed at each iteration is almost unchanged. To the best of our knowledge, these complexity results are the first ones of this type that have been given for splitting and alternating direction type methods. Numerical results on problems with millions of variables and constraints arising from computer vision, machine learning and image processing are reported to demonstrate the efficiency of the proposed methods.

On the Group Isomorphism Problem
Paolo Codenotti, (IMA postdoc)
October 4, 2011, Keller Hall 3-180, 11:15-12:15

We consider the problem of testing isomorphism of groups of order n given by Cayley tables. The $n^{\log n}$ bound on the time complexity for the general case has not been improved over the past four decades. We demonstrate that the obstacle to efficient algorithms is the presence of abelian normal subgroups; we show this by giving a polynomial-time isomomrphism test for "semisimple groups,'' defined as groups without abelian normal subgroups (joint work L. Babai, Y. Qiao, in preparation). This concludes a project started with with L. Babai, J. A. Grochow, Y. Qiao (SODA 2011). That paper gave an $n^{\log\log n}$ algorithm for this class, and gave polynomial-time algorithms assuming boundedness of certain parameters. The key ingredients for this algorithm are: (a) an algorithm to test permutational isomorphism of permutation groups in time polynomial in the order and simply exponential in the degree; (b) the introduction of the "twisted code equivalence problem," a generalization of the classical code equivalence problem (which asks whether two sets of strings over a finite alphabet are equivalent by permuting the coordinates), by admitting a group action on the alphabet; (c) an algorithm to test twisted code equivalence; (d) a reduction of semisimple group isomorphism to permutational isomorphism of transitive permutation groups under the given time limits via twisted code equivalence.

The twisted code equivalence problem and the problem of permutational isomorphism of permutation groups are of interest in their own right. In this talk I will give the definitions of the problems that make up the overall plan, show how they fit together, and then give some details on the algorithm to test permutational isomorphism of transitive groups.

This talk is based on joint work with: Laszlo Babai (University of Chicago), Joshua A. Grochow (University of Chicago) and Youming Qiao (Tsingua University).

Geometry of maximum likelihood estimation in Gaussian graphical models
Caroline Uhler (IMA postdoc)
October 11, 2011, Keller Hall 3-180, 11:15-12:15

We study maximum likelihood estimation in Gaussian graphical models from a geometric point of view. In current applications of statistics, we are often faced with problems involving a large number of random variables, but only a small number of observations. An algebraic elimination criterion allows us to ?nd exact lower bounds on the number of observations needed to ensure that the maximum likelihood estimator exists with probability one. This is applied to bipartite graphs and grids, leading to the ?rst instance of a graph for which the maximum likelihood estimator exists with probability one even when the number of observations equals the treewidth of the graph.

Necessary Conditions for Set-Based Graphical Model Selection
Divyanshu Vats (IMA postdoc)
October 18, 2011, Keller Hall 3-180, 11:15-12:15

Graphical model selection, where the goal is to estimate the graph underlying a distribution, is known to be computationally intractable in general. An important issue is to study theoretical limits on the performance of graphical model selection algorithms. In particular, given parameters of the underlying distribution, we want to find a lower bound on the number of samples required for accurate graph estimation. When deriving these theoretical bounds, it is common to treat the learning problem as a communication problem where the observations correspond to noisy messages and the decoding problem infers the graph from the observations. Current analysis of graphical model selection algorithms is limited to studying graph estimators that output a unique graph. In this paper, we consider graph estimators that output a set of graphs, leading to set-based graphical model selection (SB-GMS). This has connections to list-decoding where a decoder outputs a list of possible codewords instead of a single codeword. Our main contribution is to derive necessary conditions for accurate SB-GMS for various classes of graphical models and show reduction in the number of samples required for consistent estimation. Further, we derive necessary conditions on the cardinality of the set-based estimates given graph parameters.

Regularization Methods for Probabilistic Optimization
Gabriela Martinez (IMA postdoc)
November 1, 2011, Keller Hall 3-180, 11:15-12:15

We analyze nonlinear stochastic optimization problems with joint probabilistic constraints using the concept of a $p$-efficient point of a probability distribution. If the problem is described by convex functions, we develop two algorithms based on first order optimality conditions and a dual approach to the problem. The algorithms yield an optimal solution for problems involving $\alpha$-concave probability distributions. For arbitrary distributions, the algorithms provide upper and lower bounds for the optimal value and nearly optimal solutions. When the problem is described by continuously differentiable non-convex functions, we describe the tangent and the normal cone to the level set of the underlying probability function. Furthermore, we formulate first order and second order conditions of optimality based on the notion of $p$-efficient points. For the case of discrete distribution functions, we developed an augmented Lagrangian method based on progressive inner approximation of the level set of the probability function by generation of $p$-efficient points. Numerical experience is provided.

Exact semidefinite relaxation for the clustering and biclustering problems
Brendan Ames (IMA postdoc)
November 8, 2011, Keller Hall 3-180, 11:15-12:15

Identifying clusters of similar objects in data plays a significant role in a wide range of applications such as information retrieval, pattern recognition, computational biology, and image processing. We consider as a model problem for clustering the average weight k-disjoint clique problem (WKDC), whose goal is to identify the collection of k disjoint cliques of a given weighted complete graph maximizing the sum of the average edge weights over the complete subgraphs induced by these cliques. We show that this problem can be formulated as a nonconvex quadratic maximization problem and subsequently relaxed to a semidefinite program using symmetric matrix lifting. Although the WKDC problem is NP-hard, we show that this relaxation is exact under certain assumptions on the input graph. That is, the optimal solution for the original hard combinatorial problem can be recovered directly from the solution of the relaxed problem for certain program inputs. In particular, the semidefinite relaxation is exact for input graphs corresponding to data consisting of k large, distinct clusters and a small number of outliers.

This approach also yields a semidefinite relaxation for the biclustering problem with similar recovery guarantees. Given a set of objects and a set of features exhibited by these objects, biclustering seeks to simultaneously group the objects and features according to their expression levels. We pose this problem as partitioning of a weighted complete bipartite graph such that the edge weight within the resulting bicliques is maximized. As in our analysis of the WKDC problem, we consider a nonconvex quadratic programming formulation for this problem, and relax to semidefinite programming using matrix lifting. As before, we show that the correct partition of the objects and features can be recovered from the optimal solution of the semidefinite relaxation, in the case that the input instance consists of several disjoint sets of objects exhibiting similar features.

Diffusion Approximations for Multiscale Stochastic Networks in Heavy traffic
Xin Liu (IMA postdoc)
November 22, 2011, Keller Hall 3-180, 11:15-12:15

We study a sequence of nearly critically loaded queueing networks, with time varying arrival and service rates and routing structure. The n^th network is described in terms of two independent finite state Markov processes {Xⁿ(t): t = 0} and {Yⁿ(t) : t = 0} which can be interpreted as the random environment in which the system is operating. The process Xⁿ changes states at a much higher rate than the typical arrival and service times in the system, while the reverse is true for Yⁿ. The variations in the routing mechanism of the network are governed by Xⁿ, whereas the arrival and service rates at various stations depend on the state process (i.e. queue length process) and both Xⁿ and Yⁿ. Denoting by Zⁿ the suitably normalized queue length process, it is shown that, under appropriate heavy traffic conditions, the pair Markov process (Zⁿ, Yⁿ) converges weakly to the Markov process (Z, Y), where Y is a finite state continuous time Markov process and the process Z is a reflected diffusion with drift and diffusion coefficients depending on (Z, Y) and the stationary distribution of Xⁿ. We also study stability properties of the limit process (Z, Y).

A novel M-estimator for robust PCA
Teng Zhang (IMA postdoc)
November 29, 2011, Lind Hall 305, 11:15-12:15

We formulate a convex minimization to robustly recover a subspace from a contaminated data set, partially sampled around it, and propose a fast iterative algorithm to achieve the corresponding minimum. We establish exact recovery by this minimizer, quantify the effect of noise and regularization, explain how to take advantage of a known intrinsic dimension and establish linear convergence of the iterative algorithm. We compare our method with many other algorithms for Robust PCA on synthetic and real data sets and demonstrate state-of-the-art speed and accuracy.

Sparse coding and object recognition
Arthur Szlam (IMA postdoc)
December 6, 2011, Lind Hall 305, 11:15-12:15

I will review a standard object recognition architecture, and discuss each of the components: SIFT features, sparse coding, pooling, and linear classifiers. I will then mention recent work of myself and collaborators on a fast version of this machine.

Derivatives of eigenvalue functions
Brendan Ames (IMA postdoc)
December 13, 2011, Lind Hall 401, 11:15-12:15

The eigenvalues of a symmetric operator play a significant role in many areas of mathematics and engineering. As such, it is important to understand the behaviour of the spectrum of a matrix under small perturbations. This talk is divided into two parts. In the first, I will review several important results from the literature regarding the sensitivity of the eigenvalues of a symmetric matrix. In particular, I will provide formulas for the directional derivatives of the spectrum of a symmetric matrix, and discuss how these formulas can be extended to obtain a series approximation of the spectrum of a symmetric matrix under small perturbations. The second half of the talk will focus on the sensitivity of functions of the spectrum of a symmetric matrix. If F(X) is a function that depends smoothly on the eigenvalues of X, I will provide conditions for when this smoothness is inherited by F. As examples, I will provide conditions for differentiability of spectral functions and primary matrix functions, as well as formulas for their gradients.

The IMA Postdoc Seminar met at 11:15-12:15 every Tuesday during the semester in Lind Hall 305, except during IMA workshop weeks. The Fall semester postdoc seminar was organized by Ortiz-Duenas and Dimitar Trenev was the organizer for the Winter and Spring semesters postdoc seminars.

September 21, 2010 Randall J. Leveque (Founders Term Professor of Applied Mathematics and Adjunct Professor of Mathematics, University of Washington, Seattle) The GeoClaw software for tsunamis and other hazardous flows Abstract: Many geophysical flows over topography can be modeled by two-dimensional depth-averaged fluid dynamics equations. The shallow water equations are the simplest example of this type, though it is often necessary to incorporate non-hydrostatic pressures, more complicated rheologies (e.g. for avalanches, landslides, or debris flows), or to use multi-layer models, e.g. for capturing internal waves or to model a landslide-induced tsunamis. These equations are generally hyperbolic and can be modeled using high-resolution finite volume methods designed for such problems. However, several features of these flows lead to new algorithmic challenges, such as the fact that the depth goes to zero at the edge of the flow and that vastly differing spatial scales must often be modeled, making adaptive mesh refinement essential. I will discuss some of these algorithms and the GeoClaw software, a specialized version of Clawpack that is aimed at solving real-world geophysical flow problems over topography. In particular I will show results from some recent tsunamis and potential future events. For information about the software, see www.clawpack.org/geoclaw.

September 28, 2010 Yulia Hristova (1st year Postdoc) On detection of low emission sources in the presence of a large random background Abstract: One of the missions of the Department of Homeland Security is to prevent smuggling of weapon-grade nuclear materials. It is expected that such materials, unlike those needed for a "dirty bomb," will have low emission rates and will be well shielded, so that very few gamma photons or neutrons could escape, and even less would be detected. An additional hurdle for the detection of illicit nuclear substances is the strong natural radiation background. In this talk I will discuss when detection of such sources is feasible and how Compton camera type detectors could be used for this purpose.

October 5, 2010 Jintao Cui (1st year Postdoc) Multigrid methods for Maxwell’s equations Abstract: In this work we study finite element methods for two-dimensional Maxwell’s equations and their solutions by multigrid algorithms. We first introduce two types of nonconforming finite element methods on graded meshes for a two-dimensional curl-curl and grad-div (CCGD) problem that appears in electromagnetics. The first method is based on a discretization using weakly continuous P1 vector fields. The second method uses discontinuous P1 vector fields. Optimal convergence rates in the energy norm and the L2 norm are established for both methods on graded meshes. Then we consider a class of symmetric discontinuous Galerkin methods for a model Poisson problem on graded meshes that share many techniques with the nonconforming methods for the CCGD problem. We establish the uniform convergence of W-cycle, V-cycle and F-cycle multigrid algorithms for the resulting discrete problems. Finally, we propose a new numerical approach for two-dimensional Maxwell’s equations that is based on the Hodge decomposition for divergence-free vector fields, and present multigrid results.

October 12, 2010 Petr Plechac (University of Delaware) Hierarchical approximations, coarse-graining and fast lattice Monte Carlo simulations Abstract: We shall discuss numerical analysis aspects of coarse-graining stochastic particle systems and the connection to acceleration of kinetic Monte Carlo simulations. Mathematical tools developed for error control in microscopic simulations using the coarse-grained stochastic processes and reconstruction of microscopic scales will be presented in connection with accelerating (kinetic) Monte Carlo simulations. On specific examples of lattice as well as off-lattice dynamics we demonstrate that computational implementation of constructed hierarchical algorithms results in significant speed up of simulations. The developed framework also leads to new parallel kinetic Monte Carlo algorithms that will be briefly described.

October 26, 2010 Oscar E. Fernandez (1st year Postdoc) Simulating nonholonomic mechanics using variational integrators through Hamiltonization Abstract: Although it is well known that nonholonomic mechanical systems are not Hamiltonian, recent research has uncovered a variety of techniques which allow one to express the reduced, constrained dynamics of certain classes of nonholonomic systems as Hamiltonian. In this talk I will discuss the application of these methods to develop alternative geometric integrators for nonholonomic systems with perhaps more eacuteciency than the known nonholonomic integrators. After showing how variational integrators theoretically preserve conserved mechanical quantities (such as momentum and energy), I will discuss how Hamiltonization can be used to apply these variational integrators to certain classes of nonholonomic systems. Finally, I will discuss some current research utilizing time reparameterizations.

November 9, 2010 Niall Madden (School of Mathematics, Statistics and Applied Mathematics, National University of Ireland, Galway, Ireland) Robust numerical solution of singularly perturbed problems Abstract: Singularly perturbed differential equations are usually posed with a small positive (perturbation) parameter multiplying the highest derivative. Their solutions typically exhibit boundary or interior layers. In recent years much effort has been directed towards constructing and analysing so-called "parameter robust" methods. Such methods should yield solutions whose accuracy does not depend on the perturbation parameter, and should resolve any layers present. In this talk I will survey some of these methods, and the mathematics behind them, with particular emphasis on finite differences for coupled systems.

November 16, 2010 Blanca Ayuso de Dios (Centre de Recerca Matemàtica) Discontinuous Galerkin approximation for the Vlasov-Poisson system Abstract: One of the simplest model problems in the kinetic theory of plasma--physics is the Vlasov-Poisson (VP) system with periodic boundary conditions. Such system describes the evolution of a plasma of charged particles (electrons and ions) under the effects of the transport and self-consistent electric field. In this talk, we construct a new family of semi-discrete numerical schemes for the approximation of the Vlasov-Poisson system. The methods are based on the coupling of discontinuous Galerkin (DG) approximation to the Vlasov equation and several finite element (conforming, non-conforming and mixed) approximations for the Poisson problem. We present the error analysis in the case of smooth solutions. The issue of energy conservation is also analyzed for some of the methods. If time allows, I will also comment on the issue of approximating non-smooth solutions of the VP system. The talk is based on joint works with J.A. Carrillo (Universidad Autonoma de Barcelona) and C-W. Shu (Brown University).

November 23, 2010 Sylvain Nintcheu Fata (Oak Ridge National Laboratory) The Poincaré lemma and the computation of domain integrals in BEM Abstract: An effective technique to evaluate domain integrals appearing in a boundary element method (BEM) has been developed [1]. The proposed approach first converts a domain integral with continuous or weakly-singular integrand into an equivalent boundary integral. The resulting surface integral is then calculated via standard quadrature rules commonly used for boundary elements. This transformation of a domain integral into a boundary counterpart is accomplished through a systematic and rigorous generalization of the fundamental theorem of calculus to higher dimension. Moreover, it is shown that the higher-dimensional version of the first fundamental theorem of calculus corresponds to the classical Poincaré lemma. Employed together with the singular treatment of surface integrals that is well established in the literature [2, 3, 4], the proposed method can be utilized to ectively solve boundary-value problems involving non-homogeneous source terms by way of a collocation or a Galerkin BEM without partitioning the problem domain into volume cells. Several key features of this study, including the extension of the fundamental theorem of calculus to higher dimension, are highlighted. In addition, numerical examples dealing with mixed boundary-value problems for the Poisson equation on representative test geometries are carried out successfully to validate the proposed method. References: [1] S. Nintcheu Fata, Treatment of domain integrals in boundary element methods, Appl. Numer. Math., doi:10.1016/j.apnum.2010.07.003, 2010. [2] S. Nintcheu Fata, Explicit expressions for 3D boundary integrals in potential theory, Int. J. Num. Meth. Eng., 78(1), pp. 32—47, 2009. [3] S. Nintcheu Fata, L. J. Gray, Semi-analytic integration of hypersingular Galerkin BIEs for three-dimensional potential problems, J. Comput. Appl. Math., 231(2), pp. 561—576, 2009. [4] S. Nintcheu Fata, Semi-analytic treatment of nearly-singular Galerkin surface integrals, Appl. Numer. Math., 60(10), pp. 974—993, 2010. This research was supported by the Office of Advanced Scientific Computing Research, U.S. Department of Energy, under contract DE-AC05-00OR22725 with UT-Battelle, LLC.

December 7, 2010 Guido Kanschat (Department of Mathematics, Texas A & M University) http://www.math.tamu.edu/~kanschat Discontinuous Galerkin methods for radiative transfer: Some old results and some new results Abstract: In the 1970s, discontinuous Galerkin (DG) methods were invented as a means to solve neutron/radiation transport problems. Their convergence analysis had been developed by the early 1980s. Between 1989 and 2000 several publications in nuclear engineering suggested, that the method does not converge in scattering dominated regimes. In this presentation, we will review these seemingly contradicting results. A first robustness result requires that the DG finite element space contains an approximating continuous space. Since this result is not sufficient for applications, we use the information contained in the analysis to devise a new DG method, which will converge to the correct solution independent of the model parameters.

January 25, 2011 Pawel Konieczny (2nd year Postdoc) http://www.ima.umn.edu/~konieczny/ On dispersive effect of the Coriolis force for the stationary Navier-Stokes equations Abstract: The dispersive effect of the Coriolis force for the stationary and nonstationary Navier-Stokes equations is investigated. Existence of a unique stationary solution is shown for arbitrary large external force provided the Coriolis force is large enough. In addition to the stationary case, counterparts of several classical results for the non-stationary Navier-Stokes problem have been proven. The analysis is carried out in a new framework of the Fourier-Besov spaces.

February 1, 2011 Aycil Cesmelioglu (1st year Postdoc) http://www.ima.umn.edu/~cesma001/ On the coupling of surface/subsurface flow with transport Abstract: The coupling of porous media flow with free flow arises in many applications an example of which is groundwater contamination through rivers. The free flow is characterized by the Navier-Stokes equations whereas the porous media flow is described by the Darcy equations. Beavers-Joseph-Saffman interface condition is prescribed at the interface separating two regions. A transport equation for the contaminant concentration is fully coupled to the flow problem via the velocity field and the viscosity. First, we discuss the existence result to the related weak formulation of the full coupling problem. Second, we analyze numerical schemes based on classical finite element methods and discontinuous Galerkin methods for the special case where the coupling is only one-way, that is, the velocity field from the Navier-Stokes/Darcy problem is an input for the transport equation. Numerical solutions for non homogeneous porous media are also presented.

February 15, 2011 Hengguang Li (1st year Postdoc) http://www.ima.umn.edu/~li_h/ FEMs and MG methods for axisymmetric problems Abstract: We shall discuss finite element and multigrid techniques solving the axisymmetric Poisson's equation and the azimuthal Stokes problem on polygonal domains with possible singular solutions. In particular, we construct stable interpolation operators and establish the well-posedness and regularity in some weighted Sobolev space, which in turn, leads to special finite element spaces to approximate the solutions in the optimal rate. With a careful formulation, we also obtain uniform convergence of the MG methods. These estimates can also be used to show the stability of the Taylor-Hood elements for the axisymmetric Stokes problem and to precondition the indefinite system from the axisymmetric Stokes equations.

February 22, 2011 Weifeng (Frederick) Qiu (1st year Postdoc) http://www.ima.umn.edu/~qiuxa001/ An hp DPG method for linear elasticity with symmetric stresses    Joint work with Jamie Bramwell 3, Leszek Demkowicz 2, and Jay Gopalakrishnan 1. Abstract: In this research, we present two Discontinuous Petrov-Galerkin (DPG) finite element methods for linear elasticity. For the first method, we consider asymmetric test tensors for the constitutive equation and compute infinitessimal rotations, while in the second method we only use symmetric test tensors and therefore have fewer unknowns. We define optimal test functions which are shown to deliver the best approximation error if an optimal global test norm is used. To make the method practical, we show a localizable test norm is equivalent to the global optimal norm. The majority of this proof is the verification that the inf-sup condition holds for our DPG formulations using the localizable test space norm. From DPG theory, this proves our methods are quasi-optimal with constants independent of the mesh. We can then use results from approximation theory to show h and p convergence for both methods. Since the quasi-optimal test space norm is localizable, we have implemented practical finite element codes that show h and p convergence of both methods at optimal rates. Additionally, the DPG framework provides an a priori error estimator determined by a local auxilliary variational problems. We use this estimator as the basis for various 'greedy' adaptive schemes. We test our adaptive algorithm using a manufactured smooth solution as well as a singular solution L-shape domain problem and observe adaptive h and hp convergence. The principal contributions of this research are proving p convergence for the dual-mixed elasticity system, particularly without the need for a discrete exact sequence or commuting diagram, as well as a practical adaptive 2D elasticity code with a priori error estimation. We will present an overview of the theoretical DPG framework, the convergence proofs for both methods, and the numerical results for both a singular and smooth solution. References J. Bramwell, L. Demkowicz, and W. Qiu. Solution of Dual-Mixed Elasticity Equations using Arnold-Falk-Winther Element and Discontinuous Petrov-Galerkin Method, a Comparison. Technical Report 10-23, The Institute for Computational Engineering and Sciences, The University of Texas at Austin, June 2010. J. Bramwell, L. Demkowicz, J. Gopalakrishnan, and W. Qiu. An hp DPG Method for Linear Elasticity with Symmetric Stresses, in preparation. 1 Professor, Mathematics, University of Florida 2 Professor, Institute for Computational Engineering and Sciences, 3 Graduate Research Assistant, Institute for Computational Engineering and Sciences, University of Texas at Austin

March 22, 2011 David Yu Mao (1st year Postdoc) http://davidmao.net/ Reconstruction of binary functions and shapes from incomplete frequency information Abstract: Binary functions are a class of important functions that appears in many applications, e.g. image segmentation, bar code recognition, shape detection and so on. In this research we proved that under certain conditions the binary function can be reconstructed from very limited frequency information by using only simple linear programming. Numerical results and applications will be discussed.

March 29, 2011 Dimitrios Mitsotakis (1st year Postdoc) On the use of the finite-fault solution for tsunami generation problems Abstract: We present a new approach to describe accurately the generation of a tsunami wave due to an underwater earthquake. The main goal of this work is two-fold. First of all, we propose a simple and computationally inexpensive model for the description of the sea bed displacement during an underwater earthquake, based on the finite fault solution for the slip distribution under some assumptions on the dynamics of the rupturing process. Once the bottom motion is reconstructed, we study waves induced on the free surface of the ocean. For this purpose we consider three different models approximating the Euler equations of the water wave theory. Namely, we use the linearized Euler equations (we are in fact solving the Cauchy-Poisson problem), a Boussinesq system and a novel weakly nonlinear model. An intercomparison of these approaches is performed. The developments of the present study are illustrated on the July 27, 2006 Java event, where an underwater earthquake of magnitude 7.7 generated a tsunami that inundated the southern coast of Java.

April 5, 2011 Luis Tenorio (Colorado School of Mines) Data Analysis and Uncertainty Quantification of Inverse Problems Abstract: We present exploratory data analysis methods to assess inversion estimates using simple examples based on classic l2- and l1-regularization. These methods can be used to reveal the presence of systematic errors such as bias and discretization effects, or to validate assumptions made on the statistical model used in the analysis. The methods include: bound for randomized trace estimators, confidence intervals and bounds for the bias, resampling methods for model validation, and construction of training sets of functions with controlled local regularity.

April 26, 2011 Maria Pia Gualdani (Department of Mathematics, The University of Texas at Austin) http://www.ma.utexas.edu/users/gualdani/ A factorization method for non-symmetric linear operator: enlargement of the functional space while preserving hypo-coercivity Abstract: We present a factorization method for non-symmetric linear operators: the method allows to enlarge functional spaces while preserving spectral properties for the considered operators. In particular, spectral gap and related convergence towards equilibrium follow easily by hypo-coercivity and resolvent estimates. Applications of this theory on several kinetic equations will be presented.

May 10, 2011, Tuesday Dr. Tom Duchamp (University of Washington) Smoothness of Nonlinear Subdivision Curves Abstract: Subdivision Curves were discovered by Georges de Rham in 1947. He noticed that the sequence of polygonal lines obtained by a "corner cutting" (or "subdivision") process converges to a C1 curve. B-splines are obtained by a generalization of this procedure, which depends on the affine structure of Euclidean space. A "linear subdivision curve" is the limiting curve obtained by such a linear subdivision process. The theory of such curves, is well-understood. Because subdivision curves also support multiresolution structure, various wavelet based compression algorithms apply to them. Consequently, subdivision curves offer a way to compress data related to curves in Euclidean space. But not all data live in Euclidean space (rotations, rigid motions, deformation tensors are examples), and the quantity of such data is proliferating. In "Multiscale representations of manifold-valued data", Rahman, Rori, Stodden, Donoho, and Schroder, therefore, considered manifold-valued subdivision curves, and their multiresolution structure. These curves are all based on corresponding linear subdivision curves, and Rahman-et-al. conjectured that they enjoy the same regularity properties. In my talk, I will review linear subdivision curves, explain the generalization to manifold-valued curves, and close with some surprising results concerning their regularity properties. The talk is based on joint work with Gang Xie and Thomas Yu.

May 24, 2011, Thursday Dr. Jay Gopalakrishnan (University of Florida) An introduction to DPG methods Abstract: We will discuss a new class of discontinuous Petrov-Galerkin (DPG) methods that achieves stability by automatically finding stable pairs of trial and test spaces in a Petrov-Galerkin framework. The key is that the use of discontinuous finite element spaces (as in DG methods) allows local computation of the test spaces that guarantee stability. (This is joint work with L. Demkowicz.)