Computing the nearest diagonally dominant matrix

We solve the problem of minimizing the distance from a given matrix to the set of symmetric and diagonally dominant matrices. First, we characterize the projection onto the cone of diagonally dominant matrices with positive diagonal, and then we apply Dykstra's alternating projection algorithm on this cone and on the subspace of symmetric matrices to obtain the solution. We discuss implementation details and present encouraging preliminary numerical results. Copyright © 1999 John Wiley & Sons, Ltd.     

广义对角占优阵的一个等价条件

给出了实方阵为广义对角占优阵的充要条件,同时给出了判断广义对角占优阵可靠,可行,较简单方法。     

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 parallel GSAOR method for block diagonally dominant matrices

In this paper we consider the parallel generalized SAOR iterative method based on the generalized AOR iterative method presented by James for solving large nonsingular system. We obtain some convergence theorems for the case when coefficient matrix is a block diagonally dominant matrix or a generalized block diagonal dominant matrix. A numerical example is given to illustrate to our results.     

Invex Functions and Generalized Convexity in Multiobjective Programming

Martin (Ref. 1) studied the optimality conditions of invex functions for scalar programming problems. In this work, we generalize his results making them applicable to vectorial optimization problems. We prove that the equivalence between minima and stationary points or Kuhn–Tucker points (depending on the case) remains true if we optimize several objective functions instead of one objective function. To this end, we define accurately stationary points and Kuhn–Tucker optimality conditions for multiobjective programming problems. We see that the Martin results cannot be improved in mathematical programming, because the new types of generalized convexity that have appeared over the last few years do not yield any new optimality conditions for mathematical programming problems.     

Uzawa block relaxation domain decomposition method for a two-body frictionless contact problem

We propose a Uzawa block relaxation domain decomposition method for a two-body frictionless contact problem. We introduce auxiliary variables to separate subdomains representing linear elastic bodies. Applying a Uzawa block relaxation algorithm to the corresponding augmented Lagrangian functional yields a domain decomposition algorithm in which we have to solve two uncoupled linear elasticity subproblems in each iteration while the auxiliary variables are computed explicitly using Kuhn–Tucker optimality conditions.     

Error bounds for analytic systems and their applications

Using a 1958 result of Lojasiewicz, we establish an error bound for analytic systems consisting of equalities and inequalities defined by real analytic functions. In particular, we show that over any bounded region, the distance from any vectorx in the region to the solution set of an analytic system is bounded by a residual function, raised to a certain power, evaluated atx. For quadratic systems satisfying certain nonnegativity assumptions, we show that this exponent is equal to 1/2. We apply the error bounds to the Karush—Kuhn—Tucker system of a variational inequality, the affine variational inequality, the linear and nonlinear complementarity problem, and the 0–1 integer feasibility problem, and obtain new error bound results for these problems. The latter results extend previous work for polynomial systems and explain why a certain square-root term is needed in an error bound for the (monotone) linear complementarity problem.The research of this author is based on work supported by the Natural Sciences and Engineering Research Council of Canada under grant OPG0090391.The research of this author is based on work supported by the National Science Foundation under grants DDM-9104078 and CCR-9213739 and by the Office of Naval Research under grant 4116687-01.     

Menger's theorem for infinite graphs with ends

A well‐known conjecture of Erd?s states that given an infinite graph G and sets A, ? V(G), there exists a family of disjoint A ? B paths ?? together with an A ? B separator X consisting of a choice of one vertex from each path in ??. There is a natural extension of this conjecture in which A, B, and X may contain ends as well as vertices. We prove this extension by reducing it to the vertex version, which was recently proved by Aharoni and Berger. © 2005 Wiley Periodicals, Inc. J Graph Theory 50: 199–211, 2005     

Sharp thresholds for the phase transition between primitive recursive and Ackermannian Ramsey numbers

We compute the sharp thresholds on g at which g-large and g-regressive Ramsey numbers cease to be primitive recursive and become Ackermannian.We also identify the threshold below which g-regressive colorings have usual Ramsey numbers, that is, admit homogeneous, rather than just min-homogeneous sets.     

The convergence of Jacobi–Davidson iterations for Hermitian eigenproblems

Rayleigh quotient iteration is an iterative method with some attractive convergence properties for finding (interior) eigenvalues of large sparse Hermitian matrices. However, the method requires the accurate (and, hence, often expensive) solution of a linear system in every iteration step. Unfortunately, replacing the exact solution with a cheaper approximation may destroy the convergence. The (Jacobi‐) Davidson correction equation can be seen as a solution for this problem. In this paper we deduce quantitative results to support this viewpoint and we relate it to other methods. This should make some of the experimental observations in practice more quantitative in the Hermitian case. Asymptotic convergence bounds are given for fixed preconditioners and for the special case if the correction equation is solved with some fixed relative residual precision. A dynamic tolerance is proposed and some numerical illustration is presented. Copyright © 2002 John Wiley & Sons, Ltd.     

Partitioning the edge set of a hypergraph into almost regular cycles

A cycle of length t in a hypergraph is an alternating sequence of distinct vertices and distinct edges so that (with ). Let be the λ‐fold n‐vertex complete h‐graph. Let be a hypergraph all of whose edges are of size at least h, and . In order to partition the edge set of into cycles of specified lengths , an obvious necessary condition is that . We show that this condition is sufficient in the following cases.

• (R1) .
• (R2) , .
• (R3) , , .

In (R2), we guarantee that each cycle is almost regular. In (R3), we also solve the case where a “small” subset L of edges of is removed.     

Combination of Jacobi–Davidson and conjugate gradients for the partial symmetric eigenproblem

To compute the smallest eigenvalues and associated eigenvectors of a real symmetric matrix, we consider the Jacobi–Davidson method with inner preconditioned conjugate gradient iterations for the arising linear systems. We show that the coefficient matrix of these systems is indeed positive definite with the smallest eigenvalue bounded away from zero. We also establish a relation between the residual norm reduction in these inner linear systems and the convergence of the outer process towards the desired eigenpair. From a theoretical point of view, this allows to prove the optimality of the method, in the sense that solving the eigenproblem implies only a moderate overhead compared with solving a linear system. From a practical point of view, this allows to set up a stopping strategy for the inner iterations that minimizes this overhead by exiting precisely at the moment where further progress would be useless with respect to the convergence of the outer process. These results are numerically illustrated on some model example. Direct comparison with some other eigensolvers is also provided. Copyright © 2001 John Wiley & Sons, Ltd.     

A fresh approach to the Paley–Wiener theorem for Mellin transforms and the Mellin–Hardy spaces

Here we give a new approach to the Paley–Wiener theorem in a Mellin analysis setting which avoids the use of the Riemann surface of the logarithm and analytical branches and is based on new concepts of polar‐analytic function in the Mellin setting and Mellin–Bernstein spaces. A notion of Hardy spaces in the Mellin setting is also given along with applications to exponential sampling formulas of optical physics.     

Optimal preconditioning for the symmetric and nonsymmetric coupling of adaptive finite elements and boundary elements

We analyze a multilevel diagonal additive Schwarz preconditioner for the adaptive coupling of FEM and BEM for a linear 2D Laplace transmission problem. We rigorously prove that the condition number of the preconditioned system stays uniformly bounded, independently of the refinement level and the local mesh‐size of the underlying adaptively refined triangulations. Although the focus is on the nonsymmetric Johnson–Nédélec one‐equation coupling, the principle ideas also apply to other formulations like the symmetric FEM‐BEM coupling. Numerical experiments underline our theoretical findings. © 2015 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 33: 603–632, 2017     

Necessary and sufficient conditions for the existence of symmetric positive solutions of singular boundary value problems

Necessary and sufficient conditions are obtained for the existence of symmetric positive solutions to the boundary value problem

     

An upper and lower solution approach for singular boundary value problems with sign changing non‐linearities

We obtain via Schauder's fixed point theorem new results for singular second‐order boundary value problems where our non‐linear term f(t,y,z) is allowed to change sign. In particular, our problem may be singular at y=0, t=0 and/or t=1. Copyright © 2002 John Wiley & Sons, Ltd.     

Periodicity and non‐negativity of solutions for nonlinear neutral differential equations with variable delay via fixed point theorems

We use a modification of Krasnoselskii's fixed point theorem introduced by Burton to show the periodicity and non‐negativity of solutions for the nonlinear neutral differential equation with variable delay We invert this equation to construct the sum of a compact map and a large contraction, which is suitable for applying the modification of Krasnoselskii's theorem. Copyright © 2015 John Wiley & Sons, Ltd.     

An Analog of the Poincarée Separation Theorem for Normal Matrices and the Gauss–Lucas Theorem

We establish an analog of the Cauchy–Poincarée separation theorem for normal matrices in terms of majorization. A solution to the inverse spectral problem (Borg type result) is also presented. Using this result, we generalize and extend the Gauss–Lucas theorem about the location of roots of a complex polynomial and of its derivative. The generalization is applied to prove old conjectures due to de Bruijn–Springer and Schoenberg.