Topic overview

math.NA

4249 works8278 researchers0 institutions

Topic snapshot

What this area looks like now

4249works

8278authors

0experts visible

0communities

Next steps

Move from topic reading into action

The graph preview below keeps the nearby papers, people and communities visible in the same reading flow.

Inspect nearby papers, researchers, institutions and communities without opening a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2016arXiv

General solution of the Poisson equation for Quasi-Birth-and-Death processes

We consider the Poisson equation $(I-P)\boldsymbol{u}=\boldsymbol{g}$, where $P$ is the transition matrix of a Quasi-Birth-and-Death (QBD) process with infinitely many levels, $\bm g$ is a given infinite dimensional vector and $\bm u$ is the unknown. Our main result is to provide the general solution of this equation. To this purpose we use the block tridiagonal and block Toeplitz structure of the matrix $P$ to obtain a set of matrix difference equations, which are solved by constructing suitable resolvent triples.

preprint2015arXiv

Generalization of the Brauer Theorem to Matrix Polynomials and Matrix Laurent Series

Given a square matrix $A$, Brauer's theorem [Duke Math. J. 19 (1952), 75--91] shows how to modify one single eigenvalue of $A$ via a rank-one perturbation, without changing any of the remaining eigenvalues. We reformulate Brauer's theorem in functional form and provide extensions to matrix polynomials and to matrix Laurent series $A(z)$ together with generalizations to shifting a set of eigenvalues. We provide conditions under which the modified function $\widetilde A(z)$ has a canonical factorization $\widetilde A(z)=\widetilde U(z)\widetilde L(z^{-1})$ and we provide explicit expressions of the factors $\widetilde U(z)$ and $\widetilde L(z)$. Similar conditions and expressions are given for the factorization of $\widetilde A(z^{-1})$. Some applications are discussed.

preprint2014arXiv

Computation of measure-valued solutions for the incompressible Euler equations

We combine the spectral (viscosity) method and ensemble averaging to propose an algorithm that computes admissible measure valued solutions of the incompressible Euler equations. The resulting approximate young measures are proved to converge (with increasing numerical resolution) to a measure valued solution. We present numerical experiments demonstrating the robustness and efficiency of the proposed algorithm, as well as the appropriateness of measure valued solutions as a solution framework for the Euler equations. Furthermore, we report an extensive computational study of the two dimensional vortex sheet, which indicates that the computed measure valued solution is non-atomic and implies possible non-uniqueness of weak solutions constructed by Delort.

preprint2016arXiv

Discrete approximations to local times for reflected diffusions

We propose a discrete analogue for the boundary local time of reflected diffusions in bounded Lipschitz domains. This discrete analogue, called the discrete local time, can be effectively simulated in practice and is obtained pathwise from random walks on lattices. We establish weak convergence of the joint law of the discrete local time and the associated random walks as the lattice size decreases to zero. A cornerstone of the proof is the local central limit theorem for reflected diffusions developed in [7]. Applications of the join convergence result to PDE problems are illustrated.

preprint2015arXiv

Low-rank methods for high-dimensional approximation and model order reduction

Tensor methods are among the most prominent tools for the numerical solution of high-dimensional problems where functions of multiple variables have to be approximated. These methods exploit the tensor structure of function spaces and apply to many problems in computational science which are formulated in tensor spaces, such as problems arising in stochastic calculus, uncertainty quantification or parametric analyses. Here, we present complexity reduction methods based on low-rank approximation methods. We analyze the problem of best approximation in subsets of low-rank tensors and discuss its connection with the problem of optimal model reduction in low-dimensional reduced spaces. We present different algorithms for computing approximations of a function in low-rank formats. In particular, we present constructive algorithms which are based either on a greedy construction of an approximation (with successive corrections in subsets of low-rank tensors) or on the greedy construction of tensor subspaces (for subspace-based low-rank formats). These algorithms can be applied for tensor compression, tensor completion or for the numerical solution of equations in low-rank tensor formats. A special emphasis is given to the solution of stochastic or parameter-dependent models. Different approaches are presented for the approximation of vector-valued or multivariate functions (identified with tensors), based on samples of the functions (black-box approaches) or on the models equations which are satisfied by the functions.

preprint2012arXiv

Lower Error Bounds for Randomized Multilevel and Changing Dimension Algorithms

We provide lower error bounds for randomized algorithms that approximate integrals of functions depending on an unrestricted or even infinite number of variables. More precisely, we consider the infinite-dimensional integration problem on weighted Hilbert spaces with an underlying anchored decomposition and arbitrary weights. We focus on randomized algorithms and the randomized worst case error. We study two cost models for function evaluation which depend on the number of active variables of the chosen sample points. Multilevel algorithms behave very well with respect to the first cost model, while changing dimension algorithms and also dimension-wise quadrature methods, which are based on a similar idea, can take advantage of the more generous second cost model. We prove the first non-trivial lower error bounds for randomized algorithms in these cost models and demonstrate their quality in the case of product weights. In particular, we show that the randomized changing dimension algorithms provided in [L. Plaskota, G. W. Wasilkowski, J. Complexity 27 (2011), 505--518] achieve convergence rates arbitrarily close to the optimal convergence rate.

preprint2015arXiv

Finite element method and isogeometric analysis in electronic structure calculations: convergence study

We compare convergence of isogeometric analysis (IGA), a spline modification of finite element method (FEM), with FEM in the context of our real space code for ab-initio electronic structure calculations of non-periodic systems. The convergence is studied on simple sub-problems that appear within the density functional theory approximation to the Schrödinger equation: the Poisson problem and the generalized eigenvalue problem. We also outline the complete iterative algorithm seeking a fixed point of the charge density of a system of atoms or molecules, and study IGA/FEM convergence on a benchmark problem of nitrogen atom.

preprint2012arXiv

Infinite-Dimensional Integration in Weighted Hilbert Spaces: Anchored Decompositions, Optimal Deterministic Algorithms, and Higher Order Convergence

We study numerical integration of functions depending on an infinite number of variables. We provide lower error bounds for general deterministic linear algorithms and provide matching upper error bounds with the help of suitable multilevel algorithms and changing dimension algorithms. More precisely, the spaces of integrands we consider are weighted reproducing kernel Hilbert spaces with norms induced by an underlying anchored function space decomposition. Here the weights model the relative importance of different groups of variables. The error criterion used is the deterministic worst case error. We study two cost models for function evaluation which depend on the number of active variables of the chosen sample points, and two classes of weights, namely product and order-dependent (POD) weights and the newly introduced weights with finite active dimension. We show for these classes of weights that multilevel algorithms achieve the optimal rate of convergence in the first cost model while changing dimension algorithms achieve the optimal convergence rate in the second model. As an illustrative example, we discuss the anchored Sobolev space with smoothness parameter $α$ and provide new optimal quasi-Monte Carlo multilevel algorithms and quasi-Monte Carlo changing dimension algorithms based on higher-order polynomial lattice rules.

preprint2016arXiv

Isogeometric analysis in electronic structure calculations

In electronic structure calculations, various material properties can be obtained by means of computing the total energy of a system as well as derivatives of the total energy w.r.t. atomic positions. The derivatives, also known as Hellman-Feynman forces, require, because of practical computational reasons, the discretized charge density and wave functions having continuous second derivatives in the whole solution domain. We describe an application of isogeometric analysis (IGA), a spline modification of finite element method (FEM), to achieve the required continuity. The novelty of our approach is in employing the technique of Bézier extraction to add the IGA capabilities to our FEM based code for ab-initio calculations of electronic states of non-periodic systems within the density-functional framework, built upon the open source finite element package SfePy. We compare FEM and IGA in benchmark problems and several numerical results are presented.

preprint2016arXiv

Geometric Multigrid for Darcy and Brinkman models of flows in highly heterogeneous porous media: A numerical study

We apply geometric multigrid methods for the finite element approximation of flow problems governed by Darcy and Brinkman systems used in modeling highly heterogeneous porous media. The method is based on divergence-conforming discontinuous Galerkin methods and overlapping, patch based domain decomposition smoothers. We show in benchmark experiments that the method is robust with respect to mesh size and contrast of permeability for highly heterogeneous media.

preprint2016arXiv

Shift techniques for Quasi-Birth and Death processes: canonical factorizations and matrix equations

We revisit the shift technique applied to Quasi-Birth and Death (QBD) processes (He, Meini, Rhee, SIAM J. Matrix Anal. Appl., 2001) by bringing the attention to the existence and properties of canonical factorizations. To this regard, we prove new results concerning the solutions of the quadratic matrix equations associated with the QBD. These results find applications to the solution of the Poisson equation for QBDs.

preprint2016arXiv

Semi-Infinite Quasi-Toeplitz Matrices with Applications to QBD Stochastic Processes

Denote by $\mathcal{W}_1$ the set of complex valued functions of the form $a(z)=\sum_{i=-\infty}^{+\infty}a_iz^i$ which are continuous on the unit circle, and such that $\sum_{i=-\infty}^{+\infty}|ia_i|<\infty$. We call CQT matrix a quasi-Toeplitz matrix $A$, associated with a continuous symbol $a(z)\in\mathcal W_1$, of the form $A=T(a)+E$, where $T(a)=(t_{i,j})_{i,j\in\mathbb{Z}^+}$ is the semi-infinite Toeplitz matrix such that $t_{i,j}=a_{j-i}$, for $i,j\in\mathbb Z^+$, and $E=(e_{i,j})_{i,j\in\mathbb{Z}^+}$ is a semi-infinite matrix such that $\sum_{i,j=1}^{+\infty}|e_{i,j}|$ is finite. We prove that the class of CQT matrices is a Banach algebra with a suitable sub-multiplicative matrix norm $\|\cdot\|$. We introduce a finite representation of CQT matrices together with algorithms which implement elementary matrix operations. An application to solving quadratic matrix equations of the kind $AX^2+BX+C=0$, encountered in the solution of Quasi-Birth and Death (QBD) stochastic processes with a denumerable set of phases, is presented where $A,B,C$ are CQT matrices.

preprint2018arXiv

A stabilised finite element method for the plate obstacle problem

We introduce a stabilised finite element formulation for the Kirchhoff plate obstacle problem and derive both a priori and residual-based a posteriori error estimates using conforming $C^1$-continuous finite elements. We implement the method as a Nitsche-type scheme and give numerical evidence for its effectiveness in the case of an elastic and a rigid obstacle.

preprint2018arXiv

ODE and PDE based modeling of biological transportation networks

We study the global existence of solutions of a discrete (ODE based) model on a graph describing the formation of biological transportation networks, introduced by Hu and Cai. We propose an adaptation of this model so that a macroscopic (PDE based) system can be obtained as its formal continuum limit. We prove the global existence of weak solutions of the macroscopic PDE model. Finally, we present results of numerical simulations of the discrete model, illustrating the convergence to steady states, their non-uniqueness as well as their dependence on initial data and model parameters.

preprint2018arXiv

Robust approximation error estimates and multigrid solvers for isogeometric multi-patch discretizations

In recent publications, the author and his coworkers have shown robust approximation error estimates for B-splines of maximum smoothness and have proposed multigrid methods based on them. These methods allow to solve the linear system arizing from the discretization of a partial differential equation in Isogeometric Analysis in a single-patch setting with convergence rates that are provably robust both in the grid size and the spline degree. In real-world problems, the computational domain cannot be nicely represented by just one patch. In computer aided design, such domains are typically represented as a union of multiple patches. In the present paper, we extend the approximation error estimates and the multigrid solver to this multi-patch case.

preprint2018arXiv

A note on incremental POD algorithms for continuous time data

In our earlier work [Fareed et al., Comput. Math. Appl. 75 (2018), no. 6, 1942-1960], we developed an incremental approach to compute the proper orthogonal decomposition (POD) of PDE simulation data. Specifically, we developed an incremental algorithm for the SVD with respect to a weighted inner product for the discrete time POD computations. For continuous time data, we used an approximate approach to arrive at a discrete time POD problem and then applied the incremental SVD algorithm. In this note, we analyze the continuous time case with simulation data that is piecewise constant in time such that each data snapshot is expanded in a finite collection of basis elements of a Hilbert space. We first show that the POD is determined by the SVD of two different data matrices with respect to weighted inner products. Next, we develop incremental algorithms for approximating the two matrix SVDs with respect to the different weighted inner products. Finally, we show neither approximate SVD is more accurate than the other; specifically, we show the incremental algorithms return equivalent results.

preprint2017arXiv

Finite Volume approximations of the Euler system with variable congestion

We are interested in the numerical simulations of the Euler system with variable congestion encoded by a singular pressure. This model describes for instance the macroscopic motion of a crowd with individual congestion preferences. We propose an asymptotic preserving (AP) scheme based on a conservative formulation of the system in terms of density, momentum and density fraction. A second order accuracy version of the scheme is also presented. We validate the scheme on one-dimensional test-cases and extended here to higher order accuracy. We finally carry out two dimensional numerical simulations and show that the model exhibit typical crowd dynamics.

preprint2016arXiv

On Functions of quasi Toeplitz matrices

Let $a(z)=\sum_{i\in\mathbb Z}a_iz^i$ be a complex valued continuous function, defined for $|z|=1$, such that $\sum_{i=-\infty}^{+\infty}|ia_i|<\infty$. Consider the semi-infinite Toeplitz matrix $T(a)=(t_{i,j})_{i,j\in\mathbb Z^+}$ associated with the symbol $a(z)$ such that $t_{i,j}=a_{j-i}$. A quasi-Toeplitz matrix associated with the continuous symbol $a(z)$ is a matrix of the form $A=T(a)+E$ where $E=(e_{i,j})$, $\sum_{i,j\in\mathbb Z^+}|e_{i,j}|<\infty$, and is called a CQT-matrix. Given a function $f(x)$ and a CQT matrix $M$, we provide conditions under which $f(M)$ is well defined and is a CQT matrix. Moreover, we introduce a parametrization of CQT matrices and algorithms for the computation of $f(M)$. We treat the case where $f(x)$ is assigned in terms of power series and the case where $f(x)$ is defined in terms of a Cauchy integral. This analysis is applied also to finite matrices which can be written as the sum of a Toeplitz matrix and of a low rank correction.

preprint2018arXiv

A parallel multigrid solver for multi-patch Isogeometric Analysis

Isogeometric Analysis (IgA) is a framework for setting up spline-based discretizations of partial differential equations, which has been introduced around a decade ago and has gained much attention since then. If large spline degrees are considered, one obtains the approximation power of a high-order method, but the number of degrees of freedom behaves like for a low-order method. One important ingredient to use a discretization with large spline degree, is a robust and preferably parallelizable solver. While numerical evidence shows that multigrid solvers with standard smoothers (like Gauss Seidel) does not perform well if the spline degree is increased, the multigrid solvers proposed by the authors and their co-workers proved to behave optimal both in the grid size and the spline degree. In the present paper, the authors want to show that those solvers are parallelizable and that they scale well in a parallel environment.

preprint2017arXiv

On the Convergence of Asynchronous Parallel Iteration with Unbounded Delays

Recent years have witnessed the surge of asynchronous parallel (async-parallel) iterative algorithms due to problems involving very large-scale data and a large number of decision variables. Because of asynchrony, the iterates are computed with outdated information, and the age of the outdated information, which we call delay, is the number of times it has been updated since its creation. Almost all recent works prove convergence under the assumption of a finite maximum delay and set their stepsize parameters accordingly. However, the maximum delay is practically unknown. This paper presents convergence analysis of an async-parallel method from a probabilistic viewpoint, and it allows for large unbounded delays. An explicit formula of stepsize that guarantees convergence is given depending on delays' statistics. With $p+1$ identical processors, we empirically measured that delays closely follow the Poisson distribution with parameter $p$, matching our theoretical model, and thus the stepsize can be set accordingly. Simulations on both convex and nonconvex optimization problems demonstrate the validness of our analysis and also show that the existing maximum-delay induced stepsize is too conservative, often slowing down the convergence of the algorithm.

preprint2018arXiv

Semi-smooth Newton methods for nonlinear complementarity formulation of compositional two-phase flow in porous media

Simulating compositional multiphase flow in porous media is a challenging task, especially when phase transition is taken into account. The main problem with phase transition stems from the inconsistency of the primary variables such as phase pressure and phase saturation, i.e. they become ill-defined when a phase appears or disappears. Recently, a new approach for handling phase transition has been developed, whereby the system is formulated as a nonlinear complementarity problem (NCP). Unlike the widely used primary variable switching (PVS) method which requires a drastic reduction of the time step size when a phase appears or disappears, this approach is more robust and allows for larger time steps. One way to solve an NCP system is to reformulate the inequality constraints as a non-smooth equation using a complementary function (C-function). Because of the non-smoothness of the constraint equations, a semi-smooth Newton method needs to be developed. In this work, we consider two methods for solving NCP systems used to model multiphase flow: (1) a semi-smooth Newton method for two C-functions: the minimum and the Fischer-Burmeister functions, and (2) a new inexact Newton method based on the Jacobian smoothing method for a smooth version of the Fischer-Burmeister function. We show that the new method is robust and efficient for standard benchmark problems as well as for realistic examples with highly heterogeneous media such as the SPE10 benchmark.

preprint2017arXiv

Robust multigrid methods for isogeometric discretizations of the Stokes equations

In recent publications, the author and his coworkers have proposed a multigrid method for solving linear systems arizing from the discretization of partial differential equations in isogeometric analysis and have proven that the convergence rates are robust in both the grid size and the polynomial degree. So, far the method has only been discussed for the Poisson problem. In the present paper, we want to face the question if it is possible to extend the method to the Stokes equations.

preprint2018arXiv

Error Analysis of an Incremental POD Algorithm for PDE Simulation Data

In our earlier work [Fareed et al., Comput. Math. Appl. 75 (2018), no. 6, 1942-1960], we proposed an incremental SVD algorithm with respect to a weighted inner product to compute the proper orthogonal decomposition (POD) of a set of simulation data for a partial differential equation (PDE) without storing the data. In this work, we perform an error analysis of the incremental SVD algorithm. We also modify the algorithm to incrementally update both the SVD and an error bound when a new column of data is added. We show the algorithm produces the exact SVD of an approximate data matrix, and the operator norm error between the approximate and exact data matrices is bounded above by the computed error bound. This error bound also allows us to bound the error in the incrementally computed singular values and singular vectors. We illustrate our analysis with numerical results for three simulation data sets from a 1D FitzHugh-Nagumo PDE system with various choices of the algorithm truncation tolerances.

preprint2017arXiv

A note on stress-driven anisotropic diffusion and its role in active deformable media

We propose a new model to describe diffusion processes within active deformable media. Our general theoretical framework is based on physical and mathematical considerations, and it suggests to use diffusion tensors directly coupled to mechanical stress. A proof-of-concept experiment and the proposed generalised reaction-diffusion-mechanics model reveal that initially isotropic and homogeneous diffusion tensors turn into inhomogeneous and anisotropic quantities due to the intrinsic structure of the nonlinear coupling. We study the physical properties leading to these effects, and investigate mathematical conditions for its occurrence. Together, the experiment, the model, and the numerical results obtained using a mixed-primal finite element method, clearly support relevant consequences of stress-assisted diffusion into anisotropy patterns, drifting, and conduction velocity of the resulting excitation waves. Our findings also indicate the applicability of this novel approach in the description of mechano-electrical feedback in actively deforming bio-materials such as the heart.