Arc graphs and their possible application to sparse matrix problems

In continuation of earlier work on the graph algorithmic language GRAAL, a new type of graph representation is introduced involving solely the arcs and their incidence relations. In line with the set theoretical foundation of GRAAL, the are graph structure is defined in terms of four Boolean mappings over the power set of the ares. A simple data structure is available for are graphs requiring only storage of the order of the cardinality of the are set. As an application, the LU decomposition of large sparse matrices and the solution of the corresponding linear systems are formulated in terms of are graphs and their operators, and experimental results involving these algorithms are presented.     

Algorithms for a class of nondifferentiable problems

A nonlinear programming problem with nondifferentiabilities is considered. The nondifferentiabilities are due to terms of the form min(f ₁(x),...,f _n(x)), which may enter nonlinearly in the cost and the constraints. Necessary and sufficient conditions are developed. Two algorithms for solving this problem are described, and their convergence is studied. A duality framework for interpretation of the algorithms is also developed.This work was supported in part by the National Science Foundation under Grant No. ENG-74-19332 and Grant No. ECS-79-19396, in part by the U.S. Air Force under Grant AFOSR-78-3633, and in part by the Joint Services Electronics Program (U.S. Army, U.S. Navy, and U.S. Air Force) under Contract N00014-79-C-0424.     

Existence,uniqueness and continuity of solutions of integral equations. An addendum

Summary This note corrects au error in the continuous dependence theorem of an earlier paper on the subject stated in the title. Here it is shows that the topology of one of the spaces of functions can be modified in order to obtain the desired continuity results. This research was support in part by the National Aeronautics Space Administration under Grant No. NGL-40-002-015, and in part by the U. S. Air Force under Grant No. AF-AFOSR-67-0693A. This research was supported in part by the National Science Foundation under Grant No. GP-3904 and GP-7041 and in part by the U.S. Army under Grant No. D1-31-124-ARO-D-265. Entrata in Redazione il 10 aprile 1970.     

An element agglomeration nonlinear additive Schwarz preconditioned Newton method for unstructured finite element problems

This paper extends previous results on nonlinear Schwarz preconditioning (Cai and Keyes 2002) to unstructured finite element elliptic problems exploiting now nonlocal (but small) subspaces. The nonlocal finite element subspaces are associated with subdomains obtained from a non-overlapping element partitioning of the original set of elements and are coarse outside the prescribed element subdomain. The coarsening is based on a modification of the agglomeration based AMGe method proposed in Jones and Vassilevski 2001. Then, the algebraic construction from Jones, Vassilevski and Woodward 2003 of the corresponding non-linear finite element subproblems is applied to generate the subspace based nonlinear preconditioner. The overall nonlinearly preconditioned problem is solved by an inexact Newton method. A numerical illustration is also provided.This work was performed under the auspices of the U.S. Department of Energy by the University of California Lawrence Livermore National Laboratory: contract/grant number: W-7405-Eng-48. The contribution of the second author was also partially supported by Polish Scientific Grant 2/P03A/005/24.     

Asymptotic power comparison of the chi-square and likelihood ratio tests

Summary A Hoeffding-type power comparison is made between the likelihood ratio and chi-square tests for a simple hypothesis in a multinomial. The power comparison is based on the fact that under an alternative hypothesis the distribution of the test statistic can be approximated by a normal distribution. The theory of large deviations is used to match the significance levels. This research was partially supported by the National Science Foundation Grant No. GP-33697X2, U.S. Energy Research and Development Agency Grant 7064100, Environmental Protection Agency Grant R805379-01-0 and U.S. Public Health Service Grant USPHS ES01299-15, at the University of California-Berkeley.     

Boolean planarity characterization of graphs

Although many criteria for testing the planarity of a graph have been found since the beginning of the thirties, this paper presents a new criterion described by Boolean technique which is proved in an independent way without any use of the criteria obtained before. This research was supported by the U.S. National Science Foundation under Grant Number ECS 85 03212 and by the National Natural Science Foundation of China as well. And, the author is greatly indebted to Professor Peter L. Hammer for many helpful discussions, suggestions, and comments.     

Lower bounds for the complexity of the graph of the Hausdorff distance as a function of transformation

The Hausdorff distance is a measure defined between two sets in some metric space. This paper investigates how the Hausdorff distance changes as one set is transformed by some transformation group. Algorithms to find the minimum distance as one set is transformed have been described, but few lower bounds are known. We consider the complexity of the graph of the Hausdorff distance as a function of transformation, and exhibit some constructions that give lower bounds for this complexity. We exhibit lower-bound constructions for both sets of points in the plane, and sets of points and line segments; we consider the graph of the directed Hausdorff distance under translation, rigid motion, translation and scaling, and affine transformation. Many of the results can also be extended to the undirected Hausdorff distance. These lower bounds are for the complexity of the graph of the Hausdorff distance, and thus do not necessarily bound algorithms that search this graph; however, they do give an indication of how complex the search may be. This work was supported in part by National Science Foundation PYI Grant IRI-9057928 and matching funds from General Electric, Kodak, and Xerox, and in part by Air Force Contract AFOSR-91-0328.     

Chebyshevian multistep methods for ordinary differential equations

Summary In this paper some theory of linear multistep methods fory ^(r) (x)=f(x,y) is extended to include smooth, stepsize-dependent coefficients. Treated in particular is the case where exact integration of a given set of functions is desired.Work on this paper was supported in part by U.S. Army Research Office (Durham) Grant DA-ARO(D)-31-124-G1050 and National Science Foundation Grant GP-23655 with The University of Texas at Austin.     

The empirical behavior of sampling methods for stochastic programming

We investigate the quality of solutions obtained from sample-average approximations to two-stage stochastic linear programs with recourse. We use a recently developed software tool executing on a computational grid to solve many large instances of these problems, allowing us to obtain high-quality solutions and to verify optimality and near-optimality of the computed solutions in various ways. Research supported by the Mathematical, Information, and Computational Sciences Division subprogram of the Office of Advanced Scientific Computing Research, U.S. Department of Energy, under Contract W-31-109-Eng-38, and by the National Science Foundation under Grant 9726385. Research supported by the Mathematical, Information, and Computational Sciences Division subprogram of the Office of Advanced Scientific Computing Research, U.S. Department of Energy, under Contract W-31-109-Eng-38, and by the National Science Foundation under Grant DMS-0073770. Research supported by the Mathematical, Information, and Computational Sciences Division subprogram of the Office of Advanced Scientific Computing Research, U.S. Department of Energy, under Contract W-31-109-Eng-38, and by the National Science Foundation under Grants 9726385 and 0082065.     

Limit theorems for sums of dependent random variables occurring in statistical mechanics

Summary By the use of conditioning, we extend previously obtained results on the asymptotic behavior of partial sums for certain triangular arrays of dependent random variables, known as Curie-Weiss models. These models arise naturally in statistical mechanics. The relation of these results to multiple phases, metastable states, and other physical phenomena is explained.Alfred P. Sloan Research Fellow. Research supported in part by National Science Foundation Grant MPS 76-06644A01Alfred P. Sloan Research Fellow. Research supported in part by National Science Foundation Grant MCS 77-20683 and by U.S.-Israel Binational Science FoundationResearch supported in part by National Science Foundation Grant PHY77-02172     

Applications of a new space-partitioning technique

We present several applications of a recent space-partitioning technique of Chazelle, Sharir, and Welzl (Proceedings of the 6th Annual ACM Symposium on Computational Geometry, 1990, pp. 23–33). Our results include efficient algorithms for output-sensitive hidden surface removal, for ray shooting in two and three dimensions, and for constructing spanning trees with low stabbing number.Work on this paper has been supported by DIMACS, an NSF Science and Technology Center, under Grant STC-88-09684. The second author has been supported by Office of Naval Research Grants N00014-89-J-3042 and N00014-90-J-1284, by National Science Foundation Grant CCR-89-01484, and by grants from the U.S.-Israeli Binational Science Foundation, the Fund for Basic Research administered by the Israeli Academy of Sciences, and the G.I.F., the German-Israeli Foundation for Scientific Research and Development.     

Hybrid Proximal-Point Methods for Common Solutions of Equilibrium Problems and Zeros of Maximal Monotone Operators

The purpose of this paper is to introduce and study two hybrid proximal-point algorithms for finding a common element of the set of solutions of an equilibrium problem and the set of solutions to the equation 0∈Tx for a maximal monotone operator T in a uniformly smooth and uniformly convex Banach space X. Strong and weak convergence results of these two hybrid proximal-point algorithms are established, respectively. The research of L.C. Ceng was partially supported by the National Science Foundation of China (10771141), Ph.D. Program Foundation of Ministry of Education of China (20070270004), Science and Technology Commission of Shanghai Municipality Grant (075105118), Innovation Program of Shanghai Municipal Education Commission (09ZZ133), and Shanghai Leading Academic Discipline Project (S30405). The research of J.C. Yao was partially supported by Grant NSC 97-2115-M-110-001. Research was carried on within the agreement between National Sun Yat-Sen University of Kaohsiung, Taiwan and Pisa University, Pisa, Italy, 2008.     

Using AI methodologies in mathematical modeling of production systems

This research was supported in part by Sandia National Laboratories Grant No. 56-4617. Sandia is managed by AT&;T Technologies for the U.S. Department of Energy.     

A bound for the optimum relaxation factor for the successive overrelaxation method

Summary An upper bound on the optimum relaxation factor for use with the successive overrelaxation method is derived for a class of linear systems arising from the numerical solution by finite difference methods of a boundary value problem involving the self-adjoint differential equationWork on this paper was supported in part by the U. S. Army Research Office (Durham) through Grant DA-ARO(D)-31-124-G 1050 and by the National Science Foundation through Grant GP-8442 with The University of Texas at Austin.     

Solving combinatorial optimization problems using Karmarkar's algorithm

We describe a cutting plane algorithm for solving combinatorial optimization problems. The primal projective standard-form variant of Karmarkar's algorithm for linear programming is applied to the duals of a sequence of linear programming relaxations of the combinatorial optimization problem.Computational facilities provided by the Cornell Computational Optimization Project supported by NSF Grant DMS-8706133 and by the Cornell National Supercomputer Facility. The Cornell National Supercomputer Facility is a resource of the Center for Theory and Simulation in Science and Engineering at Cornell Unversity, which is funded in part by the National Science Foundation, New York State, and the IBM Corporation. The research of both authors was partially supported by the U.S. Army Research Office through the Mathematical Sciences Institute of Cornell University.Research partially supported by ONR Grant N00014-90-J-1714.Research partially supported by NSF Grant ECS-8602534 and by ONR Contract N00014-87-K-0212.     

Diameter,width, closest line pair,and parametric searching

We apply Megiddo's parametric searching technique to several geometric optimization problems and derive significantly improved solutions for them. We obtain, for any fixed ε>0, anO(n ^1+ε) algorithm for computing the diameter of a point set in 3-space, anO(^8/5+ε) algorithm for computing the width of such a set, and onO(n ^8/5+ε) algorithm for computing the closest pair in a set ofn lines in space. All these algorithms are deterministic. Work by Bernard Chazelle was supported by NSF Grant CCR-90-02352. Work by Herbert Edelsbrunner was supported by NSF Grant CCR-89-21421. Work by Leonidas Guibas and Micha Sharir was supported by a grant from the U.S.-Israeli Binational Science Foundation. Work by Micha Sharir was also supported by ONR Grant N00014-90-J-1284, by NSF Grant CCR-89-01484, and by grants from the Fund for Basic Research administered by the Israeli Academy of Sciences, and the G.I.F., the German-Israeli Foundation for Scientific Research and Development.     

Local convergence of interior-point algorithms for degenerate monotone LCP

Most asymptotic convergence analysis of interior-point algorithms for monotone linear complementarity problems assumes that the problem is nondegenerate, that is, the solution set contains a strictly complementary solution. We investigate the behavior of these algorithms when this assumption is removed.The work of this author was based on research supported by the National Science Foundation under grant DDM-9109404 and the Office of Naval Research under grant N00014-93-1-0234.The work of this author was based on research supported by the Office of Scientific Computing, U.S. Department of Energy, under Contract W-31-109-Eng-38.     

Approximating maximum independent sets by excluding subgraphs

An approximation algorithm for the maximum independent set problem is given, improving the best performance guarantee known toO(n/(logn)²). We also obtain the same performance guarantee for graph coloring. The results can be combined into a surprisingly strongsimultaneous performance guarantee for the clique and coloring problems.The framework ofsubgraph-excluding algorithms is presented. We survey the known approximation algorithms for the independent set (clique), coloring, and vertex cover problems and show how almost all fit into that framework. We show that among subgraph-excluding algorithms, the ones presented achieve the optimal asymptotic performance guarantees.A preliminary version of this paper appeared in [9].Supported in part by National Science Foundation Grant CCR-8902522 and PYI Award CCR-9057488.Research done at Rutgers University. Supported in part by Center for Discrete Mathematics and Theoretical Computer Science (DIMACS) fellowship.     

Interior-point methods for convex programming

This work is concerned with generalized convex programming problems, where the objective function and also the constraints belong to a certain class of convex functions. It examines the relationship of two basic conditions used in interior-point methods for generalized convex programming—self-concordance and a relative Lipschitz condition—and gives a short and simple complexity analysis of an interior-point method for generalized convex programming. In generalizing ellipsoidal approximations for the feasible set, it also allows a geometrical interpretation of the analysis.This work was supported by a research grant from the Deutsche Forschungsgemeinschaft, and in part by the U.S. National Science Foundation Grant DDM-8715153 and the Office of Naval Research Grant N00014-90-J-1242.On leave from the Institut für Angewandte Mathematik, University of Würzburg, Am Hubland, W-8700 Würzburg, Federal Republic of Germany.     

An optimization problem from linear filtering with quantum measurements

We consider the problem of optimal (in the sense of minimum error variance) linear filtering a vector discrete-time signal process, which influences a quantum mechanical field, utilizing quantum mechanical measurements. The nonclassical characteristic of the problem is the joint optimization over the measurement process and the linear signal processing scheme. The problem is formulated as an optimization problem of a functional over a set of operator-valued measures and matrices. We prove existence of optimal linear filters and provide necessary and sufficient conditions for optimality.This work was partially supported by the National Science Foundation under Grant ENG 75-20900 and by U.S. ARO Contract DAAG-39-83-C-0028.