AN ADAPTIVE VARIANT OF CGNR ALGORITHM

1　IntroductionConsider large linear systemAx =b, ( 1 .1 )where A and b are given,A isa nonsingularn×n real matrix,and b is an n-vector.When A issymmetric positive definite ( s.p.d.) ,the classical conjugate gradient method ( CG) [7] used inconjunction with incomplete factorization preconditioning technique[1 0 ] is a succesful method inview of the high robustness and efficiency.But for general non-s.p.d.systems,the situationis less satisfactory.The generalized minimal residual algorithm( …     

Adaptive polynomial preconditioning for hermitian indefinite linear systems

This paper explores the use of polynomial preconditioned CG methods for hermitian indefinite linear systems,Ax=b. Polynomial preconditioning is attractive for several reasons. First, it is well-suited to vector and/or parallel architectures. It is also easy to employ, requiring only matrix-vector multiplication and vector addition. To obtain an optimum polynomial preconditioner we solve a minimax approximation problem. The preconditioning polynomial,C(), is optimum in that it minimizes a bound on the condition number of the preconditioned matrix,C(A)A. We also characterize the behavior of this minimax polynomial, which makes possible a thorough understanding of the associated CG methods. This characterization is also essential to the development of an adaptive procedure for dynamically determining the optimum polynomial preconditioner. Finally, we demonstrate the effectiveness of polynomial preconditioning in a variety of numerical experiments on a Cray X-MP/48. Our results suggest that high degree (20–50) polynomials are usually best.This research was supported in part by the Applied Mathematical Sciences subprogram of the Office of Energy Research, U.S. Dept. of Energy, by Lawrence Livermore National Laboratory under contract W-7405-ENG-48.This research was supported in part by the Dept. of Energy and the National Science Foundation under grant DMS 8704169.This research was supported in part by U.S. Dept. of Energy grant DEFG02-87ER25026 and by National Science Foundation grant DMS 8703226.     

On the eigenvalue distribution of a class of preconditioning methods

Summary A class of preconditioning methods depending on a relaxation parameter is presented for the solution of large linear systems of equationAx=b, whereA is a symmetric positive definite matrix. The methods are based on an incomplete factorization of the matrixA and include both pointwise and blockwise factorization. We study the dependence of the rate of convergence of the preconditioned conjugate gradient method on the distribution of eigenvalues ofC ^–1 A, whereC is the preconditioning matrix. We also show graphic representations of the eigenvalues and present numerical tests of the methods.     

Disjoint bases in a polymatroid

Let f : 2^N → ⁺ be a polymatroid (an integer‐valued non‐decreasing submodular set function with f(??) = 0). We call S ? N a base if f(S) = f(N). We consider the problem of finding a maximum number of disjoint bases; we denote by m* be this base packing number. A simple upper bound on m* is given by k* = max{k : Σ_iεNf_A(i) ≥ kf_A(N),?A ? N} where f_A(S) = f(A ∪ S) ‐ f(A). This upper bound is a natural generalization of the bound for matroids where it is known that m* = k*. For polymatroids, we prove that m* ≥ (1 ? o(1))k*/lnf(N) and give a randomized polynomial time algorithm to find (1 ? o(1))k*/lnf(N) disjoint bases, assuming an oracle for f. We also derandomize the algorithm using minwise independent permutations and give a deterministic algorithm that finds (1 ? ε)k*/lnf(N) disjoint bases. The bound we obtain is almost tight because it is known there are polymatroids for which m* < (1 + o(1))k*/lnf(N). Moreover it is known that unless NP ? DTIME(n^{log log n}), for any ε > 0, there is no polynomial time algorithm to obtain a (1 + ε)/lnf(N)‐approximation to m*. Our result generalizes and unifies two results in the literature. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

Parallel Multiplication in GF(2k) using Polynomial Residue Arithmetic

We present a novel method of parallelization of the multiplication operation in GF(2^k) for an arbitrary value of k and arbitrary irreducible polynomial n(x) generating the field. The parallel algorithm is based on polynomial residue arithmetic, and requires that we find L pairwise relatively prime modulim _i(x) such that the degree of the product polynomialM(x)=m ₁(x)m ₂(x)··· m_L(x) is at least 2k. The parallel algorithm receives the residue representations of the input operands (elements of the field) and produces the result in its residue form, however, it is guaranteed that the degree of this polynomial is less than k and it is properly reduced by the generating polynomial n(x), i.e., it is an element of the field. In order to perform the reductions, we also describe a new table lookup based polynomial reduction method.     

Polynomial time algorithms for some classes of constrained nonconvex quadratic problems

In this paper we consider different classes of noneonvex quadratic problems that can be solved in polynomial time. We present an algorithm for the problem of minimizing the product of two linear functions over a polyhedron P in R ⁿ The complexity of the algorithm depends on the number of vertices of the projection of P onto the R ² space. In the worst-case this algorithm requires an exponential number of steps but its expected computational time complexity is polynomial. In addition, we give a characterization for the number of isolated local minimum areas for problems on this form.

Furthermore, we consider indefinite quadratic problems with variables restricted to be nonnegative. These problems can be solved in polynomial time if the number of negative eigenvalues of the associated symmetric matrix is fixed.     

An Algorithm for Corona Solutions on <Emphasis Type="Italic">H</Emphasis><Superscript>∞</Superscript> (<Emphasis Type="Italic">D</Emphasis>)

We give an algorithm to find corona solutions in H ^∞ (D) for polynomial input data. Partially supported by NSF Grant DMS-0400307.     

A capacity-rounding algorithm for the minimum-cost circulation problem: A dual framework of the Tardos algorithm

Recently, É. Tardos gave a strongly polynomial algorithm for the minimum-cost circulation problem and solved the open problem posed in 1972 by J. Edmonds and R.M. Karp. Her algorithm runs in O(m ² T(m, n) logm) time, wherem is the number of arcs,n is the number of vertices, andT(m, n) is the time required for solving a maximum flow problem in a network withm arcs andn vertices. In the present paper, taking an approach that is a dual of Tardos's, we also give a strongly polynomial algorithm for the minimum-cost circulation problem. Our algorithm runs in O(m ² S(m, n) logm) time and reduces the computational complexity, whereS(m, n) is the time required for solving a shortest path problem with a fixed origin in a network withm arcs,n vertices, and a nonnegative arc length function. The complexity is the same as that of Orlin's algorithm, recently developed by efficiently implementing the Edmonds-Karp scaling algorithm.     

Stability analysis of a general toeplitz systems solver

We show that a fast algorithm for theQR factorization of a Toeplitz or Hankel matrixA is weakly stable in the sense thatR ^T R is close toA ^T A. Thus, when the algorithm is used to solve the semi-normal equationsR ^TRx=A^T b, we obtain a weakly stable method for the solution of a nonsingular Toeplitz or Hankel linear systemAx=b. The algorithm also applies to the solution of the full-rank Toeplitz or Hankel least squares problem min ||Ax-b||₂.     

Computations on preconditioning cubic spline collocation method of elliptic equations

In this work we investigate the finite element preconditioning method for theC ¹-cubic spline collocation discretizations for an elliptic operatorA defined byAu:=−Δu+a ₁ u _x +a ₂ u _y +a ₀ u in the unit square with some boundary conditions. We compute the condition number and the numerical solution of the preconditioning system for the several example problems. Finally, we compare the this preconditioning system with the another preconditioning system.     

QD algorithms and algebraic eigenvalue problems

A sketch of the standard QD algorithm is followed by the derivation of two similar algorithms for the calculation of all the eigenvalues of the matrix A from the sequence {A^rg₀}. The existence of one of the methods is stablished and bounds for the results are given when A is totally positive. The paper concludes by showing the close connection between the QD algorithm for the calculation of the zeros of a polynomial and the method of treppeniteration for the calculation of the eigenvalues of its companion matrix.     

A faster capacity scaling algorithm for minimum cost submodular flow

We describe an O(n ⁴ hmin{logU,n ²logn}) capacity scaling algorithm for the minimum cost submodular flow problem. Our algorithm modifies and extends the Edmonds–Karp capacity scaling algorithm for minimum cost flow to solve the minimum cost submodular flow problem. The modification entails scaling a relaxation parameter δ. Capacities are relaxed by attaching a complete directed graph with uniform arc capacity δ in each scaling phase. We then modify a feasible submodular flow by relaxing the submodular constraints, so that complementary slackness is satisfied. This creates discrepancies between the boundary of the flow and the base polyhedron of a relaxed submodular function. To reduce these discrepancies, we use a variant of the successive shortest path algorithm that augments flow along minimum cost paths of residual capacity at least δ. The shortest augmenting path subroutine we use is a variant of Dijkstra’s algorithm modified to handle exchange capacity arcs efficiently. The result is a weakly polynomial time algorithm whose running time is better than any existing submodular flow algorithm when U is small and C is big. We also show how to use maximum mean cuts to make the algorithm strongly polynomial. The resulting algorithm is the first capacity scaling algorithm to match the current best strongly polynomial bound for submodular flow. Received: August 6, 1999 / Accepted: July 2001?Published online October 2, 2001     

A note on skew differential operators on commutative rings

Let A be a commutative integral domain that is a finitely generated algebra over a field k of characteristic 0 and let ø be a k-algebra automorphism of A of finite order m. In this note we study the ring D(A;ø of differential operators introduced by A.D. Bell. We prove that if A is a free module over the fixed sub-ring A ^ø, with a basis containing 1, then D(A;ø) is isomorphic to the matrix ring M_m(D(A ^ø). It follows from Grothendieck's Generic Flatness Theorem that for an arbitrary A there is an element c?Asuch that D(A[c^-1];ø)?M _m(D(A[c^-1]^ø)). As an application, we consider the structure of D(A;ø)when A is a polynomial or Laurent polynomial ring over k and ø is a diagonalizable linear automorphism.     

Boolean Metric Spaces and Boolean Algebraic Varieties

Abstract

The concepts of Boolean metric space and convex combination are used to characterize polynomial maps A ⁿ ?→?A ^m in a class of commutative Von Neumann regular rings including p-rings, that we have called CFG-rings. In those rings, the study of the category of algebraic varieties (i.e., sets of solutions to a finite number of polynomial equations with polynomial maps as morphisms) is equivalent to the study of a class of Boolean metric spaces, that we call here CFG-spaces.     

Polynomials in a matrix

Let A be a matrixp(x) a polynomial. Put B=p(A). It is shown that necessary and sufficient conditions for A to be a polynomial in B are (i) if λ is any eigenvalue of A, and if some elementary divisor of A corresponding to λ is nonlinear, thenp ^′(λ)≠0;and (ii) if λ,μ are distinct eigenvalues of A, then p(λ)p(μ) are also distinct. Here all computations are over some algebraically closed field.     

Optimal orthogonalization processes

Two optimal orthogonalization processes are devised toorthogonalize,possibly approximately,the columns of a very large and possiblysparse matrix A∈C^n×k.Algorithmically the aim is,at each step,to optimallydecrease nonorthogonality of all the columns of A.One process relies on using translated small rank corrections.Another is a polynomial orthogonalization process forperforming the L?wdin orthogonalization.The steps rely on using iterative methods combined,preferably,with preconditioning which can have a dramatic effect on how fast thenonorthogonality decreases.The speed of orthogonalization depends on howbunched the singular values of A are,modulo the number of steps taken.These methods put the steps of the Gram-Schmidt orthogonalizationprocess into perspective regardingtheir(lack of)optimality.The constructions are entirely operatortheoretic and can be extended to infinite dimensional Hilbert spaces.     

High quality preconditioning of a general symmetric positive definite matrix based on its UTU + UTR + RTU-decomposition

A new matrix decomposition of the form A = U^TU + U^TR + R^TU is proposed and investigated, where U is an upper triangular matrix (an approximation to the exact Cholesky factor U₀), and R is a strictly upper triangular error matrix (with small elements and the fill-in limited by that of U₀). For an arbitrary symmetric positive matrix A such a decomposition always exists and can be efficiently constructed; however it is not unique, and is determined by the choice of an involved truncation rule. An analysis of both spectral and K-condition numbers is given for the preconditioned matrix M = U^−T AU⁻¹ and a comparison is made with the RIC preconditioning proposed by Ajiz and Jennings. A concept of approximation order of an incomplete factorization is introduced and it is shown that RIC is the first order method, whereas the proposed method is of second order. The idea underlying the proposed method is also applicable to the analysis of CGNE-type methods for general non-singular matrices and approximate LU factorizations of non-symmetric positive definite matrices. Practical use of the preconditioning techniques developed is discussed and illustrated by an extensive set of numerical examples. Copyright © 1999 John Wiley & Sons, Ltd.     

A new look at the doubling algorithm for a structured palindromic quadratic eigenvalue problem

Recently, Guo and Lin [SIAM J. Matrix Anal. Appl., 31 (2010), 2784–2801] proposed an efficient numerical method to solve the palindromic quadratic eigenvalue problem (PQEP) (λ²A^T+λQ + A)z = 0 arising from the vibration analysis of high speed trains, where have special structures: both Q and A are, among others, m × m block matrices with each block being k × k (thus, n = mk), and moreover, Q is block tridiagonal, and A has only one nonzero block in the (1,m)th block position. The key intermediate step of the method is the computation of the so‐called stabilizing solution to the n × n nonlinear matrix equation X + A^TX⁻¹A = Q via the doubling algorithm. The aim of this article is to propose an improvement to this key step through solving a new nonlinear matrix equation having the same form but of only k × k in size. This new and much smaller matrix equation can also be solved by the doubling algorithm. For the same accuracy, it takes the same number of doubling iterations to solve both the larger and the new smaller matrix equations, but each doubling iterative step on the larger equation takes about 4.8 as many flops than the step on the smaller equation. Replacing Guo's and Lin's key intermediate step by our modified one leads to an alternative method for the PQEP. This alternative method is faster, but the improvement in speed is not as dramatic as just for solving the respective nonlinear matrix equations and levels off as m increases. Numerical examples are presented to show the effectiveness of the new method. Copyright © 2014 John Wiley & Sons, Ltd.     

Asymptotic convergence of degree‐raising

It is well known that the degree‐raised Bernstein–Bézier coefficients of degree n of a polynomial g converge to g at the rate 1/n. In this paper we consider the polynomial A _n(g) of degree ⩼ n interpolating the coefficients. We show how A _n can be viewed as an inverse to the Bernstein polynomial operator and that the derivatives A _n(g)(^r) converge uniformly to g(^r) at the rate 1/n for all r. We also give an asymptotic expansion of Voronovskaya type for A _n(g) and discuss some shape preserving properties of this polynomial. This revised version was published online in June 2006 with corrections to the Cover Date.