Some Features of Gaussian Elimination with Rook Pivoting

Rook pivoting is a relatively new pivoting strategy used in Gaussian elimination (GE). It can be as computationally cheap as partial pivoting and as stable as complete pivoting. This paper shows some new attractive features of rook pivoting. We first derive error bounds for the LU factors computed by GE and show rook pivoting usually gives a highly accurate U factor. Then we show accuracy of the computed solution of a linear system by rook pivoting is essentially independent of row scaling of the coefficient matrix. Thus if the matrix is ill-conditioned due to bad row scaling a highly accurate solution can usually be obtained. Finally for a typical inversion method involving the LU factorization we show rook pivoting usually makes both left and right residuals for the computed inverse of a matrix small.     

Stability of a Pivoting Strategy for Parallel Gaussian Elimination

Gaussian elimination with partial pivoting achieved by adding the pivot row to the kth row at step k, was introduced by Onaga and Takechi in 1986 as means for reducing communications in parallel implementations. In this paper it is shown that the growth factor of this partial pivoting algorithm is bounded above by _n <#60; 3 ^n–1, as compared to 2 ^n–1 for the standard partial pivoting. This bound _n, close to 3 ^n–2, is attainable for class of near-singular matrices. Moreover, for the same matrices the growth factor is small under partial pivoting.This revised version was published online in October 2005 with corrections to the Cover Date.     

A Multigrid Method Based on Incomplete Gaussian Elimination

In this paper we introduce and analyse a new Schur complement approximation based on incomplete Gaussian elimination. The approximate Schur complement is used to develop a multigrid method. This multigrid method has an algorithmic structure that is very similar to the algorithmic structure of classical multigrid methods. The resulting method is almost purely algebraic and has interesting properties with respect to variation in problem parameters.     

On the pivot structure for the weighing matrix W(12,11)

In the present article we concentrate our study on the growth problem for the weighing matrix W(12,11) and show that the unique W(12,11) has three pivot structures. An improved algorithm for extending a k?×?k (0,+,-) matrix to a W(n,n-1), if possible, has been developed to simplify the proof. For the implementation of the algorithm special emphasis is given to the notions of data structures and parallel processing.     

On the fast solution of Toeplitz-block linear systems arising in multivariate approximation theory

When constructing multivariate Padé approximants, highly structured linear systems arise in almost all existing definitions [10]. Until now little or no attention has been paid to fast algorithms for the computation of multivariate Padé approximants, with the exception of [17]. In this paper we show that a suitable arrangement of the unknowns and equations, for the multivariate definitions of Padé approximant under consideration, leads to a Toeplitz-block linear system with coefficient matrix of low displacement rank. Moreover, the matrix is very sparse, especially in higher dimensions. In Section 2 we discuss this for the so-called equation lattice definition and in Section 3 for the homogeneous definition of the multivariate Padé approximant. We do not discuss definitions based on multivariate generalizations of continued fractions [12, 25], or approaches that require some symbolic computations [6, 18]. In Section 4 we present an explicit formula for the factorization of the matrix that results from applying the displacement operator to the Toeplitz-block coefficient matrix. We then generalize the well-known fast Gaussian elimination procedure with partial pivoting developed in [14, 19], to deal with a rectangular block structure where the number and size of the blocks vary. We do not aim for a superfast solver because of the higher risk for instability. Instead we show how the developed technique can be combined with an easy interval arithmetic verification step. Numerical results illustrate the technique in Section 5.Research partly funded by FWO-Vlaanderen.     

A collection of examples where Neville elimination outperforms Gaussian elimination

Neville elimination is an elimination procedure alternative to Gaussian elimination. It is very useful when dealing with totally positive matrices, for which nice stability results are known. Here we include examples, most of them test matrices used in MATLAB which are not totally positive matrices, where Neville elimination outperforms Gaussian elimination.     

On the growth factor in Gaussian elimination for generalized Higham matrices

A Higham matrix is a complex symmetric matrix A=B+iC, where both B and C are real, symmetric and positive definite. We prove that, for such A, the growth factor in Gaussian elimination is less than 3. Moreover, a slightly larger bound holds true for a broader class of complex matrices A=B+iC, where B and C are Hermitian and positive definite. Copyright © 2002 John Wiley & Sons, Ltd.     

Values of Minors of (1, −1) Incidence Matrices of SBIBDs and Their Application to the Growth Problem

We obtain explicit formulae for the values of the v-j minors, j=0,1,2 of (1, –1) incidence matrices of SBIBD(v,k,). This allows us to obtain explicit information on the growth problem for families of matrices with moderate growth. An open problem remains to establish whether the (1, –1) CP incidence matrices of SBIBD(v,k,), can have growth greater than v for families other than Hadamard families.     

Gaussian elimination is stable for the inverse of a diagonally dominant matrix

Let be a row diagonally dominant matrix, i.e.,

where with We show that no pivoting is necessary when Gaussian elimination is applied to Moreover, the growth factor for does not exceed The same results are true with row diagonal dominance being replaced by column diagonal dominance.

     

On the row merge tree for sparse LU factorization with partial pivoting

We consider the problem of structure prediction for sparse LU factorization with partial pivoting. In this context, it is well known that the column elimination tree plays an important role for matrices satisfying an irreducibility condition, called the strong Hall property. Our primary goal in this paper is to address the structure prediction problem for matrices satisfying a weaker assumption, which is the Hall property. For this we consider the row merge matrix, an upper bound that contains the nonzeros in L and U for all possible row permutations that can be performed during the numerical factorization with partial pivoting. We discuss the row merge tree, a structure that represents information obtained from the row merge matrix; that is, information on the dependencies among the columns in Gaussian elimination with partial pivoting and on structural upper bounds of the factors L and U. We present new theoretical results that show that the nonzero structure of the row merge matrix can be described in terms of branches and subtrees of the row merge tree. These results lead to an efficient algorithm for the computation of the row merge tree, that uses as input the structure of A, and has a time complexity almost linear in the number of nonzeros in A. We also investigate experimentally the usage of the row merge tree for structure prediction purposes on a set of matrices that satisfy only the Hall property. We analyze in particular the size of upper bounds of the structure of L and U, the reordering of the matrix based on a postorder traversal and its impact on the factorization runtime. We show experimentally that for some matrices, the row merge tree is a preferred alternative to the column elimination tree. AMS subject classification (2000)  65F50, 65F05, 68R10     

Gauss整数环诸类问题探

本文主要探讨：（１） Ｇａｕｓｓ 整数环的定义及性质;（２） 其商环及性质;（３） Ｚ（ｘ）ｘ２＋ １同构于 Ｚ（ｉ）;（４） 两点猜想     

The growth factor of a Hadamard matrix of order 16 is 16

In 1968 Cryer conjectured that the growth factor of an n × n Hadamard matrix is n. In 1988 Day and Peterson proved this only for the Hadamard–Sylvester class. In 1995 Edelman and Mascarenhas proved that the growth factor of a Hadamard matrix of order 12 is 12. In the present paper we demonstrate the pivot structures of a Hadamard matrix of order 16 and prove for the first time that its growth factor is 16. The study is divided in two parts: we calculate pivots from the beginning and pivots from the end of the pivot pattern. For the first part we develop counting techniques based on symbolic manipulation for specifying the existence or non‐existence of specific submatrices inside the first rows of a Hadamard matrix, and so we can calculate values of principal minors. For the second part we exploit sophisticated numerical techniques that facilitate the computations of all possible (n ? j) × (n ? j) minors of Hadamard matrices for various values of j. The pivot patterns are obtained by utilizing appropriately the fact that the pivots appearing after the application of Gaussian elimination on a completely pivoted matrix are given as quotients of principal minors of the matrix. Copyright © 2009 John Wiley & Sons, Ltd.     

On the Automatic Scaling of Matrices for Gaussian Elimination

The usual pivotal strategies for Gaussian elimination are basedon the assumption that all the matrix elements are of comparablesize. We propose an algorithm for scaling based on the assumptionthat the given matrix can be scaled to this required form. Somenumerical experiments are presented to show that it producesmuch better results than straightforward row and column normequilibration, particularly in the sparse case, and that thecomputing cost is moderate.     

On the efficiency of Gaussian adaptation

Gaussian Adaptation (GA) is a stochastic process that adapts a Gaussian distribution to a region or set of feasible points in parameter space. As a result of the adaptation, GA becomes a maximum dispersion process extending the sampling over the largest possible volume in parameter space while keeping the probability of finding feasible points at a suitable level. For such a process, a general measure of efficiency is defined and an efficiency theorem is proved.     

On the capacity of the continuous time Gaussian channel with feedback

We discuss the capacity of the Gaussian channel with feedback. In general it is not easy to give an explicit formula for the capacity of a Gaussian channel, unless the channel is without feedback or a white Gaussian channel. We consider the case where a constraint, given in terms of the covariance functions of the input processes, is imposed on the input processes. It is shown that the capacity of the Gaussian channel can be achieved by transmitting a Gaussian message and using additive linear feedback.     

Bounding the growth factor in Gaussian elimination for Buckley's class of complex symmetric matrices

A Buckley matrix is an n × n complex symmetric matrix A = I _n + iC, where C is real symmetric positive definite. We prove that, for such A the growth factor in Gaussian elimination is not greater than $${1 + \sqrt{17} \over 4} \simeq 1.28078\ldots$$ Copyright © 2000 John Wiley & Sons, Ltd.     

On the Equivalence of Multiparameter Gaussian Processes

Our purpose is to characterize the multiparameter Gaussian processes, that is Gaussian sheets, that are equivalent in law to the Brownian sheet and to the fractional Brownian sheet. We survey multiparameter analogues of the Hitsuda, Girsanov and Shepp representations. As an application, we study a special type of stochastic equation with linear noise.      

A note on reduction of quadratic and bilinear programs with equality constraints

Reduction of some classes of global optimization programs to bilinear programs may be done in various ways, and the choice of method clearly influences the ease of solution of the resulting problem. In this note we show how linear equality constraints may be used together with graph theoretic tools to reduce a bilinear program, i.e., eliminate variables from quadratic terms to minimize the number of complicating variables. The method is illustrated on an example. Computer results are reported on known test problems.     

On multivariate Gaussian tails

Let {X _{n, n} ≥1} be a sequence of standard Gaussian random vectors in ℝ _d ,d ≥ 2. In this paper we derive lower and upper bounds for the tail probabilityP{X _n >t _n } witht _n ∈ ℝ _d some threshold. We improve for instance bounds on Mills ratio obtained by Savage (1962,J. Res. Nat. Bur. Standards Sect. B,66, 93–96). Furthermore, we prove exact asymptotics under fairly general conditions on bothX _n andt _n , as ‖t _n ‖→∞ where the correlation matrix Σ _n ofX _n may also depend onn.     

Simultaneous backward stability of Gauss and Gauss–Jordan elimination

It is well known that some pivoting strategies are backward stable for Gauss elimination but are not backward stable for Gauss–Jordan elimination (GJE) when these procedures are used to solve a linear system Ax=b. We analyse the simultaneous backward stability for Gauss and GJE of several pivoting strategies, including a pivoting strategy which we call double partial pivoting. Copyright © 2002 John Wiley & Sons, Ltd.