Xuemin Tu

Alexandre J. Chorin, Matthias Morzfeld, Xuemin Tu

Implicit particle filters for data assimilation update the particles by first choosing probabilities and then looking for particle locations that assume them, guiding the particles one by one to the high probability domain. We provide a detailed description of these filters, with illustrative examples, together with new, more general, methods for solving the algebraic equations and with a new algorithm for parameter identification.

Matthias Morzfeld, Xuemin Tu, Ethan Atkins et al.

Implicit particle filters for data assimilation generate high-probability samples by representing each particle location as a separate function of a common reference variable. This representation requires that a certain underdetermined equation be solved for each particle and at each time an observation becomes available. We present a new implementation of implicit filters in which we find the solution of the equation via a random map. As examples, we assimilate data for a stochastically driven Lorenz system with sparse observations and for a stochastic Kuramoto-Sivashinski equation with observations that are sparse in both space and time.

Peter R. Brune, Matthew G. Knepley, Barry F. Smith et al.

Most efficient linear solvers use composable algorithmic components, with the most common model being the combination of a Krylov accelerator and one or more preconditioners. A similar set of concepts may be used for nonlinear algebraic systems, where nonlinear composition of different nonlinear solvers may significantly improve the time to solution. We describe the basic concepts of nonlinear composition and preconditioning and present a number of solvers applicable to nonlinear partial differential equations. We have developed a software framework in order to easily explore the possible combinations of solvers. We show that the performance gains from using composed solvers can be substantial compared with gains from standard Newton-Krylov methods.

Jing Li, Xuemin Tu

A non-overlapping domain decomposition algorithm is proposed to solve the linear system arising from mixed finite element approximation of incompressible Stokes equations. A continuous finite element space for the pressure is used. In the proposed algorithm, Lagrange multipliers are used to enforce continuity of the velocity component across the subdomain domain boundary. The continuity of the pressure component is enforced in the primal form, i.e., neighboring subdomains share the same pressure degrees of freedom on the subdomain interface and no Lagrange multipliers are needed. After eliminating all velocity variables and the independent subdomain interior parts of the pressures, a symmetric positive semi-definite linear system for the subdomain boundary pressures and the Lagrange multipliers is formed and solved by a preconditioned conjugate gradient method. A lumped preconditioner is studied and the condition number bound of the preconditioned operator is proved to be independent of the number of subdomains for fixed subdomain problem size. Numerical experiments demonstrate the convergence rate of the proposed algorithm.

Xuemin Tu, Jing Li

A unified framework of FETI-DP algorithms is proposed for solving the system of linear equations arising from the mixed finite element approximation of incompressible Stokes equations. A distinctive feature of this framework is that it allows using both continuous and discontinuous pressures in the algorithm, while previous FETI-DP methods only apply to discontinuous pressures. A preconditioned conjugate gradient method is used in the algorithm with either a lumped or a Dirichlet preconditioner, and scalable convergence rates are proved. This framework is also used to describe several previously developed FETI-DP algorithms and greatly simplifies their analysis. Numerical experiments of solving a two-dimensional incompressible Stokes problem demonstrate the performances of the discussed FETI-DP algorithms represented under the same framework.

Wenchi Ma, Xuemin Tu, Bo Luo et al.

The paper proposes a semantic clustering based deduction learning by mimicking the learning and thinking process of human brains. Human beings can make judgments based on experience and cognition, and as a result, no one would recognize an unknown animal as a car. Inspired by this observation, we propose to train deep learning models using the clustering prior that can guide the models to learn with the ability of semantic deducing and summarizing from classification attributes, such as a cat belonging to animals while a car pertaining to vehicles. %Specifically, if an image is labeled as a cat, then the model is trained to learn that "this image is totally not any random class that is the outlier of animal". The proposed approach realizes the high-level clustering in the semantic space, enabling the model to deduce the relations among various classes during the learning process. In addition, the paper introduces a semantic prior based random search for the opposite labels to ensure the smooth distribution of the clustering and the robustness of the classifiers. The proposed approach is supported theoretically and empirically through extensive experiments. We compare the performance across state-of-the-art classifiers on popular benchmarks, and the generalization ability is verified by adding noisy labeling to the datasets. Experimental results demonstrate the superiority of the proposed approach.

Bart de Leeuw, Svetlana Dubinkina, Jason Frank et al.

In this article we develop algorithms for data assimilation based upon a computational time dependent stable/unstable splitting. Our particular method is based upon shadowing refinement and synchronization techniques and is motivated by work on Assimilation in the Unstable Subspace (AUS) and Pseudo-orbit Data Assimilation (PDA). The algorithm utilizes time dependent projections onto the non-stable subspace determined by employing computational techniques for Lyapunov exponents/vectors. The method is extended to parameter estimation without changing the problem dynamics and we address techniques for adapting the method when (as is commonly the case) observations are not available in the full model state space. We use a combination of analysis and numerical experiments (with the Lorenz 63 and Lorenz 96 models) to illustrate the efficacy of the techniques and show that the results compare favorably with other variational techniques.

Matthias Morzfeld, Xuemin Tu, Jon Wilkening et al.

Implicit sampling is a weighted sampling method that is used in data assimilation, where one sequentially updates estimates of the state of a stochastic model based on a stream of noisy or incomplete data. Here we describe how to use implicit sampling in parameter estimation problems, where the goal is to find parameters of a numerical model, e.g.~a partial differential equation (PDE), such that the output of the numerical model is compatible with (noisy) data. We use the Bayesian approach to parameter estimation, in which a posterior probability density describes the probability of the parameter conditioned on data and compute an empirical estimate of this posterior with implicit sampling. Our approach generates independent samples, so that some of the practical difficulties one encounters with Markov Chain Monte Carlo methods, e.g.~burn-in time or correlations among dependent samples, are avoided. We describe a new implementation of implicit sampling for parameter estimation problems that makes use of multiple grids (coarse to fine) and BFGS optimization coupled to adjoint equations for the required gradient calculations. The implementation is "dimension independent", in the sense that a well-defined finite dimensional subspace is sampled as the mesh used for discretization of the PDE is refined. We illustrate the algorithm with an example where we estimate a diffusion coefficient in an elliptic equation from sparse and noisy pressure measurements. In the example, dimension\slash mesh-independence is achieved via Karhunen-Loève expansions.

Fei Lu, Matthias Morzfeld, Xuemin Tu et al.

Polynomial chaos expansions are used to reduce the computational cost in the Bayesian solutions of inverse problems by creating a surrogate posterior that can be evaluated inexpensively. We show, by analysis and example, that when the data contain significant information beyond what is assumed in the prior, the surrogate posterior can be very different from the posterior, and the resulting estimates become inaccurate. One can improve the accuracy by adaptively increasing the order of the polynomial chaos, but the cost may increase too fast for this to be cost effective compared to Monte Carlo sampling without a surrogate posterior.

Alexandre J. Chorin, Xuemin Tu

We present a general form of the iteration and interpolation process used in implicit particle filters. Implicit filters are based on a pseudo-Gaussian representation of posterior densities, and are designed to focus the particle paths so as to reduce the number of particles needed in nonlinear data assimilation. Examples are given.

Alexandre J. Chorin, Xuemin Tu

Particle filters for data assimilation in nonlinear problems use "particles" (replicas of the underlying system) to generate a sequence of probability density functions (pdfs) through a Bayesian process. This can be expensive because a significant number of particles has to be used to maintain accuracy. We offer here an alternative, in which the relevant pdfs are sampled directly by an iteration. An example is discussed in detail.