Accuracy of TSVD solutions computed from rank-revealing decompositions

Summary. Rank-revealing decompositions are favorable alternatives to the singular value decomposition (SVD) because they are faster to compute and easier to update. Although they do not yield all the information that the SVD does, they yield enough information to solve various problems because they provide accurate bases for the relevant subspaces. In this paper we consider rank-revealing decompositions in computing estimates of the truncated SVD (TSVD) solution to an overdetermined system of linear equations , where is numerically rank deficient. We derive analytical bounds which show how the accuracy of the solution is intimately connected to the quality of the subspaces. Received July 12, 1993 / Revised version received November 14, 1994     

Spectral decompositions for the solutions of Sylvester,Lyapunov, and Krein equations

Doklady Mathematics - Spectral decompositions for the solutions of Lyapunov equation obtained earlier are generalized to a more general class of solutions of Krein matrix equations including as a...     

UTV Expansion Pack: Special-purpose rank-revealing algorithms

This collection of Matlab 7.0 software supplements and complements the package UTV Tools from 1999, and includes implementations of special-purpose rank-revealing algorithms developed since the publication of the original package. We provide algorithms for computing and modifying symmetric rank-revealing VSV decompositions, we expand the algorithms for the ULLV decomposition of a matrix pair to handle interference-type problems with a rank-deficient covariance matrix, and we provide a robust and reliable Lanczos algorithm which – despite its simplicity – is able to capture all the dominant singular values of a sparse or structured matrix. These new algorithms have applications in signal processing, optimization and LSI information retrieval. AMS subject classification 65F25     

A Krylov–Schur approach to the truncated SVD

Computing a small number of singular values is required in many practical applications and it is therefore desirable to have efficient and robust methods that can generate such truncated singular value decompositions. A method based on the Lanczos bidiagonalization and the Krylov–Schur method is presented. It is shown that deflation strategies can be easily implemented in this method and possible stopping criteria are discussed. Numerical experiments show the efficiency of the Krylov–Schur method.     

Spectral Decompositions for the Solutions of Lyapunov Equations for Bilinear Dynamical Systems

Doklady Mathematics - In this paper, novel spectral decompositions are obtained for the solutions of generalized Lyapunov equations, which are observed in the study of controllability and...     

Schauder decomposition and its application to integral equations of the second kind

The rates of convergence of Schauder decompositions in L_p and W_p⁽ⁿ⁾ are established. An application of Schauder decompositions to numerical solutions for integral of the second kind is made.     

Basic systems of orthogonal functions for space-time multivectors

Space-time multivectors in Clifford algebra (space-time algebra) and their application to nonlinear electrodynamics are considered. Functional product and infinitesimal operators for translation and rotation groups are introduced, where unit pseudoscalar or hyperimaginary unit is used instead of imaginary unit. Basic systems of orthogonal functions (plane waves, cylindrical, and spherical) for space-time multivectors are built by using the introduced infinitesimal operators. Appropriate orthogonal decompositions for electromagnetic field are presented. These decompositions are applied to nonlinear electrodynamics. Appropriate first order equation systems for cylindrical and spherical radial functions are obtained. Plane waves, cylindrical, and spherical solutions to the linear electrodynamics are represented by using the introduced orthogonal functions. A decomposition of a plane wave in terms of the introduced spherical harmonics is obtained.     

部分服务台异步单重休假M/M/c排队

利用拟生灭过程和矩阵几何解的方法研究了只允许部分服务台异步单重休假的M/M/c排队系统,给出了系统的稳态指标的计算方法和条件随机分解结果,最后指出一些较简单的排队模型是本文的特例.     

Characterization of infinite divisibility by duality formulas. Application to Lévy processes and random measures

Processes with independent increments are proven to be the unique solutions of duality formulas. This result is based on a simple characterization of infinitely divisible random vectors by a functional equation in which a difference operator appears. This operator is constructed by a variational method and compared to approaches involving chaos decompositions. We also obtain a related characterization of infinitely divisible random measures.     

矩阵方程AX=B的中心对称定秩解及其最佳逼近

本文研究了矩阵方程AX=B的中心对称解.利用矩阵对的广义奇异值分解和广义逆矩阵,获得了该方程有中心对称解的充要条件以及有解时,最大秩解、最小秩解的一般表达式,并讨论了中心对称最小秩解集合中与给定矩阵的最佳逼近解.     

A pathwise approach to backward and forward stochastic differential equations on the poisson space*

We study the existence and uniqueness of pathwise solutions to backward and forward stochastic differential equations on the Poisson space. We obtain the structure of these pathwise solutions to give the relationship between them. Also, in the bilinear case, we calculate the explicit form of their chaos decompositions.     

General interface problems—II

We continue the study of general interface problems. We prove regularity and asymptotics of solutions in usual Sobolev spaces for non-constant coefficients operators. We also give the stabilization procedure when unstable decompositions appear near a critical angle.     

Elastic and electro-magnetic waves in infinite waveguides

We consider initial-boundary value problems for the equations of isotropic elasticity for several mixed boundary conditions in infinite wave guides, as well as Maxwell equations. With the help of decompositions of the displacement field into divergence- and curl-free parts, respectively, which are compatible with the boundary conditions, we obtain sharp decay rates for the solutions. The decomposed systems correspond to the second-order Maxwell equations for the electric and the magnetic field with electric and magnetic boundary conditions, respectively.     

Wavelet method for solving the unsteady porous-medium flow problem with discontinuous coefficients

A method is proposed for constructing stable approximate wavelet decompositions of weak solutions to boundary value problems for the unsteady porous-medium flow equation with discontinuous coefficients and inexact data. The method is based on the general scheme for finite-dimensional approximation in Tikhonov regularization and on multiresolution analysis with basis functions defined as the product of one-dimensional Daubechies wavelets.     

On the Structure of asymptotics of the solution of a second-order elliptic equation in a neighborhood of an angular point

The behavior of solutions of elliptic equations in neighborhoods of angular and conical boundary points has been well studied; the asymptotics of these solutions has been constructed. In the present paper, we propose a new approach to constructing asymptotic decompositions in a neighborhood of an angular boundary point, which allows us to describe the structure of these asymptotics in a relatively simple and illustrative way.     

Undominated d.c. Decompositions of Quadratic Functions and Applications to Branch-and-Bound Approaches

In this paper we analyze difference-of-convex (d.c.) decompositions for indefinite quadratic functions. Given a quadratic function, there are many possible ways to decompose it as a difference of two convex quadratic functions. Some decompositions are dominated, in the sense that other decompositions exist with a lower curvature. Obviously, undominated decompositions are of particular interest. We provide three different characterizations of such decompositions, and show that there is an infinity of undominated decompositions for indefinite quadratic functions. Moreover, two different procedures will be suggested to find an undominated decomposition starting from a generic one. Finally, we address applications where undominated d.c.d.s may be helpful: in particular, we show how to improve bounds in branch-and-bound procedures for quadratic optimization problems.     

A technique to prove parameter-uniform convergence for a singularly perturbed convection–diffusion equation

A priori parameter explicit bounds on the solution of singularly perturbed elliptic problems of convection–diffusion type are established. Regular exponential boundary layers can appear in the solution. These bounds on the solutions and its derivatives are obtained using a suitable decomposition of the solution into regular and layer components. By introducing extensions of the coefficients to a larger domain, artificial compatibility conditions are not imposed in the derivation of these decompositions.     

On truncated incomplete decompositions

In the present paper we introduce truncated incomplete decompositions (TrILU) for constant coefficient matrices. This new ILU variant saves most of the memory and work usually needed to compute and store the factorization. Further it improves the smoothing and preconditioning properties of standard ILU-decompositions. Besides describing the algorithm, we give theoretical results concerning stability and convergence as well as the smoothing property and robustness for TrILU smoothing in a multi-grid method. Further, we add numerical results of TrILU as smoother in a multi-grid method and as preconditioner in a pcg-method fully confirming the theoretical results.This work was supported by Deutsche Forschungsgemeinschaft.