Applied Math Seminar

Central Schemes: a Powerful Black-Box-Solver for Nonlinear Hyperbolic PDEs

10/23/2013 - 1:15pm
10/23/2013 - 2:15pm
Alexander Kurganov (Tulane University)

I will first give a brief description of finite-volume, Godunov-type methods for hyperbolic
systems of conservation laws. These methods consist of two types of schemes: upwind and
central. My lecture will focus on the second type -- non-oscillatory central schemes.

Godunov-type schemes are projection-evolution methods. In these methods, the solution, at
each time step, is interpolated by a (discontinuous) piecewise polynomial interpolant, which
is then evolved to the next time level using the integral form of conservation laws. Therefore,
in order to design an upwind scheme, (generalized) Riemann problems have to be
(approximately) solved at each cell interface. This however may be hard or even impossible.

The main idea in the derivation of central schemes is to avoid solving Riemann problems by
averaging over the wave fans generated at cell interfaces. This strategy leads to a family of
universal numerical methods that can be applied as a black-box-solver to a wide variety of
hyperbolic PDEs and related problems. At the same time, central schemes suffer from
(relatively) high numerical viscosity, which can be reduced by incorporating of some
upwinding information into the scheme derivation -- this leads to central-upwind schemes,
which will be presented in the lecture.

During the talk, I will show a number of recent applications of the central schemes.

Davidson, CMC

Getting a Grip on Network Delays

12/04/2013 - 1:15pm
12/04/2013 - 2:15pm
Almut Burchard (University of Toronto)

Delay analysis in packet networks is notoriously hard. Statistical properties of traffic, link scheduling, and subtle correlations between traffic at different nodes increase the difficulty of characterizing the variable portion of delays. Historically, performance analysis has relied on two fundamentally different tools: Classical queuing theory (to predict delay distributions in a network where nodes operate independently and time correlations can be neglected), and worst-case analysis (to understand complex scheduling algorithms in smaller networks). Beyond that, asymptotic methods have been used to determine stability regions and exponential decay rates.

In this talk, I will discuss recent progress on the end-to-end delay analysis for a traffic flow in a packet network, using a stochastic network calculus approach that has been developed over the last twenty years. I will consider the following questions: What is the relative impact of scheduling and statistical multiplexing on delays at a packet switch? How do end-to-end delays scale as the number of traversed nodes is increased? What do self-similar and heavy-tailed traffic arrival processes contribute to the delay? (Joint work with J. Liebeherr and his group.)

Davidson Lecture Hall

K-mappings and regression trees

11/20/2013 - 1:15pm
11/20/2013 - 2:15pm
Yi Grace Wang (Duke University)

I will describe a method for learning a piecewise affine approximation to a mapping f : R^d → R^p given a labeled training set of examples {x1, ..., xn} = X \subset R^d and targets {y1 = f(x1), ..., yn = f(xn)} = Y \subset R^p. The method first trains a binary subdivision tree that splits via hyperplanes in X corresponding to high variance directions in Y . A fixed number K of affine regressors of rank q are then trained via a K-means like iterative algorithm on the leaves of the tree. Expereiments are followed to evaluate its performance.

Davidson, CMC

Standard finite difference discretizations of the elliptic Monge-Ampere equation

11/13/2013 - 1:15pm
11/13/2013 - 2:15pm
Gerard Awanou (University of Illinois, Chicago)

Abstract: Given an orthogonal lattice with mesh length $ h $ on a bounded convex domain $ \Omega $, we show that the Aleksandrov solution of the Monge-Amp\`ere equation is the uniform limit on compact subsets of $ \Omega $ of mesh functions $ u_h $ which solve a discrete Monge-Amp\`ere equation with the Hessian discretized using the standard finite difference method. The result provides the mathematical foundation of methods based on the standard finite difference method and designed to numerically converge to non-smooth solutions. The numerical resolution of the Monge-Amp\`ere equation has become an active research field because of several applications of increasing importance e.g. optimal transport, reflector design etc.

CMC Davidson

Mathematical Models of Bacterial Track-Altering Motors

02/26/2014 - 1:15pm
02/26/2014 - 2:15pm
Blerta Shtylla (Pomona College)

The appropriate localization of proteins inside a cell is vital for the maintenance of cell function. Proteins can reach specific locations in a variety of ways, however directed movement frequently requires the rectification of Brownian motion. A exotic and rich variety of mechanisms can be used to generate directed movement, here we will focus on a bacterial track-altering motor complex that is employed to segregate replicated chromosome regions to specific locations in the cell. We develop and analyze various simplified mathematical models that examine how diffusion and ATP-hydrolysis mediated monomer removal can be combined to power directed movement. Using a mean first passage approach and stochastic simulations, we discuss how to calculate the effective track cleaving velocities and effective dispersion coefficient for the bacterial track-altering motor. We conclude by giving an overview of the biological implications of our model results.

CGU, Math South Conference Room, 710 N. College Ave

Domain decomposition method for image denosing and image deblurring

10/16/2013 - 1:15pm
10/16/2013 - 2:15pm
Xu Jing (Zhejiang Gongshang University, Currently she is visiting UCLA)


Image restoration has drawn much attention in recent years and a surge of research has been done on variational models and their numerical studies. However, there remains an urgent need to develop fast and robust methods for solving the minimization problems and the underlying nonlinear PDEs to process image of moderate to large size. We proposed a two –level domain decomposition method, which consists of an overlapping domain decomposition technique and a coarse mesh correction, for directly solving the total variational minimization problems. What’s more, the domain decomposition method hadn't been applied directly to image deblurring because of the global character of blur operator. In order to avoid separating the blur operator, we propose an algorithm for directly solving the total variational minimization problems with domain decomposition method. Various numerical experiments and comparisons demonstrate that the proposed method is efficient and fast particularly for images of large size.


Dr. Jing Xu is an associate professor in Zhejiang Gongshang University, Hangzhou, China. Now she is a visiting scholar of Professor Luminita Vese in mathematics in UCLA from July 1, 2013 to June 30, 2014. Her research major is the applications of partial differential equations to image processing. She got her PHD degree in applied mathematics institute of Chinese Academy Science, 2007. In that time, she studied the multigrid method in image restoration from Professor Qianshun Chang. Jing Xu has one year experience being a research fellow in Nanyang Technology University, Singapore from 2008 to 2009. During that time, she studied domain decomposition method from Professor Xuecheng Tai and lilian Wang.

CMC Campus, Adams Hall, Davidson (the largest lecture room on the first floor)

Faster approximation of high dimensional integrals with Monte Carlo

09/18/2013 - 1:15pm
09/18/2013 - 2:15pm
Mark Huber (CMC)

High dimensional integrals and sums arise often in applications coming from statistics, theoretical physics, and computer science.  Consider the problem of approximating these integrals to within a factor of $ 1 + \epsilon $ for some specified $ \epsilon > 0. $ when the integrand (or summand) is nonnegative..  Monte Carlo methods for approximating these integrals work by drawing samples randomly from a family of distributions formed from the nonnegative integrand.  Typically the value of these integrals is exponentially large in the problem input size, so let $ q $ denote the natural logarithm of the integral in question.  Previous Monte Carlo methods for such approximation used $ O(q \ln(q)^5) $ samples (suppressing the dependence on $ \epsilon $), but the big-O notation hid factors on the order of $ 10^{10} $..  In this work, a new method is presented that uses only $ O(q \ln(q) $ samples, with a factor of about 16.7.  As a bonus, this method is much simpler to implement then previous approaches.  This is the first practical method for creating provably good approximations for these problems.


CMC Campus, Adams Hall, Davidson (the largest lecture room on the first floor)

Learning Structured Dictionaries for Manifold-type Data based on a Geometric Multi-Resolution Analysis

09/04/2013 - 1:15pm
09/04/2013 - 2:15pm
Guangliang Chen (CMC)
Data sets are often modeled as samples from a probability distribution
in high dimensions, but assumed to have some interesting low-dimensional
structure, for example that of a $ d $-dimensional submanifold $ \mathcal{M} $ of $ \mathbb{R}^D $,
with $ d\ll D $. When $ \mathcal{M} $ is simply a linear subspace, one may encode
efficiently the data by projection onto a dictionary consisting of the
top $ d $ singular vectors, with a cost of $ d(N+D) $ (where $ N $ is the data size).
When $ \mathcal{M} $ is nonlinear, there are no "explicit" and fast constructions of
dictionaries that achieve a similar efficiency: typically one uses
either random dictionaries, or dictionaries obtained by black-box global
optimization. In this talk we present an efficient construction of
data-dependent dictionaries for manifold-type data based on a geometric
multiresolution analysis, aiming at efficiently encoding and
manipulating the data. We will also mention its application to anomaly detection.



CMC Campus, Adams Hall, Davidson (the largest lecture room on the first floor)

One-bit matrix completion

05/08/2013 - 1:15pm
05/08/2013 - 2:15pm
Mark A. Davenport (School of Electrical and Computer Engineering, Georgia Institute of Technology)

In this talk I will describe a theory of matrix completion for the extreme case of noisy 1-bit observations. Instead of observing a subset of the real-valued entries of a matrix M, we obtain a small number of binary (1-bit) measurements generated according to a probability distribution determined by the real-valued entries of M. The central question I will discuss is whether or not it is possible to obtain an accurate estimate of M from this data. In general this would seem impossible, but we show that the maximum likelihood estimate under a suitable constraint returns an accurate estimate of M under certain natural conditions. If the log-likelihood is a concave function (e.g., the logistic or probit observation models), then we can obtain this estimate by optimizing a convex program.


Combinatorial Pooling Enables Selective Sequencing of the Barley Gene Space

03/13/2013 - 1:15pm
03/13/2013 - 2:15pm
Denise Duma (Computer Science, University of California Riverside)

For the vast majority of species -- including many economically or ecologically important organisms, progress in biological research is hampered due to the lack of a reference genome sequence. Despite recent advances in sequencing technologies, several factors still limit the availability of such a critical resource. At the same time, many research groups and international consortia have already produced BAC libraries and physical maps and now are in a position to proceed with the development of whole-genome sequences organized around a physical map anchored to a genetic map. We propose a BAC-by-BAC sequencing protocol that combines combinatorial pooling design and second-generation sequencing technology to efficiently approach denovo selective genome sequencing. We show that combinatorial pooling is a cost-effective and practical alternative to exhaustive DNA barcoding when preparing sequencing libraries for hundreds or thousands of DNA samples, such as in this case gene-bearing minimum-tiling-path BAC clones. The novelty of the protocol hinges on the computational ability to efficiently compare hundred millions of short reads and assign them to the correct BAC clones (deconvolution) so that the assembly can be carried out clone-by-clone. Experimental results on simulated data for the rice genome show that the deconvolution is very accurate, and the resulting BAC assemblies have high quality. Results on real data for a gene-rich subset of the barley genome confirm that the deconvolution is accurate and the BAC assemblies have good quality. While our method cannot provide the level of completeness that one would achieve with a comprehensive whole-genome sequencing project, we show that it is quite successful in reconstructing the gene sequences within BACs. In the case of plants such as barley, this level of sequence knowledge is sufficient to support critical end-point objectives such as map-based cloning and marker-assisted breeding.

RS 105
Add to calendar
Syndicate content