Finiteness obstructions and Euler characteristics of categories

We introduce notions of finiteness obstruction, Euler characteristic, L²-Euler characteristic, and Möbius inversion for wide classes of categories. The finiteness obstruction of a category Γ of type (FPR) is a class in the projective class group K₀(RΓ); the functorial Euler characteristic and functorial L²-Euler characteristic are respectively its RΓ-rank and L²-rank. We also extend the second author's K-theoretic Möbius inversion from finite categories to quasi-finite categories. Our main example is the proper orbit category, for which these invariants are established notions in the geometry and topology of classifying spaces for proper group actions. Baez and Dolan's groupoid cardinality and Leinster's Euler characteristic are special cases of the L²-Euler characteristic. Some of Leinster's results on Möbius–Rota inversion are special cases of the K-theoretic Möbius inversion.     

On structure-oriented hybrid two-stage iteration methods for the large and sparse blocked system of linear equations

In this paper, we first present a class of structure-oriented hybrid two-stage iteration methods for solving the large and sparse blocked system of linear equations, as well as the saddle point problem as a special case. And the new methods converge to the solution under suitable restrictions, for instance, when the coefficient matrix is positive stable matrix generally. Numerical experiments for a model generalized saddle point problem are given, and the results show that our new methods are feasible and efficient, and converge faster than the Classical Uzawa Method.     

More on the weeks method for the numerical inversion of the Laplace transform

Summary Most of the numerical methods for the inversion of the Laplace Transform require the values of several incidental parameters. Generally, these parameters are related to the properties of the algorithm and to the analytical properties of the Laplace Transform functionF(s).One of the most promising inversion methods, the Weeks methods, computes the inverse functionf(t) as a series expansion of Laguerre functions involving two parameters, usually denoted by andb. In this paper we characterize the optimal choiceb _opt ofb, which maximizes the rate of convergence of the series, in terms of the location of the singularities ofF(s).     

On fundamental skew distributions

A new class of multivariate skew-normal distributions, fundamental skew-normal distributions and their canonical version, is developed. It contains the product of independent univariate skew-normal distributions as a special case. Stochastic representations and other main properties of the associated distribution theory of linear and quadratic forms are considered. A unified procedure for extending this class to other families of skew distributions such as the fundamental skew-symmetric, fundamental skew-elliptical, and fundamental skew-spherical class of distributions is also discussed.     

Efficient Software-Implementation of Finite Fields with Applications to Cryptography

In this work, we present a survey of efficient techniques for software implementation of finite field arithmetic especially suitable for cryptographic applications. We discuss different algorithms for three types of finite fields and their special versions popularly used in cryptography: Binary fields, prime fields and extension fields. Implementation details of the algorithms for field addition/subtraction, field multiplication, field reduction and field inversion for each of these fields are discussed in detail. The efficiency of these different algorithms depends largely on the underlying micro-processor architecture. Therefore, a careful choice of the appropriate set of algorithms has to be made for a software implementation depending on the performance requirements and available resources.     

Matching is as easy as matrix inversion

We present a new algorithm for finding a maximum matching in a general graph. The special feature of our algorithm is that its only computationally non-trivial step is the inversion of a single integer matrix. Since this step can be parallelized, we get a simple parallel (RNC ²) algorithm. At the heart of our algorithm lies a probabilistic lemma, the isolating lemma. We show other applications of this lemma to parallel computation and randomized reductions. Work done while visiting MSRI, Berkeley, in Fall 1985. Supported by NSF Grant BCR 85-03611 and an IBM Faculty Development Award.     

Biorthogonal decompositions of the Radon transform

Summary. The concept of singular value decompositions is a valuable tool in the examination of ill-posed inverse problems such as the inversion of the Radon transform. A singular value decomposition depends on the determination of suitable orthogonal systems of eigenfunctions of the operators , . In this paper we consider a new approach which generalizes this concept. By application of biorthogonal instead of orthogonal functions we are able to apply a larger class of function sets in order to account for the structure of the eigenfunction spaces. Although it is preferable to use eigenfunctions it is still possible to consider biorthogonal function systems which are not eigenfunctions of the operator. With respect to the Radon transform for functions with support in the unit ball we apply the system of Appell polynomials which is a natural generalization of the univariate system of Gegenbauer (ultraspherical) polynomials to the multivariate case. The corresponding biorthogonal decompositions show some advantages in comparison with the known singular value decompositions. Vice versa by application of our decompositions we are able to prove new properties of the Appell polynomials. Received October 19, 1993     

Characterizing joint distributions of random sets by multivariate capacities

By the Choquet theorem, distributions of random closed sets can be characterized by a certain class of set functions called capacity functionals. In this paper a generalization to the multivariate case is presented, that is, it is proved that the joint distribution of finitely many random sets can be characterized by a multivariate set function being completely alternating in each component, or alternatively, by a capacity functional defined on complements of cylindrical sets. For the special case of finite spaces a multivariate version of the Moebius inversion formula is derived. Furthermore, we use this result to formulate an existence theorem for set-valued stochastic processes.     

On general hemiequilibrium problems

In this paper, we introduce and analyze a new class of equilibrium problems known as general hemiequilibrium problems. It is shown that this class includes hemiequilibrium problems, hemivariational inequalities and complementarity problems as special cases. We use the auxiliary principle techniques to suggest some iterative-type methods for solving multivalued hemiequilibrium problems. We also analyze the convergence analysis of these new iterative methods under some mild conditions. As special cases, we obtain several new and known methods for solving variational inequalities and equilibrium problems.     

Fast inversion of Chebyshev--Vandermonde matrices

Summary. This paper contains two fast algorithms for inversion of Chebyshev--Vandermonde matrices of the first and second kind. They are based on special representations of the Bezoutians of Chebyshev polynomials of both kinds. The paper also contains the results of numerical experiments which show that the algorithms proposed here are not only much faster, but also more stable than other algorithms available. It is also efficient to use the above two algorithms for solving Chebyshev--Vandermode systems of equations with preprocessing. Received January 23, 1993/Revised version received May 21, 1993     

Inversion of polynomial and rational matrices

The inversion of polynomial and rational matrices is considered. For regular matrices, three algorithms for computing the inverse matrix in a factored form are proposed. For singular matrices, algorithms of constructing pseudoinverse matrices are considered. The algorithms of inversion of rational matrices are based on the minimal factorization which reduces the problem to the inversion of polynomial matrices. A class of special polynomial matrices is regarded whose inverse matrices are also polynomial matrices. Inversion algorithms are applied to the solution of systems with polynomial and rational matrices. Bibliography: 3 titles. Translated by V. N. Kublanovskaya. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 202, 1992, pp. 97–109.     

Numerical accuracy of real inversion formulas for the Laplace transform

In this article, we investigate and compare a number of real inversion formulas for the Laplace transform. The focus is on the accuracy and applicability of the formulas for numerical inversion. In this contribution, we study the performance of the formulas for measures concentrated on a positive half-line to continue with measures on an arbitrary half-line. As our trial measure concentrated on a positive half-line, we take the broad Gamma probability distribution family.     

Ringel duality and Auslander–Dlab–Ringel algebras

We introduce a new class of quasi-hereditary algebras, containing in particular the Auslander–Dlab–Ringel (ADR) algebras. We show that this new class of algebras is preserved under Ringel duality, which determines in particular explicitly the Ringel dual of any ADR algebra. As a special case of our theory, it follows that, under very restrictive conditions, an ADR algebra is Ringel dual to another one. The latter provides an alternative proof for a recent result of Conde and Erdmann, and places it in a more general setting.     

An adaptive Newton algorithm based on numerical inversion: Regularization as postconditioner

Summary We examine a class of approximate inversion processes, satisfying estimates similar to those defined by finite element or truncated spectral approximations; these are to be used as approximate right inverses for Newton iteration methods. When viewed at the operator level, these approximations introduce a defect, or loss of derivatives, of order one or more. Regularization is introduced as a form of defect correction. A superlinearly convergent, approximate Newton iteration is thereby obtained by using the numerical inversion adaptively, i.e., with spectral or grid parameters correlated to the magnitude of the current residual in an intermediate norm defined by the defect. This adaptive choice makes possible ascribing an order to the convergent process, and this is identified as essentially optimal for elliptic problems, relative to complexity. The design of the algorithm involves multi-parameter selection, thereby opening up interesting avenues for elliptic problems, relative to complexity. This applies also to the regularization which may be carried out in the Fourier transform space, and is band-limited in the language of Whittaker-Shannon sampling theory. The norms employed in the analysis are of Hölder space type; the iteration is an adaptation of Nash-Moser interation; and, the complexity studies use Vitukin's theory of information processing. Computational experience is described in the final section.Research supported by National Science Foundation grant MCS-8218041. This is the second part of work in progress during the author's visit to the Institute for Mathematics and its Applications, University of Minnesota, Minneapolis, USA     

Relativistic Kronig-Penney-type Hamiltonians

The relativistic Kronig-Penney model is extended to a wide class of point interactions introduced in the nonrelativisfic case by Paul Chernoff and the author. A generalized Kronig-Penney relation, which converges to the standard Kronig-Penney relation in the nonrelativistic limit, is shown to determine the spectrum of the corresponding Hamiltonian. Several examples are considered, including the well-known special cases of electrostatic and Lorentz scalar point interactions, as well as several new solvable models.     

Displacement structure approach to q-adic polynomial-Vandermonde and related matrices

In the present paper a new class of the so-called q-adic polynomial-Vandermonde-like matrices over an arbitrary non-algebraically closed field is introduced. This class generalizes both the simple and the confluent polynomial-Vandermonde-like matrices over the complex field, and the q-adic Vandermonde and the q-adic Chebyshev-Vandermonde-like matrices studied earlier by different authors. Three kinds of displacement structures and two kinds of fast inversion formulas are obtained for this class of matrices by using displacement structure matrix method, which generalize the corresponding results of the polynomial-Vandermonde-like and the q-adic Vandermonde-like matrices.     

A note on error expressions for reflected and averaged implicit Runge-Kutta methods

In addition to their usefulness in the numerical solution of initial value ODE's, the implicit Runge-Kutta (IRK) methods are also important for the solution of two-point boundary value problems. Recently, several classes of modified IRK methods which improve significantly on the efficiency of the standard IRK methods in this application have been presented. One such class is the Averaged IRK methods; a member of the class is obtained by applying an averaging operation to a non-symmetric IRK method and its reflection. In this paper we investigate the forms of the error expressions for reflected and averaged IRK methods. Our first result relates the expression for the local error of the reflected method to that of the original method. The main result of this paper relates the error expression of an averaged method to that of the method upon which it is based. We apply these results to show that for each member of the class of the averaged methods, there exists an embedded lower order method which can be used for error estimation, in a formula-pair fashion.This work was supported by the Natural Science and Engineering Research Council of Canada.     

OnM-functions and nonlinear relaxation methods

Globally convergent nonlinear relaxation methods are considered for a class of nonlinear boundary value problems (BVPs), where the discretizations are continuousM-functions.It is shown that the equations with one variable occurring in the nonlinear relaxation methods can always be solved by Newton's method combined with the Bisection method. The nonlinear relaxation methods are used to get an initial approximation in the domain of attraction of Newton's method. Numerical examples are given.