Search

For a block upper triangular matrix, a necessary and sufficient condition has been given to let it be the sum of block upper rectangular matrices satisfying certain rank constraints; see [12] . The proof involves elements from Integer Programming (totally unimodular systems of equations playing a role in particular) and employs Farkas' Lemma. The linear space of block upper triangular matrices can be viewed as being determined by a special pattern of zeros. The present paper is concerned with the question whether the decomposition result can be extended to situations where other, less restrictive, zero patterns play a role. It is shown that such generalizations do indeed hold for certain directed graphs determining the pattern of zeros. The graphs in question are what will be called L -free. This notion is akin to other graph theoretical concepts available in the literature, among them the one of being N -free in the sense of [16] .

The Gauss-Seidel and Kaczmarz methods are two classic iteration methods for solving systems of linear equations, which operate in column and row spaces, respectively. Utilizing the connections between these two methods and imitating the exact analysis of the mean-squared error for the randomized Kaczmarz method, we conduct an exact closed-form formula for the mean-squared residual of the iterate generated by the randomized Gauss-Seidel method. Based on this new formula, we further estimate an upper bound for the convergence rate of the randomized Gauss-Seidel method. Theoretical analysis and numerical experiments show that this bound measurably improves the existing ones. Moreover, these theoretical results are also extended to the more general extrapolated randomized Gauss-Seidel method.

For solving large sparse, overdetermined, and inconsistent system of linear equations by iteration methods, by further reconstructing the randomized extended Kaczmarz method proposed by Zouzias and Freris in 2013 (SIAM J. Matrix Anal. Appl. 34 (2013), 773–793), we propose a partially randomized extended Kaczmarz method. When the coefficient matrix is assumed to be of full column rank, we prove the convergence and derive an upper bound for the expected convergence rate of the partially randomized extended Kaczmarz method. This bound could be smaller than that of the randomized extended Kaczmarz method under certain conditions. Moreover, with numerical results we show that the partially randomized extended Kaczmarz method can be much more effective than the randomized extended Kaczmarz method.

For consistent system of linear equations with the coefficient matrix being flat, we conduct an exact closed-form formula for the mean squared error of the iterate generated by the randomized Kaczmarz method, which completes the existing closed-form formula derived only for the tall coefficient matrix. Based upon these formulas, we further estimate an upper bound for the convergence rate of the randomized Kaczmarz method. Both theoretical analysis and numerical experiments demonstrate that this bound can significantly improve the existing ones.

Computational procedures for the stationary probability distribution, the group inverse of the Markovian kernel and the mean first passage times of an irreducible Markov chain, are developed using perturbations. The derivation of these expressions involves the solution of systems of linear equations and, structurally, inevitably the inverses of matrices. By using a perturbation technique, starting from a simple base where no such derivations are formally required, we update a sequence of matrices, formed by linking the solution procedures via generalized matrix inverses and utilising matrix and vector multiplications. Six different algorithms are given, some modifications are discussed, and numerical comparisons made using a test example. The derivations are based upon the ideas outlined in Hunter, J.J., The computation of stationary distributions of Markov chains through perturbations, Journal of Applied Mathematics and Stochastic Analysis, 4, 29-46, (1991)., Comment: 23 pages

We consider a problem of determining the component-wise distance (called the radius) of a linear system of equations or inequalities to a system that is either solvable or unsolvable. We propose explicit characterization of these radii and show relations between them. Then the radii are classified in the polynomial vs. NP-hard manner. We also present a generalization to an arbitrary linear system consisting from both equations and inequalities with both free and nonnegative variables. Eventually, we extend the concept of the component-wise distance to a non-uniform one.

In this paper, a non-modulus linear method for solving the linear complementarity problem is established by using the sign patterns of the solution of the equivalent modulus equation. In the proposed method the efficient numerical algorithms for solving the linear equations can be applied to the large sparse problems. Numerical examples show that the new method is valid.

Basing on recent results on the stability of collocation methods applied to Cauchy singular integral equations with additional fixed singularities we give necessary and sufficient conditions for the stability of collocation–quadrature methods for such equations. These methods have the advantage that the respective system of equations has a very simple structure and allows to apply fast summation methods which results in a fast algorithm with O ( n log ⁡ n ) complexity. We present numerical results of the application of the proposed collocation–quadrature methods to the notched half plane problem of two-dimensional elasticity theory.

In this paper, we develop finite-time stability theory for linear differential-algebraic equations with delay. Based on the Lyapunov-like functional method, new delay-dependent sufficient conditions such that the system is regular, impulse-free and robustly finite-time stable are developed in terms of solutions of some linear matrix inequalities. A numerical example is given to illustrate the effectiveness of the proposed result.

By using Moreau's decomposition theorem for projecting onto cones, the problem of projecting onto a simplicial cone is reduced to finding the unique solution of a nonsmooth system of equations. It is shown that Picard's method applied to the system of equations associated with the problem of projecting onto a simplicial cone generates a sequence that converges linearly to the solution of the system. Numerical experiments are presented making the comparison between Picard's and semi-smooth Newton's methods to solve the nonsmooth system associated with the problem of projecting a point onto a simplicial cone.

H-matrices (matrices whose comparison matrix is an M-matrix) are well studied in matrix theory and have numerous applications, e.g., linear complementarity problems and iterative methods for solving systems of linear equations. In this article we establish some properties of their tensor counterparts: strong H -tensors and (general) H -tensors.

The extinction probability of the Markovian Binary Tree (MBT) is the minimal nonnegative solution of a Quadratic Vector Equation (QVE). In this paper, we present a perturbation analysis for the extinction probability of a supercritical MBT. We derive a perturbation bound for the minimal nonnegative solution of the QVE, which is a bound on the difference between the solutions of two nearby equations in terms of the perturbation magnitude. A posteriori error bound is also given, which is a bound on the distance between an approximate solution and the real solution, in terms of the residual of the approximate solution. Numerical experiments show that these bounds are fairly sharp.

We study in an unified fashion several quadratic vector and matrix equations with nonnegativity hypotheses. Specific cases of such problems (QBD equations, nonsymmetric algebraic Riccati equations, Lu's simple equation, Markovian binary trees equations) have been studied extensively in the past by several authors. Many of the results appearing here have already been proved for one or more of the single instances of the problems, resorting to specific characteristics of the problem. In some cases the proofs we present here are mere rewriting of the original proofs with a little change of notation to adapt them to our framework, but in some cases we are effectively able to remove some hypotheses and generalize the results by abstracting the specific aspects of each problem., Comment: Revised version

This paper investigates the standard orthogonal vectors in semilinear spaces of n -dimensional vectors over commutative zerosumfree semirings. First, we discuss some characterizations of standard orthogonal vectors. Then as applications, we obtain some necessary and sufficient conditions that a set of vectors is a basis of a semilinear subspace which is generated by standard orthogonal vectors, prove that a set of linearly independent nonstandard orthogonal vectors cannot be orthogonalized if it has at least two nonzero vectors, and show that the analog of the Kronecker–Capelli theorem is valid for systems of equations.

In this paper, we shall deal with solvability of interval systems of linear equations in max-plus algebra. Max-plus algebra is an algebraic structure in which classical addition and multiplication are replaced by ⊕ and ⊗ , where a ⊕ b = max { a , b } , a ⊗ b = a + b . The notation A ⊗ x = b represents an interval system of linear equations, where A = 〈 A , A ¯ 〉 , b = 〈 b , b ¯ 〉 are given interval matrix and interval vector, respectively, and a solution is from a given interval vector x = 〈 x , x ¯ 〉 . We can define several types of solvability of interval systems. In this paper, we define six types of solvability of interval max-plus systems of linear equations and give necessary and sufficient conditions for them.

It is known that the max-algebraic powers Ar of a nonnegative irreducible matrix are ultimately periodic. This leads to the concept of attraction cone Attr(A, t), by which we mean the solution set of a two-sided system λt(A)Ar⊗x=Ar+t⊗x, where r is any integer after the periodicity transient T(A) and λ(A) is the maximum cycle geometric mean of A. A question which this paper answers, is how to describe Attr(A,t) by a concise system of equations without knowing T(A). This study requires knowledge of certain structures and symmetries of periodic max-algebraic powers, which are also described. We also consider extremals of attraction cones in a special case, and address the complexity of computing the coefficients of the system which describes attraction cone.

For square, semipositive matrices A ( Ax > 0 for some x > 0 ), two (nonnegative) equilibrants e ( A ) and E ( A ) are defined. Our primary goal is to develop theory from which each may be calculated. To this end, the collection of semipositive matrices is partitioned into three subclasses for each equilibrant, and a connection to those matrices that are scalable to doubly stochastic matrices is made. In the process a certain matrix/vector equation that is related to scalability of a matrix to one with line sums 1 is derived and discussed.

Our randomized preprocessing enables pivoting-free and orthogonalization-free solution of homogeneous linear systems of equations. In the case of Toeplitz inputs, we decrease the estimated solution time from quadratic to nearly linear, and our tests show dramatic decrease of the CPU time as well. We prove numerical stability of our approach and extend it to solving nonsingular linear systems, inversion and generalized (Moore–Penrose) inversion of general and structured matrices by means of Newton’s iteration, approximation of a matrix by a nearby matrix that has a smaller rank or a smaller displacement rank, matrix eigen-solving, and root-finding for polynomial and secular equations and for polynomial systems of equations. Some by-products and extensions of our study can be of independent technical intersest, e.g., our extensions of the Sherman–Morrison–Woodbury formula for matrix inversion, our estimates for the condition number of randomized matrix products, and preprocessing via augmentation.

An explicit solution is given for the system of linear equations E φ E t = φ ′ , where φ , φ ′ are alternating matrices of Pfaffian 1, which at most differ in their first row and column, and E is of the form ∏ i = 2 2 r E 1 i ( x i ) . If v , v ′ , w ∈ R r + 1 with 〈 v , w 〉 = 1 = 〈 v ′ , w 〉 then a sequence of Cohn transforms with respect to (the fixed) w which takes ( v , w ) to ( v ′ , w ) is prescribed.

Hensel’s lifting modulo a prime q is a customary means of the solution of an integer or rational linear system of equations. In combination with some effective numerical algorithms this technique enables solution in nearly optimal time in the case of most popular structured inputs. Practically one can further benefit from choosing q = 2 v for a proper positive integer v and performing binary computations within the computer precision. If the input matrix becomes singular because of the reduction modulo q , then the approach fails. For larger integers q and random integer input matrices, however, such degeneration occurs rarely according to the analysis by Brent and McKay 1987. Based on distinct techniques we show that degeneration also occurs rarely for random integer matrices with all most popular structures such as the Toeplitz, Hankel, band and rank (quasiseparable) structures. Furthermore with random small-rank modifications of an input matrix we have good chances to overcome degeneration, safely solve the new linear system, and recover the solution of the original one. The results of our extensive tests support our formal analysis.

A matrix A ∈ R n × n is called a bisymmetric matrix if its elements a i , j satisfy the properties a i , j = a j , i and a i , j = a n - j + 1 , n - i + 1 for 1 ⩽ i , j ⩽ n . This paper considers least squares solutions to the matrix equation AX = B for A under a central principal submatrix constraint and the optimal approximation. A central principal submatrix is a submatrix obtained by deleting the same number of rows and columns in edges of a given matrix. We first discuss the specified structure of bisymmetric matrices and their central principal submatrices. Then we give some necessary and sufficient conditions for the solvability of the least squares problem, and derive the general representation of the solutions. Moreover, we also obtain the expression of the solution to the corresponding optimal approximation problem.

A simple method is proposed to find the orthogonal projection of a given point to the solution set of a system of linear equations. This is also a direct method for solving systems of linear equations. The output of the method is either the projection or inconsistency of the system. Moreover, in the process also linearly dependent equations are recognized. This paper is constrained for giving theoretical foundations, computational complexity and some numerical experiments with dense matrices although the method allows to employ sparsity. The raw method could not compete with best software packages in solving linear equations for general matrices, but it was competitive in finding projections for matrices with small number of rows relative to the number of columns.

We consider the numerical solution of linear systems arising from the discretization of the electric field integral equation (EFIE). For some geometries the associated matrix can be poorly conditioned making the use of a preconditioner mandatory to obtain convergence. The electromagnetic scattering problem is here solved by means of a preconditioned GMRES in the context of the multilevel fast multipole method (MLFMM). The novelty of this work is the construction of an approximate hierarchically semiseparable (HSS) representation of the near-field matrix, the part of the matrix capturing interactions among nearby groups in the MLFMM, as preconditioner for the GMRES iterations. As experience shows, the efficiency of an ILU preconditioning for such systems essentially depends on a sufficient fill-in, which apparently sacrifices the sparsity of the near-field matrix. In the light of this experience we propose a multilevel near-field matrix and its corresponding HSS representation as a hierarchical preconditioner in order to substantially reduce the number of iterations in the solution of the resulting system of equations.

Different kinds of nonlinear matrix equations are analyzed and their interplay with certain structured matrices is pointed out. By using the point of view and the tools of structured linear algebra, both theoretical results and numerical methods are derived for solving different classes of nonlinear matrix equations.

The main goal of this paper consists in expressing the solution of a Stein equation in terms of the Fisher information matrix (FIM) of a scalar ARMAX process. A condition for expressing the FIM in terms of a solution to a Stein equation is also set forth. Such interconnections can be derived when a companion matrix with eigenvalues equal to the roots of an appropriate polynomial associated with the ARMAX process is inserted in the Stein equation. The case of algebraic multiplicity greater than or equal to one is studied. The FIM and the corresponding solution to Stein’s equation are presented as solutions to systems of linear equations. The interconnections are obtained by using the common particular solution of these systems. The kernels of the structured coefficient matrices are described as well as some right inverses. This enables us to find a solution to the newly obtained linear system of equations.

Let a ⊕ b =max( a , b ), a ⊗ b = a + b for a,b∈ R := R ∪{−∞} . By max-algebra we understand the analogue of linear algebra developed for the pair of operations (⊕,⊗) extended to matrices and vectors. Max-algebra, which has been studied for more than 40 years, is an attractive way of describing a class of nonlinear problems appearing for instance in machine-scheduling, information technology and discrete-event dynamic systems. This paper focuses on presenting a number of links between basic max-algebraic problems like systems of linear equations, eigenvalue–eigenvector problem, linear independence, regularity and characteristic polynomial on one hand and combinatorial or combinatorial optimisation problems on the other hand. This indicates that max-algebra may be regarded as a linear-algebraic encoding of a class of combinatorial problems. The paper is intended for wider readership including researchers not familiar with max-algebra.

Given a set S of linear relations (equations and/or inequalities) among n variables, the problem of solving the systems resulting after selecting any subsets of S is dealt with. An algorithm that obtains all the necessary information to solve this problem, even if the operator in each linear relation is chosen, at wish, as an equality or inequality ⩽, is given. In addition, this algorithm simultaneously obtains the orthogonal set (dual cone) of a linear space (cone) generated by any subset of a given set of vectors (including sign selection), and allows simplifying the representation of the resulting linear spaces and cones to their minimal representations. The proposed methods are illustrated with several examples.

An interval system of equations is weakly solvable if at least one of its subsystems is solvable, and it is strongly solvable if all its subsystems are solvable. We give necessary and sufficient conditions enabling efficient testing of weak and strong solvability over max-plus and max-min algebras.

In this paper, a method to compute the solution of a system of linear equations by means of Neville elimination is described using two kinds of partitioning techniques: Block and Block-striped. This type of approach is especially suited to the case of totally positive linear systems, which is present in different fields of application. Although Neville elimination carried out more floating point operations than Gaussian elimination in some cases, in this study we confirm that these advantages disappear when we use multiprocessor systems. On the other hand, the overall parallel run time of Neville elimination is better than Gauss time as Neville elimination uses a lower cost communication model.

We present sufficient conditions for the convergent splitting of a non-Hermitian positive definite matrix. These results are applicable to identify the convergence of iterative methods for solving large sparse system of linear equations.

In [J. Nedoma, Ann. Oper. Res. 47 (1993) 483–496], a method for optimizing a linear function on the solution set of a vague system of linear equations was proposed. In this paper, we deal with the so-called simultaneous version of this method. We show that it works provided the system matrix is pattern-shaped. In this case, moreover, the iteration process is extremely simple, not requiring any matrix operation after being started. The application of this method to the mentioned optimization problem is straightforward provided a list of the space orthants covering the solution set is given. A way of finding this list is outlined briefly.

A linear system of equations Ax=b is sign solvable if it is solvable and both its solvability and the sign pattern of its solution vector x are uniquely determined by the sign patterns of A and b . It was proved in [L. Bassett, J. Maybee, J. Quirk, Economitrica 36 (1968) 544–563; R.A. Bruali, B.L. Shader, Matrices of Sign-Solvable Linear Systems, Cambridge University Press, Cambridge, 1995] that the sign solvability of a linear system Ax=b in standard form and with a square coefficient matrix A can be described in terms of the signed digraph S(A) of the matrix A with a specified vertex subset depending on the sign pattern of the vector b . In this paper we define the notion of W + -sign solvable signed digraphs which represent precisely the sign solvable linear systems in standard form. We give necessary and sufficient conditions for the underlying (unsigned) digraphs of W + -sign solvable signed digraphs in terms of forbidden subdigraphs. We also give several necessary and sufficient conditions for strongly connected W + -sign solvable signed digraphs.

For unsolvable systems of linear equations of the form A⊗ x = b over the max–min (fuzzy) algebra R =(〈0,1〉,⊕= max ,⊗= min ), we propose an efficient method for finding a Chebychev-best approximation of the matrix A∈ R (m,n) in the set S ( b )={D∈ R (m,n);D⊗ x = b is solvable } .

We propose a new fast O( n 2 ) parallel algorithm for solving Cauchy systems of linear equations. We perform an a priori rounding error analysis and obtain componentwise bounds for the forward, backward and residual errors. These bounds indicate that for the class of totally positive Cauchy matrices the new algorithm is forward and backward stable, producing a remarkably high relative accuracy. In particular, Hilbert linear systems, often considered to be too ill-conditioned to be attacked, can be rapidly solved with high precision. The results indicate a close resemblance between the numerical properties of Cauchy matrices and the much-studied Vandermonde matrices. In fact, our proposed Cauchy solver is an analog of the well-known Bjorck–Pereyra algorithm for Vandermonde systems. As a by-product we obtain favorably backward error bounds for the original Bjorck–Pereyra algorithm. Several computed examples illustrate a connection of high relative accuracy to the concepts of effective well-conditioning and total positivity.

A descent method for solving a system of linear equations Ax = b consists of the iterations x k +1 = x k + λ k z k , where z k is a vector and λ k a parameter chosen to minimize some functional. In this paper, we will consider multiparameter generalizations of such descent methods, namely iterations of the form x k +1 = x k + Z k Λ k , where Z k is a matrix and Λ k a vector chosen to minimize some functional. Multiparameter generalizations of the conjugate direction method and the Lanczos method will be obtained and their algebraic properties discussed. Multiparameter conjugate and biconjugate gradient algorithms and other Lanczos-type algorithms for implementing this Lanczos method will also be given.

Two extremal algebras ℬ=(B⊕,⊗) based on a linearly ordered set (B, ⩽) are considered: in the maxmin algebra ⊖=max, ⊗ = min and in the maxgroup algebra ⊕ = max and ⊗ is a group operation. If a system A ⊗ x = b of linear equations over an extremal algebra is insolvable, then any subset of equations such that its omitting leads to a solvable subsystem is called a relieving set. We show that the problem of finding the minimum cardinality relieving set is NP-complete in the maxmin algebra already for bivalent systems, while it is polynomially solvable for bivalent systems in maxgroup algebra and also NP-complete for trivalent systems.

Recently, Wu and Cain [L. Wu, B. Cain, Linear Algebra and its Applications 236 (1996) 137–146] gave necessary and sufficient conditions for the matrix equationAX = B to have a solution with respect toA subject to the condition that the Hermitian part ofA is non-negative definite. In this note we give an easier approach, which also provides possible explicit expressions forA. Further, necessary and sufficient conditions are derived when the Hermitian part ofA is prescribed to be positive definite, thus correcting a result in [L. Wu, B. Cain, Linear Algebra and its Applications 236 (1996) 137–146, Theorem 5].

A class of parallel decomposition-type accelerated over-relaxation methods, including four arbitrary parameters and suitable to the SIMD-systems, is established for solving the large sparse systems of linear equations in this paper, and sufficient conditions ensuring its convergence are deduced when the coefficient matrices of the linear systems of equations are respectively L -matrices, H -matrices and positive definite matrices. In particular, we investigate in detail the symmetric versions of these new methods, and deduce a series of conveniently applicable conditions for determining the convergence of hese versions when the coefficient matrices of the linear systems of equations are symmetric positive definite matrices.

This paper is concerned with the solution of systems of linear equations TNXN = bN, where ∗TN∗NϵN denotes a sequence of nonsingular nonsymmetric Toeplitz matrices arising from a generating function of the Wiener class. We present a technique for the fast construction of optimal trigonometric preconditioners MN = MN(T′NTN) of the corresponding normal equation which can be extended to Toeplitz least squares problems in a straightforward way. Moreover, we prove that the spectrum of the preconditioned matrix MN1T′NTN is clustered at 1 such that the PCG-method applied to the normal equation converges superlinearly. Numerical tests confirm the theoretical expectations.

All involutions on the set of all matrices with complex entries are described. It is established when every matrix possesses a generalized inverse for an involution. This generalized inverse is then applied to the least-squares solution to a system of linear equations using more general inner products.

We give a method to compute all nonnegative integer solutions of a homogeneous system of linear equations. We use this method to provide an algorithm to compute all nonnegative integer solutions of homogeneous systems of equations having some of the equations in congruences.

We give a weakly stable algorithm to solve a block Toeplitz system of linear equations. If the lookahead steps taken to compute the parameters of the inversion formula for the block Toeplitz matrix are small compared to the order n of the matrix, the algorithm requires O(n2) floating-point operations. The parameters of the inversion formula are interpreted and computed in a recursive way as solutions of certain interpolation problems given the formal Laurent series based on the data of the block Toeplitz matrix.

Adler and Beling considered the linear programming problem over the real algebraic numbers. They obtained the necessary bounds in terms of a notion of size and dimension needed to justify its polynomial-time solvability, using the ellipsoid method and under some models of computation. Based on a better notion of size than that used by Adler and Beling, we first reduce the feasibility problem in linear programming to some canonical problems preserving its size and its constraint-matrix dimensions. For these canonical problems as well as for the matrix scaling problem, shown to be a more general problem than linear programming, we obtain the necessary bounds; demonstrate simple rounding schemes; justify the applicability of two polynomial-time interior-point algorithms under some models of computation; describe a method for solving a system of linear equations over the algebraic numbers which is a subroutine within these interior-point algorithms under an input model; and give an alternative method to the traditional duality-based approach for the conversion of a general linear programming problem into a feasibility problem.

It is proved that some classical bounds on solutions of perturbed systems of linear equations may yield arbitrarily large overestimations for arbitrarily narrow perturbations. The proofs are constructive.

A class of new hybrid algebraic multilevel preconditioning methods is presented for solving the large sparse systems of linear equations with symmetric positive definite coefficient matrices resulting from the discretization of many second-order elliptic boundary-value problems by the finite-element method. The new preconditioners are shown to be of optimal orders of complexities for two-dimensional and three-dimensional problem domains, and their relative condition numbers are estimated to be bounded uniformly, independent of the numbers of both the levels and the nodes.

Let A x = b be a system of linear equations where A is symmetric and positive definite. Suppose that the associated block Jacobi matrix B is consistently ordered, weekly cyclic of index 2, and convergent [i.e., μ 1 ≔ ϱ ( B ) n + 1 = T ω x n + c ω for n ⩾ 0, to solve the system. We derive a uniform error bound for the overrelaxation methods, ∥x−x n ∥ 2 ⩽ 1 [1+s(μ 1 2 ) + t(μ 1 2 )] 2 x (t 0 + |t 1 |μ 1 2 ) 2 ∥δ n ∥ 2 − 2t 0 〈δ n ,δ n+1 〉 +|t 1 |μ 1 2 ∥δ n ∥∥δ n+1 ∥+∥δ n+1 ∥ 2 where ∥ · ∥ = ∥ · ∥ 2 , δ n = x n − x n − 1 , and s ( μ 2 ) and t ( μ 2 ) ≔ t 0 + t 1 μ 2 are two coefficients of the corresponding functional equation connecting the eigenvalues λ of T ω to the eigenvalues μ of B . As special cases of the uniform error bound, we will give two error bounds for the SSOR and USSOR methods.

The relaxation method for linear inequalities iterates by projecting the current point onto the most violated constraint. Accelerated methods project onto the intersection of several halfspaces or onto a surrogate halfspace corresponding to a nonnegative combination of constraints. We extend Todd's conditions for finding best surrogate inequalities via the solution of systems of linear equations. Our techniques may be used for accelerating various methods for convex feasibility and optimization problems.

For large-scale system of linear equations with symmetric positive definite block coefficient matrix resulting from the discretization of a self-adjoint elliptic boundary-value problem, by making use of blocked multilevel iteration we construct preconditioning matrices for the coefficient matrix and set up a class of parallel multilevel iterative methods for solving such system. Theoretical analysis shows that besides lending themselves to strongly parallel computation these new methods have convergence rates independent of both the sizes and the level numbers of the grids, and their computational work loads are also bounded by linear functions about the step sizes of the finest grids.

Discrete irregular sampling is the problem of recovering a band-limited discrete signal from its nonuniformly sampled values. We introduce a new method for discrete irregular sampling. It features a new sampling geometry where the sampling points are chosen to come in pairs. A frequency domain formulation reduces the problem to a system of linear equations for which the matrix is of Toeplitz type and is positive definite as soon as there are enough samples. An explicit estimate of the condition number of that matrix is given under some condition on the maximum sampling gap. This condition allows gaps larger than the Nyquist gap. We recombine the new method and the conjugate method to deduce an efficient iterative reconstruction scheme for band-limited discrete signals. Numerical results are provided to illustrate the efficiency of the method.

Inspired by a recent article of Searle (1994), we consider some specific features of estimation of Xβ in the general linear model {y , Xβ , V} , where the model matrix X need not have full column rank and the dispersion matrix V can be singular. Particular attention is paid to the problems related to the invariance of some matrix expressions with respect to the choice of generalized inverses. These invariance properties yield interesting matrix algebra while characterizing the best linear unbiased estimator of Xβ .