An incomplete-factorization preconditioning using repeated red-black ordering

Summary The convergence of the conjugate gradient method for the iterative solution of large systems of linear equations depends on proper preconditioning matrices. We present an efficient incomplete-factorization preconditioning based on a specific, repeated red-black ordering scheme and cyclic reduction. For the Dirichlet model problem, we prove that the condition number increases asymptotically slower with the number of equations than for usual incomplete factorization methods. Numerical results for symmetric and non-symmetric test problems and on locally refined grids demonstrate the performance of this method, especially for large linear systems.     

A hybrid Arnoldi-Faber iterative method for nonsymmetric systems of linear equations

Summary We present here a new hybrid method for the iterative solution of large sparse nonsymmetric systems of linear equations, say of the formAx=b, whereA ^{N, N} , withA nonsingular, andb ^N are given. This hybrid method begins with a limited number of steps of the Arnoldi method to obtain some information on the location of the spectrum ofA, and then switches to a Richardson iterative method based on Faber polynomials. For a polygonal domain, the Faber polynomials can be constructed recursively from the parameters in the Schwarz-Christoffel mapping function. In four specific numerical examples of non-normal matrices, we show that this hybrid algorithm converges quite well and is approximately as fast or faster than the hybrid GMRES or restarted versions of the GMRES algorithm. It is, however, sensitive (as other hybrid methods also are) to the amount of information on the spectrum ofA acquired during the first (Arnoldi) phase of this procedure.     

An algorithm for best approximate solutions ofAx=b with a smooth strictly convex norm

Summary In this paper, overdetermined systems ofm linear equations inn unknowns are considered. With ^m equipped with a smooth strictly convex norm, ·, an iterative algorithm for finding the best approximate solution of the linear system which minimizes the ·-error is given. The convergence of the algorithm is established and numerical results are presented for the case when · is anl _p norm, 1<p<.Portions of this paper are taken from the author's Ph.D. thesis at Michigan State University     

Limitations of the L-curve method in ill-posed problems

This paper considers the Tikhonov regularization method with the regularization parameter chosen by the so-called L-curve criterion. An infinite dimensional example is constructed for which the selected regularization parameter vanishes too rapidly as the noise to signal ratio in the data goes to zero. As a consequence the computed reconstructions do not converge to the true solution. Numerical examples are given to show that similar phenomena can be observed under more general assumptions in discrete ill-posed problems provided the exact solution of the problem is smooth.This work was partially supported by NATO grant CRG 930044.     

Characterization of regular singular linear systems of difference equations

This paper deals with linear systems of difference equations whose coefficients admit generalized factorial series representations atz=. We are concerned with the behavior of solutions near the pointz= (the only fixed singularity for difference equations). It is important to know whether a system of linear difference equations has a regular singularity or an irregular singularity. To a given system () we can assign a number , called the Moser's invariant of (), so that the system is regular singular if and only if 1. We shall develop an algorithm, implementable in a computer algebra system, which reduces in a finite number of steps the system of difference equations to an irreducible form. The computation ot the number can be done explicitly from this irreducible form.     

Stability of Systems of Functional Differential Equations Containing a Small Parameter

New results on the stability of functional differential equations of the delayed type with a small parameter are reported. The right-hand side of the investigated system is assumed to satisfy Carathéodory-type conditions for the existence of a solution of the initial-value problem and to be globally continuous with respect to the parameter at the point . Under these assumptions the results can be used to investigate functional differential equations with rapidly oscillating coefficients. The concept of -stability is defined, and sufficient conditions for -stability are formulated in terms of Lyapunov-type functionals.     

Monodromy-data parameterization of spaces of local solutions of integrable reductions of Einstein’s field equations

We show that for the fields depending on only two of the four space-time coordinates, the spaces of local solutions of various integrable reductions of Einsteins field equations are the subspaces of the spaces of local solutions of the null-curvature equations selected by universal (i.e., solution-independent conditions imposed on the canonical (Jordan) forms of the desired matrix variables. Each of these spaces of solutions can be parameterized by a finite set of holomorphic functions of the spectral parameter, which can be interpreted as a complete set of the monodromy data on the spectral plane of the fundamental solutions of associated linear systems. We show that both the direct and inverse problems of such a map, i.e., the problem of finding the monodromy data for any local solution of the null-curvature equations for the given Jordan forms and also of proving the existence and uniqueness of such a solution for arbitrary monodromy data, can be solved unambiguously (the monodromy transform). We derive the linear singular integral equations solving the inverse problem and determine the explicit forms of the monodromy data corresponding to the spaces of solutions of Einsteins field equations.__________Translated from Teoreticheskaya i Matematicheskaya Fizika, Vol. 143, No. 2, pp. 278–304, May, 2005     

Discrete Series Characters for GL(n, q)

The discrete series characters of the finite general linear group GL(n, q) are expressed as uniquely defined integral linear combinations of characters induced from linear characters on certain subgroups Hd, n of GL(n, q). The coefficients in these linear combinations are determined (for all n, q) by a family of polynomials r(T) Z[T] indexed by the set of all partitions .     

A chance-constrained programming algorithm

This paper describes a new algorithm solving the deterministic equivalents of chance-constrained problems where the random variables are normally distributed and independent of each other. In this method nonlinear chance-constraints are first replaced by uniformly tighter linear constraints. The resulting linear programming problem is solved by a standard simplex method. The linear programming problem is then revised using the solution data and solved again until the stopping rule of the algorithm terminates the process. It is proved that the algorithm converges and that the solution found is the -optimal solution of the chance-constrained programming problem.The computational experience of the algorithm is reported. The algorithm is efficient if the random variables are distributed independently of each other and if they number less than two hundred. The computing system is called CHAPS, i.e. Chance-ConstrainedProgrammingSystem.     

Büschel linearer Abbildungen

If , , are linear mappings out of a projective space (P,G) into a projective space (P', G') and , then is said to belong to the pencil <,<> of linear mappings spanned by and if in the main (x), (x), (x) are collinear for all x P. We give some sufficient conditions for x P and , , such that (x) is uniquely determined by giving, and (z), z P.

---

---

Herrn Prof. Dr.Helmut Karzel zum 60. Geburtstag gewidmet     

A New Integral Equation Form of Integrable Reductions of the Einstein Equations

We further develop the monodromy transformation method for analyzing hyperbolic and elliptic integrable reductions of the Einstein equations. The compatibility conditions for alternative representations of solutions of the associated linear systems with a spectral parameter in terms of a pair of dressing (scattering) matrices yield a new set of linear (quasi-Fredholm) integral equations that are equivalent to the symmetry-reduced Einstein equations. In contrast to the previously derived singular integral equations constructed using conserved (nonevolving) monodromy data for fundamental solutions of the associated linear systems, the scalar kernels of the new equations involve functional parameters of a different type, the evolving (dynamic) monodromy data for scattering matrices. In the context of the Goursat problem, these data are completely determined for hyperbolic reductions by the characteristic initial data for the fields. The field components are expressed in quadratures in terms of solutions of the new integral equations.     

An Adaptive Greedy Algorithm for Solving Large RBF Collocation Problems

The solution of operator equations with radial basis functions by collocation in scattered points leads to large linear systems which often are nonsparse and ill-conditioned. But one can try to use only a subset of the data for the actual collocation, leaving the rest of the data points for error checking. This amounts to finding sparse approximate solutions of general linear systems arising from collocation. This contribution proposes an adaptive greedy method with proven (but slow) linear convergence to the full solution of the collocation equations. The collocation matrix need not be stored, and the progress of the method can be controlled by a variety of parameters. Some numerical examples are given.     

On Infinite Systems of Linear Autonomous and Nonautonomous Stochastic Equations

The solvability of autonomous and nonautonomous stochastic linear differential equations in is studied. The existence of strong continuous (L^p-continuous) solutions of autonomous linear stochastic differential equations in with continuous (L^p-continuous) right-hand sides is proved. Uniqueness conditions are obtained. We give examples showing that both deterministic and stochastic linear nonautonomous differential equations with the same operator in may fail to have a solution. We also establish existence and uniqueness conditions for nonautonomous equations.     

Midpoint collocation for Cauchy singular integral equations

Summary A Cauchy singular integral equation on a smooth closed curve may be solved numerically using continuous piecewise linear functions and collocation at the midpoints of the underlying grid. Even if the grid is non-uniform, suboptimal rates of convergence are proved using a discrete maximum principle for a modified form of the collocation equations. The same techniques prove negative norm estimates when midpoint collocation is used to determine piecewise constant approximations to the solution of first kind equations with the logarithmic potential.This work was supported by the Australian Research Council through the program grant Numerical analysis for integrals, integral equations and boundary value problems     

Maximal inequalities,convexity inequality,and their duality. II

, , . . . [1], , . , , ., , L logL. , , . . . . [5]. , .     

On the admissibility of function spaces of typeB p,q s andF p,q s,and boundary value problems for non-linear partial differential equations

u=f(x)+S(u), S — , u-G(u), G — . B _p,q ^s () -F _p,q ^s (). R _n — . — . _p,q ^s F _p,q ^s .     

Borel fibrations and G-spaces

Considering discrete groups G only, we present an elementary proof of the familiar equivalence of the category of G-spaces (with maps equivariant up to homotopy) and the category of Borel fibrations over BG.     

Extension of functions,which are traces of functions belonging to 249-01249-01249-01on an arbitrary subset of the line

( , k) , ER f(x) f(x)H _k (R) (k2— ,=(t) — k- ). f(x) E (t).     

An algebraic test forA 0-stability

The stability of a large class of numerical methods to solve initial value problems of ordinary differential equations is governed by a two-variable polynomial (,) when the method is applied toy'=qy. Here=hq, whereh is the stepsize. This class of methods includes Runge-Kutta methods, linear multistep methods, predictor-corrector methods, composite multistep methods and linear multistep-multiderivative methods. An algebraic test is given to determineA ₀-stability of such methods in a finite number of operations (additions, subtractions, multiplications and divisions). It is shown that the number of multiplications and divisions is of order 1/8²(⁴ +O(³)), where is the degree of (,) in the variable and the degree in the variable. The test has been implemented for multistep-multiderivative methods in a symbol manipulation language. For Enright's second derivativek-step methods it is proved that the methods areA ₀-stable if and only ifk<8.Supported by the Swiss National Foundation Grant No. 82.524.077. On leave from Institute of Mathematics, Ruhr-University Bochum, D-463 Germany.     

Numerical stability of GMRES

The Generalized Minimal Residual Method (GMRES) is one of the significant methods for solving linear algebraic systems with nonsymmetric matrices. It minimizes the norm of the residual on the linear variety determined by the initial residual and then-th Krylov residual subspace and is therefore optimal, with respect to the size of the residual, in the class of Krylov subspace methods. One possible way of computing the GMRES approximations is based on constructing the orthonormal basis of the Krylov subspaces (Arnoldi basis) and then solving the transformed least squares problem. This paper studies the numerical stability of such formulations of GMRES. Our approach is based on the Arnoldi recurrence for the actually, i.e., in finite precision arithmetic, computed quantities. We consider the Householder (HHA), iterated modified Gram-Schmidt (IMGSA), and iterated classical Gram-Schmidt (ICGSA) implementations. Under the obvious assumption on the numerical nonsingularity of the system matrix, the HHA implementation of GMRES is proved backward stable in the normwise sense. That is, the backward error for the approximation is proportional to machine precision . Additionally, it is shown that in most cases the norm of the residual computed from the transformed least squares problem (Arnoldi residual) gives a good estimate of the true residual norm, until the true residual norm has reached the level A x.This work was supported by NSF contract Int921824.