**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Publication# On quadratic matrix equations with infinite size coefficients encountered in QBD stochastic processes

Abstract

Matrix equations of the kind A(1)X(2)+A(0)X+A(-1)=X, where both the matrix coefficients and the unknown are semi-infinite matrices belonging to a Banach algebra, are considered. These equations, where coefficients are quasi-Toeplitz matrices, are encountered in certain quasi-birth-death processes as the tandem Jackson queue or in any other processes that can be modeled as a reflecting random walk in the quarter plane. We provide a numerical framework for approximating the minimal nonnegative solution of these equations that relies on semi-infinite quasi-Toeplitz matrix arithmetic. In particular, we show that the algorithm of cyclic reduction can be effectively applied and can approximate the infinite-dimensional solutions with quadratic convergence at a cost that is comparable to that of the finite case. This way, we may compute a finite approximation of the sought solution and of the invariant probability measure of the associated quasi-birth-death process, within a given accuracy. Numerical experiments, performed on a collection of benchmarks, confirm the theoretical analysis.

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related concepts

Loading

Related publications

Loading

Related publications (6)

Loading

Loading

Loading

Related concepts (19)

Matrix (mathematics)

In mathematics, a matrix (plural matrices) is a rectangular array or table of numbers, symbols, or expressions, arranged in rows and columns, which is used to represent a mathematical object or a pr

Coefficient

In mathematics, a coefficient is a multiplicative factor involved in some term of a polynomial, a series, or an expression. It may be a number (dimensionless), in which case it is known as a numeric

Stochastic process

In probability theory and related fields, a stochastic (stəˈkæstɪk) or random process is a mathematical object usually defined as a sequence of random variables, where the index of the sequence has

Several computational challenges arise when evaluating the failure probability of a given system in the context of risk prediction or reliability analysis. When the dimension of the uncertainties becomes high, well established direct numerical methods can not be employed because of the "curse-of-dimensionality". Many surrogate models have been proposed with the aim of reducing computational effort. However, most of them fail in computing an accurate failure probability when the limit state surface defined by the failure event in the probability space lacks smoothness. In addition, for a stochastic system modeled by partial differential equations (PDEs) with random input, only a limited number of the underlying PDEs (order of a few tens) are affordable to solve in practice due to the considerable computational effort, therefore preventing the application of many numerical methods especially for high dimensional random inputs. In this work we develop hybrid and goal-oriented adaptive reduced basis methods to tackle these challenges by accurately and efficiently computing the failure probability of a stochastic PDE. The curse-of-dimensionality is significantly alleviated by reduced basis approximation whose bases are constructed by goal-oriented adaptation. Moreover, an accurate evaluation of the failure probability for PDE system with solution of low regularity in probability space is guaranteed by the certified a posteriori error bound for the output approximation error. At the end of this paper we suitably extend our proposed method to deal with more general PDE models. Finally we perform several numerical experiments to illustrate its computational accuracy and efficiency. (C) 2013 Elsevier B.V. All rights reserved.

This thesis is devoted to the derivation of error estimates for partial differential equations with random input data, with a focus on a posteriori error estimates which are the basis for adaptive strategies. Such procedures aim at obtaining an approximation of the solution with a given precision while minimizing the computational costs. If several sources of error come into play, it is then necessary to balance them to avoid unnecessary work. We are first interested in problems that contain small uncertainties approximated by finite elements. The use of perturbation techniques is appropriate in this setting since only few terms in the power series expansion of the exact random solution with respect to a parameter characterizing the amount of randomness in the problem are required to obtain an accurate approximation. The goal is then to perform an error analysis for the finite element approximation of the expansion up to a certain order. First, an elliptic model problem with random diffusion coefficient with affine dependence on a vector of independent random variables is studied. We give both a priori and a posteriori error estimates for the first term in the expansion for various norms of the error. The results are then extended to higher order approximations and to other sources of uncertainty, such as boundary conditions or forcing term. Next, the analysis of nonlinear problems in random domains is proposed, considering the one-dimensional viscous Burgers' equation and the more involved incompressible steady-state Navier-Stokes equations. The domain mapping method is used to transform the equations in random domains into equations in a fixed reference domain with random coefficients. We give conditions on the mapping and the input data under which we can prove the well-posedness of the problems and give a posteriori error estimates for the finite element approximation of the first term in the expansion. Finally, we consider the heat equation with random Robin boundary conditions. For this parabolic problem, the time discretization brings an additional source of error that is accounted for in the error analysis. The second part of this work consists in the analysis of a random elliptic diffusion problem that is approximated in the physical space by the finite element method and in the stochastic space by the stochastic collocation method on a sparse grid. Considering a random diffusion coefficient with affine dependence on a vector of independent random variables, we derive a residual-based a posteriori error estimate that controls the two sources of error. The stochastic error estimator is then used to drive an adaptive sparse grid algorithm which aims at alleviating the so-called curse of dimensionality inherent to tensor grids. Several numerical examples are given to illustrate the performance of the adaptive procedure.

We present a new fully first-order strongly hyperbolic representation of the Baumgarte-Shapiro-Shibata-Nakamura formulation of Einstein's equations with optional constraint damping terms. We describe the characteristic fields of the system, discuss its hyperbolicity properties, and present two numerical implementations and simulations: one using finite differences, adaptive mesh refinement, and, in particular, binary black holes, and another one using the discontinuous Galerkin method in spherical symmetry. The results of this paper constitute a first step in an effort to combine the robustness of Baumgarte-Shapiro-Shibata-Nakamura evolutions with very high accuracy numerical techniques, such as spectral collocation multidomain or discontinuous Galerkin methods.