Two applications of Boolean models

Semantical arguments, based on the completeness theorem for first-order logic, give elegant proofs of purely syntactical results. For instance, for proving a conservativity theorem between two theories, one shows instead that any model of one theory can be extended to a model of the other theory. This method of proof, because of its use of the completeness theorem, is a priori not valid constructively. We show here how to give similar arguments, valid constructively, by using Boolean models. These models are a slight variation of ordinary first-order models, where truth values are now regular ideals of a given Boolean algebra. Two examples are presented: a simple conservativity result and Herbrand's theorem. Received December 5, 1995     

Meeting infinitely many cells of a partition once

We investigate several versions of a cardinal characteristic defined by Frankiewicz. Vojtáš showed , and Blass showed . We show that all the versions coincide and that is greater than or equal to the splitting number. We prove the consistency of and of . Received: 2 October 1996 / Revised version: 22 May 1997     

Relative-error bounds for the LU decomposition via the GTH algorithm

Summary. Recently the author showed that the Grassmann-Taksar-Heyman (GTH) algorithm computes the steady-state distribution of a finite-state Markov chain with low relative error. Here it is shown that the LU decomposition computed in the course of the GTH algorithm also has low relative error. The proof requires a refinement of the methods used in the earlier paper. Received September 2, 1994 / Revised version received July 17, 1995     

Block LU factorizations of M–matrices

Summary. It is well known that any nonsingular M–matrix admits an LU factorization into M–matrices (with L and U lower and upper triangular respectively) and any singular M–matrix is permutation similar to an M–matrix which admits an LU factorization into M–matrices. Varga and Cai establish necessary and sufficient conditions for a singular M–matrix (without permutation) to allow an LU factorization with L nonsingular. We generalize these results in two directions. First, we find necessary and sufficient conditions for the existence of an LU factorization of a singular M-matrix where L and U are both permitted to be singular. Second, we establish the minimal block structure that a block LU factorization of a singular M–matrix can have when L and U are M–matrices. Received November 21, 1994 / Revised version received August 4, 1997     

Symmetric Gaussian elimination for cauchy-type matrices with application to positive definite Toeplitz matrices

The problem of solving linear equations with a Toeplitz matrix appears in many applications. Often is positive definite but ill-conditioned with many small eigenvalues. In this case fast and superfast algorithms may show a very poor behavior or even break down. In recent papers the transformation of a Toeplitz matrix into a Cauchy-type matrix is proposed. The resulting new linear equations can be solved in operations using standard pivoting strategies which leads to very stable fast methods also for ill-conditioned systems. The basic tool is the formulation of Gaussian elimination for matrices with low displacement rank. In this paper, we will transform a Hermitian Toeplitz matrix into a Cauchy-type matrix by applying the Fourier transform. We will prove some useful properties of and formulate a symmetric Gaussian elimination algorithm for positive definite . Using the symmetry and persymmetry of we can reduce the total costs of this algorithm compared with unsymmetric Gaussian elimination. For complex Hermitian , the complexity of the new algorithm is then nearly the same as for the Schur algorithm. Furthermore, it is possible to include some strategies for ill-conditioned positive definite matrices that are well-known in optimization. Numerical examples show that this new algorithm is fast and reliable. Received March 24, 1995 / Revised version received December 13, 1995     

Stability analysis and fast algorithms for triangularization of Toeplitz matrices

Summary. A new algorithm for triangularizing an Toeplitz matrix is presented. The algorithm is based on the previously developed recursive algorithms that exploit the Toeplitz structure and compute each row of the triangular factor via updating and downdating steps. A forward error analysis for this existing recursive algorithm is presented, which allows us to monitor the conditioning of the problem, and use the method of corrected semi-normal equations to obtain higher accuracy for certain ill-conditioned matrices. Numerical experiments show that the new algorithm improves the accuracy significantly while the computational complexity stays in . Received April 30, 1995 / Revised version received February 12, 1996     

Polynomials on the Cauchy circle

Summary. Let be a complex polynomial of degree with and Cauchy radius 1 about the origin. We discuss the order of magnitude of the minimal number such that Previous estimates of are improved to . Some other related properties of these polynomials are also exhibited. Received March 3, 1993     

Hybrid procedures for solving linear systems

Summary. In this paper, we introduce the notion of hybrid procedures for solving a system of linear equations. A hybrid procedure consists in a combination of two arbitrary approximate solutions with coefficients summing up to one. Thus the combination only depends on one parameter whose value is chosen in order to minimize the Euclidean norm of the residual vector obtained by the hybrid procedure. Properties of such procedures are studied in detail. The two approximate solutions which are combined in a hybrid procedure are usually obtained by two iterative methods. Several strategies for combining these two methods together or with the previous iterate of the hybrid procedure itself are discussed and their properties are analyzed. Numerical experiments illustrate the various procedures. Received October 21, 1992/Revised version received May 28, 1993     

Fast verification of solutions of matrix equations

Summary. In this paper, we are concerned with a matrix equation where A is an real matrix and x and b are n-vectors. Assume that an approximate solution is given together with an approximate LU decomposition. We will present fast algorithms for proving nonsingularity of A and for calculating rigorous error bounds for . The emphasis is on rigour of the bounds. The purpose of this paper is to propose different algorithms, the fastest with flops computational cost for the verification step, the same as for the LU decomposition. The presented algorithms exclusively use library routines for LU decomposition and for all other matrix and vector operations. Received June 16, 1999 / Revised version received January 25, 2001 / Published online June 20, 2001     

Numerical solution of a secular equation

Summary. A method is proposed for the solution of a secular equation, arising in modified symmetric eigenvalue problems and in several other areas. This equation has singularities which make the application of standard root-finding methods difficult. In order to solve the equation, a class of transformations of variables is considered, which transform the equation into one for which Newton's method converges from any point in a certain given interval. In addition, the form of the transformed equation suggests a convergence accelerating modification of Newton's method. The same ideas are applied to the secant method and numerical results are presented. Received July 1, 1994     

Pivoting strategies leading to diagonal dominance by rows

Pivoting strategies for Gaussian elimination leading to upper triangular matrices which are diagonally dominant by rows are studied. Forward error analysis of triangular systems whose coefficient matrices are diagonally dominant by rows is performed. We also obtain small bounds of the backward errors for the pivoting strategies mentioned above. Our examples of matrices include H-matrices and some generalizations of diagonally dominant matrices, and scaled partial pivoting for the 1-norm is an example of these pivoting strategies. In the case of an M-matrix, a pivoting strategy of computational complexity is proposed, which satisfies all the results of the paper. Received June 6, 1997 / Revised version received October 27, 1997     

Factorization of analytic functions by means of Koenig's theorem and Toeplitz computations

Summary. By providing a matrix version of Koenig's theorem we reduce the problem of evaluating the coefficients of a monic factor r(z) of degree h of a power series f(z) to that of approximating the first h entries in the first column of the inverse of an Toeplitz matrix in block Hessenberg form for sufficiently large values of n. This matrix is reduced to a band matrix if f(z) is a polynomial. We prove that the factorization problem can be also reduced to solving a matrix equation for an matrix X, where is a matrix power series whose coefficients are Toeplitz matrices. The function is reduced to a matrix polynomial of degree 2 if f(z) is a polynomial of degreeN and . These reductions allow us to devise a suitable algorithm, based on cyclic reduction and on the concept of displacement rank, for generating a sequence of vectors that quadratically converges to the vector having as components the coefficients of the factor r(z). In the case of a polynomial f(z) of degree N, the cost of computing the entries of given is arithmetic operations, where is the cost of solving an Toeplitz-like system. In the case of analytic functions the cost depends on the numerical degree of the power series involved in the computation. From the numerical experiments performed with several test polynomials and power series, the algorithm has shown good numerical properties and promises to be a good candidate for implementing polynomial root-finders based on recursive splitting strategies. Applications to solving spectral factorization problems and Markov chains are also shown. Received September 9, 1998 / Revised version received November 14, 1999 / Published online February 5, 2001     

Numerical solution of constant coefficient linear delay differential equations as abstract Cauchy problems

Summary. In this paper we present an approach for the numerical solution of delay differential equations where , and , different from the classical step-by-step method. We restate (1) as an abstract Cauchy problem and then we discretize it in a system of ordinary differential equations. The scheme of discretization is proved to be convergent. Moreover the asymptotic stability is investigated for two significant classes of asymptotically stable problems (1). Received May 4, 1998 / Revised version received January 25, 1999 / Published online November 17, 1999     

The shrinking principle and the axiom of choice

The axiom of choice is equivalent to the shrinking principle: every indexed cover of a set has a refinement with the same index set which is a partition. A simple and direct proof of this equivalence is given within an elementary fragment of constructive Zermelo–Fraenkel set theory. Variants of the shrinking principle are discussed, and it is related to a similar but different principle formulated by Vaught.     

Dimension de Krull,Nullstellensätze et évaluation dynamique

Résumé. Nous démontrons un Nullstellensatz qui établit une équivalence entre l'existence d'une identité algébrique d'un certain type, d'une part, et l'impossibilité de trouver une suite croissante de variétés irréductibles répondant à certaines contraintes d'autre part. De ce point de vue le Nullstellensatz usuel correspond au cas des variétés réduites à un point. Nous établissons aussi un Nullstellensatz formel du même type, en relation avec les suites croissantes d'idéaux premiers. Un cas particulier important est donné par la notion de suite pseudo régulière, plus générale que la notion de suite régulière. Nous obtenons de cette manière une nouvelle caractérisation de la dimension de Krull d'un anneau : un anneau a une dimension de Krull si et seulement si il existe une suite pseudo régulière de longueur dans l'anneau. Dans les cas où ces résultats peuvent avoir une signification constructive précise, nos preuves y aboutissent constructivement. Nous pensons avoir donné ainsi quelques éléments en vue d'une interprétation constructive de la théorie de la dimension de Krull des anneaux commutatifs. Notre méthode utilise la notion de structure algébrique dynamique introduite dans des articles précédents. Received: 4 October 1999; in final form: 11 October 2000 / Published online: 25 June 2001     

Some remarks on category of the real line

We find a characterization of the covering number , of the real line in terms of trees. We also show that the cofinality of is greater than or equal to for every where ( is the additivity number of the ideal of all Lebesgue measure zero sets) is the least cardinal number k for which the statement: fails. Received: 19 October 1994 / Revised version: 12 December 1996     

The characterizations of a semicircle law by the certain freeness in a C*-probability space

In usual probability theory, various characterizations of the Gaussian law have been obtained. For instance, independence of the sample mean and the sample variance of independently identically distributed random variables characterizes the Gaussian law and the property of remaining independent under rotations characterizes the Gaussian random variables. In this paper, we consider the free analogue of such a kind of characterizations replacing independence by freeness. We show that freeness of the certain pair of the linear form and the quadratic form in freely identically distributed noncommutative random variables, which covers the case for the sample mean and the sample variance, characterizes the semicircle law. Moreover we give the alternative proof for Nica's result that the property of remaining free under rotations characterizes a semicircular system. Our proof is more direct and straightforward one. Received: 12 February 1997 / Revised version: 16 June 1998