The discrete picard condition for discrete ill-posed problems

We investigate the approximation properties of regularized solutions to discrete ill-posed least squares problems. A necessary condition for obtaining good regularized solutions is that the Fourier coefficients of the right-hand side, when expressed in terms of the generalized SVD associated with the regularization problem, on the average decay to zero faster than the generalized singular values. This is the discrete Picard condition. We illustrate the importance of this condition theoretically as well as experimentally.This work was carried out during a visit to Dept. of Mathematics, UCLA, and was supported by the Danish Natural Science Foundation, by the National Science Foundation under contract NSF-DMS87-14612, and by the Army Research Office under contract No. DAAL03-88-K-0085.     

Regularization,GSVD and truncatedGSVD

The purpose of this paper is to analyze Tikhonov regularization in general form by means of generalized SVD (GSVD) in the same spirit as SVD is used to analyze standard-form regularization. We also define a truncated GSVD solution which is of interest in its own right and which sheds light on regularization as well. In addition, our analysis gives insight into a particular numerical method for solving the general-form problem via a transformation to standard form.Part of this work was carried out while visiting the Mathematical Sciences Section, Oak Ridge National Laboratory, Tennessee, during the Numerical Linear Algebra Year 1987–88, and was supported by the Danish Natural Science Foundation.     

The truncatedSVD as a method for regularization

The truncated singular value decomposition (SVD) is considered as a method for regularization of ill-posed linear least squares problems. In particular, the truncated SVD solution is compared with the usual regularized solution. Necessary conditions are defined in which the two methods will yield similar results. This investigation suggests the truncated SVD as a favorable alternative to standard-form regularization in cases of ill-conditioned matrices with well-determined numerical rank.This work was carried out while the author visited the Dept. of Computer Science, Stanford University, California, U.S.A., and was supported in part by National Science Foundation Grant Number DCR 8412314, by a Fulbright Supplementary Grant, and by the Danish Space Board.     

Subspace-restricted singular value decompositions for linear discrete ill-posed problems

The truncated singular value decomposition is a popular solution method for linear discrete ill-posed problems. These problems are numerically underdetermined. Therefore, it can be beneficial to incorporate information about the desired solution into the solution process. This paper describes a modification of the singular value decomposition that permits a specified linear subspace to be contained in the solution subspace for all truncations. Modifications that allow the range to contain a specified subspace, or that allow both the solution subspace and the range to contain specified subspaces also are described.     

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     

On uniqueness of JSJ decompositions of finitely generated groups

We give an example of two JSJ decompositions of a group that are not related by conjugation, conjugation of edge-inclusions, and slide moves. This answers the question of Rips and Sela stated in [RS].On the other hand we observe that any two JSJ decompositions of a group are related by an elementary deformation, and that strongly slide-free JSJ decompositions are genuinely unique. These results hold for the decompositions of Rips and Sela, Dunwoody and Sageev, and Fujiwara and Papasoglu, and also for accessible 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.     

A survey of multilevel preconditioned iterative methods

We survey multilevel iterative methods applied for solving large sparse systems with matrices, which depend on a level parameter, such as arise by the discretization of boundary value problems for partial differential equations when successive refinements of an initial discretization mesh is used to construct a sequence of nested difference or finite element meshes.We discuss various two-level (two-grid) preconditioning techniques, including some for nonsymmetric problems. The generalization of these techniques to the multilevel case is a nontrivial task. We emphasize several ways this can be done including classical multigrid methods and a recently proposed algebraic multilevel preconditioning method. Conditions for which the methods have an optimal order of computational complexity are presented.On leave from the Institute of Mathematics, and Center for Informatics and Computer Technology, Bulgarian Academy of Sciences, Sofia, Bulgaria. The research of the second author reported here was partly supported by the Stichting Mathematisch Centrum, Amsterdam.     

Local refinement techniques for elliptic problems on cell-centered grids

Summary Algebraic multilevel analogues of the BEPS preconditioner designed for solving discrete elliptic problems on grids with local refinement are formulated, and bounds on their relative condition numbers, with respect to the composite-grid matrix, are derived. TheV-cycle and, more generally,v-foldV-cycle multilevel BEPS preconditioners are presented and studied. It is proved that for 2-D problems theV-cycle multilevel BEPS is almost optimal, whereas thev-foldV-cycle algebraic multilevel BEPS is optimal under a mild restriction on the composite cell-centered grid. For thev-fold multilevel BEPS, the variational relation between the finite difference matrix and the corresponding matrix on the next-coarser level is not necessarily required. Since they are purely algebraically derived, thev-fold (v>1) multilevel BEPS preconditioners perform without any restrictionson the shape of subregions, unless the refinement is too fast. For theV-cycle BEPS preconditioner (2-D problem), a variational relation between the matrices on two consecutive grids is required, but there is no restriction on the method of refinement on the shape, or on the size of the subdomains.     

Boundaries of right-angled Coxeter groups with manifold nerves

All abstract reflection groups act geometrically on non-positively curved geodesic spaces. Their natural space at infinity, consisting of (bifurcating) infinite geodesic rays emanating from a fixed base point, is called a boundary of the group.We will present a condition on right-angled Coxeter groups under which they have topologically homogeneous boundaries. The condition is that they have a nerve which is a connected closed orientable PL manifold.In the event that the group is generated by the reflections of one of Davis’ exotic open contractible n-manifolds (n?4), the group will have a boundary which is a homogeneous cohomology manifold. This group boundary can then be used to equivariantly Z-compactify the Davis manifold.If the compactified manifold is doubled along the group boundary, one obtains a sphere if n?5. The system of reflections extends naturally to this sphere and can be augmented by a reflection whose fixed point set is the group boundary. It will be shown that the fixed point set of each extended original reflection on the thus formed sphere is a tame codimension-one sphere.     

An inverse eigenvalue problem: ComputingB-stable Runge-Kutta methods having real poles

The implementation of implicit Runge-Kutta methods requires the solution of large sets of nonlinear equations. It is known that on serial machines these costs can be reduced if the stability function of ans-stage method has only ans-fold real pole. Here these so-called singly-implicit Runge-Kutta methods (SIRKs) are constructed utilizing a recent result on eigenvalue assignment by state feedback and a new tridiagonalization, which preserves the entries required by theW-transformation. These two algorithms in conjunction with an unconstrained minimization allow the numerical treatment of a difficult inverse eigenvalue problem. In particular we compute an 8-stage SIRK which is of order 8 andB-stable. This solves a problem posed by Hairer and Wanner a decade ago. Furthermore, we finds-stageB-stable SIRKs (s=6,8) of orders, which are evenL-stable.     

A direct active set algorithm for large sparse quadratic programs with simple bounds

We show how a direct active set method for solving definite and indefinite quadratic programs with simple bounds can be efficiently implemented for large sparse problems. All of the necessary factorizations can be carried out in a static data structure that is set up before the numeric computation begins. The space required for these factorizations is no larger than that required for a single sparse Cholesky factorization of the Hessian of the quadratic. We propose several improvements to this basic algorithm: a new way to find a search direction in the indefinite case that allows us to free more than one variable at a time and a new heuristic method for finding a starting point. These ideas are motivated by the two-norm trust region problem. Additionally, we also show how projection techniques can be used to add several constraints to the active set at each iteration. Our experimental results show that an algorithm with these improvements runs much faster than the basic algorithm for positive definite problems and finds local minima with lower function values for indefinite problems.Research partially supported by the Applied Mathematical Sciences Research Program (KC-04-02) of the Office of Energy Research of the U.S. Department of Energy under grant DE-FG02-86ER25013.A000.     

UTV Tools: Matlab templates for rank-revealing UTV decompositions

We describe a Matlab 5.2 package for computing and modifying certain rank-revealing decompositions that have found widespread use in signal processing and other applications. The package focuses on algorithms for URV and ULV decompositions, collectively known as UTV decompositions. We include algorithms for the ULLV decomposition, which generalizes the ULV decomposition to a pair of matrices. For completeness a few algorithms for computation of the RRQR decomposition are also included. The software in this package can be used as is, or can be considered as templates for specialized implementations on signal processors and similar dedicated hardware platforms. This revised version was published online in June 2006 with corrections to the Cover Date.     

Orthogonal Rational Functions with real coefficients and semiseparable matrices

When one wants to use Orthogonal Rational Functions (ORFs) in system identification or control theory, it is important to be able to avoid complex calculations. In this paper we study ORFs whose numerator and denominator polynomial have real coefficients. These ORFs with real coefficients (RORFs) appear when the poles and the interpolation points appear in complex conjugate pairs, which is a natural condition. Further we deduce that there is a strong connection between RORFs and semiseparable matrices.     

Trigonometric Hermite wavelet approximation for the integral equations of second kind with weakly singular kernel

This paper is concerned with a trigonometric Hermite wavelet Galerkin method for the Fredholm integral equations with weakly singular kernel. The kernel function of this integral equation considered here includes two parts, a weakly singular kernel part and a smooth kernel part. The approximation estimates for the weakly singular kernel function and the smooth part based on the trigonometric Hermite wavelet constructed by E. Quak [Trigonometric wavelets for Hermite interpolation, Math. Comp. 65 (1996) 683–722] are developed. The use of trigonometric Hermite interpolant wavelets for the discretization leads to a circulant block diagonal symmetrical system matrix. It is shown that we only need to compute and store O(N)$\mathrm{O}(N)$ entries for the weakly singular kernel representation matrix with dimensions N²$N^2$ which can reduce the whole computational cost and storage expense. The computational schemes of the resulting matrix elements are provided for the weakly singular kernel function. Furthermore, the convergence analysis is developed for the trigonometric wavelet method in this paper.     

Computing the CS and the generalized singular value decompositions

Summary If the columns of a matrix are orthonormal and it is partitioned into a 2-by-1 block matrix, then the singular value decompositions of the blocks are related. This is the essence of the CS decomposition. The computation of these related SVD's requires some care. Stewart has given an algorithm that uses the LINPACK SVD algorithm together with a Jacobitype clean-up operation on a cross-product matrix. Our technique is equally stable and fast but avoids the cross product matrix. The simplicity of our technique makes it more amenable to parallel computation on systolic-type computer architectures. These developments are of interest because a good way to compute the generalized singular value decomposition of a matrix pair (A, B) is to compute the CS decomposition of a certain orthogonal column matrix related toA andB.The research associated with this paper was partially supported by the Office of Naval Research contract N00014-83-K-0640, USA     

Geometric invariants of spaces with isolated flats

We study those groups that act properly discontinuously, cocompactly, and isometrically on CAT(0) spaces with isolated flats. The groups in question include word hyperbolic CAT(0) groups as well as geometrically finite Kleinian groups and numerous two-dimensional CAT(0) groups. For such a group we show that there is an intrinsic notion of a quasiconvex subgroup which is equivalent to the subgroup being undistorted. We also show that the visual boundary of the CAT(0) space is actually an invariant of the group. More generally, we show that each quasiconvex subgroup of such a group has a canonical limit set which is independent of the choice of overgroup.The main results in this article were established by Gromov and Short in the word hyperbolic setting and do not extend to arbitrary CAT(0) groups.     

A matrix perturbation method for computing the steady-state probability distributions of probabilistic Boolean networks with gene perturbations

Modeling genetic regulatory interactions is an important issue in systems biology. Probabilistic Boolean networks (PBNs) have been proved to be a useful tool for the task. The steady-state probability distribution of a PBN gives important information about the captured genetic network. The computation of the steady-state probability distribution involves the construction of the transition probability matrix of the PBN. The size of the transition probability matrix is 2ⁿ×2ⁿ where n is the number of genes. Although given the number of genes and the perturbation probability in a perturbed PBN, the perturbation matrix is the same for different PBNs, the storage requirement for this matrix is huge if the number of genes is large. Thus an important issue is developing computational methods from the perturbation point of view. In this paper, we analyze and estimate the steady-state probability distribution of a PBN with gene perturbations. We first analyze the perturbation matrix. We then give a perturbation matrix analysis for the captured PBN problem and propose a method for computing the steady-state probability distribution. An approximation method with error analysis is then given for further reducing the computational complexity. Numerical experiments are given to demonstrate the efficiency of the proposed methods.     

Computing projections with LSQR

LSQR uses the Golub-Kahan bidiagonalization process to solve sparse least-squares problems with and without regularization. In some cases, projections of the right-hand side vector are required, rather than the least-squares solution itself. We show that projections may be obtained from the bidiagonalization as linear combinations of (the-oretically) orthogonal vectors. Even the least-squares solution may be obtained from orthogonal vectors, perhaps more accurately than the usual LSQR solution. (However, LSQR has proved equally good in all examples so far.) Presented at the Cornelius Lanczos International Centenary Conference, North Carolina State University, Raleigh, NC, December 1993. Partially supported by Department of Energy grant DE-FG03-92ER25117, National Science Foundation grants DMI-9204208 and DMI-9500668, and Office of Naval Research grants N00014-90-J-1242 and N00014-96-1-0274.     

Extensions of block-projections methods with relaxation parameters to inconsistent and rank-deficient least-squares problems

There exist many classes of block-projections algorithms for approximating solutions of linear least-squares problems. Generally, these methods generate sequences convergent to the minimal norm least-squares solution only for consistent problems. In the inconsistent case, which usually appears in practice because of some approximations or measurements, these sequences do no longer converge to a least-squares solution or they converge to the minimal norm solution of a “perturbed” problem. In the present paper, we overcome this difficulty by constructing extensions for almost all the above classes of block-projections methods. We prove that the sequences generated with these extensions always converge to a least-squares solution and, with a suitable initial approximation, to the minimal norm solution of the problem. Numerical experiments, described in the last section of the paper, confirm the theoretical results obtained.