Conjugate-gradient method for computing the Moore-Penrose inverse and rank of a matrix

A conjugate-gradient method is developed for computing the Moore-Penrose generalized inverseA of a matrix and the associated projectors, by using the least-square characteristics of both the method and the inverseA . Two dual algorithms are introduced for computing the least-square and the minimum-norm generalized inverses, as well asA . It is shown that (i) these algorithms converge for any starting approximation; (ii) if they are started from the zero matrix, they converge toA ; and (iii) the trace of a sequence of approximations multiplied byA is a monotone increasing function converging to the rank ofA. A practical way of compensating the self-correcting feature in the computation ofA is devised by using the duality of the algorithms. Comparison with Ben-Israel's method is made through numerical examples. The conjugate-gradient method has an advantage over Ben-Israel's method.After having completed the present paper, the author received from Professor M. R. Hestenes his paper entitledPseudo Inverses and Conjugate Gradients. This paper treated the same subject and appeared in Communications of the ACM, Vol. 18, pp. 40–43, 1975.     

Asymptotics of the generating function for the volume of the Wiener sausage

Summary We consider the generating function of the voltime of the Wiener sausageC (t), which is the -neighbourhood of the Wiener path in the time interval [0,t]. For <0, the limiting behavior fort, up to logarithmic equivalence, had been determined in a celebrated work of Donsker and Varadhan. For >0 it had been investigated by van den Berg and Tóth, but in contrast to the case <0, there is no simple expression for the exponential rate known. We determine the asymptotic behaviour of this rate for small and large .     

Stochastic bounds on distributions of optimal value functions with applications to pert,network flows and reliability

In various network models the quantities of interest are optimal value functions of the form max X _i , min X _i , min maxX _i , max minX _i , where the inner operation is on the nodes of a path/cut and the outer operation on all paths/cuts, e.g. shortest path of a project network, maximal flow of a flow network or lifetime of a reliability system. ForX _i random with given marginal distributions, we obtain bounds for the optimal value functions, based on common and on antithetic joint distributions.This work was carried out during a visit to RWTH Aachen, supported by DAAD.     

A certain periodic control problem for differential equations with impulses in the space of bounded numerical sequences

One considers the differential equation dx/dt=f(t, x) with the impulse action ¦_t=t_i=H_i(t_i,x) in the space of bounded numerical sequences, where f(t, x), H_i(t, x) are T-periodic, countable-dimensional vector-valued functions, is a positive parameter. One gives conditions for the existence of a control (₁,₂) such that the solution of the equation dx/dt=f(t, x)–₁ with impulse action x¦_t=t_i=H_i(t_i,x)–₂ assuming for t= the value x=x₀, be T-periodic.Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 42, No. 2, pp. 271–275, February, 1990.     

A matroid algorithm and its application to the efficient solution of two optimization problems on graphs

We address the problem of finding a minimum weight baseB of a matroid when, in addition, each element of the matroid is colored with one ofm colors and there are upper and lower bound restrictions on the number of elements ofB with colori, fori = 1, 2,,m. This problem is a special case of matroid intersection. We present an algorithm that exploits the special structure, and we apply it to two optimization problems on graphs. When applied to the weighted bipartite matching problem, our algorithm has complexity O(|EV|+|V| ²log|V|). HereV denotes the node set of the underlying bipartite graph, andE denotes its edge set. The second application is defined on a general connected graphG = (V,E) whose edges have a weight and a color. One seeks a minimum weight spanning tree with upper and lower bound restrictions on the number of edges with colori in the tree, for eachi. Our algorithm for this problem has complexity O(|EV|+m ² |V|+ m|V| ²). A special case of this constrained spanning tree problem occurs whenV ^* is a set of pairwise nonadjacent nodes ofG. One must find a minimum weight spanning tree with upper and lower bound restrictions on the degree of each node ofV ^*. Then the complexity of our algorithm is O(|VE|+|V ^* V| ²). Finally, we discuss a new relaxation of the traveling salesman problem.This report was supported in part by NSF grant ECS 8601660.     

On the K shortest path trees problem

We address the problem of finding the K best path trees connecting a source node with any other non-source node in a directed network with arbitrary lengths. The main result in this paper is the proof that the kth shortest path tree is adjacent to at least one of the previous (k-1) shortest path trees. Consequently, we design an O(f(n,m,C_max)+Km) time and O(K+m) space algorithm to determine the K shortest path trees, in a directed network with n nodes, m arcs and maximum absolute length C_max, where O(f(n,m,C_max)) is the best time needed to solve the shortest simple paths connecting a source node with any other non-source node.     

Clifford algebra method for network expression,computation, and algorithm construction

Clifford algebra is introduced as a theoretical foundation for network topology expression and algorithm construction. Network nodes are coded with basis vectors in a vector space , and the edges and k‐walk routes can be expressed by 2‐blades and k‐blades, respectively, in the Clifford algebra Cl(n,0). The topologies among nodes, edges, and routes of networks can be directly calculated, and the network routes can be extended and traversed with oriented join products. The network algorithm construction processes based on Clifford algebra are instantiated by the single source shortest path algorithm. The experimental results on different scale random networks suggest that Clifford algebra is suited for network expression and relation computation. The Clifford algebra‐based shortest path algorithm is vivid and clear in geometric meaning and has great advantage on temporal and spatial complexity. Copyright © 2013 John Wiley & Sons, Ltd.     

Blow-up rates for parabolic systems

Let ⁿ be a bounded domain andB _R be a ball in ⁿ of radiusR. We consider two parabolic systems: ut=u +f(), i= +g(u) in × (0,T) withu=v=0 on × (0,T) andu _t =u, v _t =v inB _r × (0,T) withe/v=f (v), e/v=g(u) onB _R × (0,T). Whenf(v) andg(u) are power law or exponential functions, we establish estimates on the blow-up rates for nonnegative solutions of the systems.     

On the complete chromatic number of Halin graphs

ThisresearchissupportedbytheNationalNaturalScienceFoundationofChina.Write.1.IntroductionDefinition1.FOrany3-connectedplanargraphG(V,E,F)withA(G)23,iftheboundaryedgesoffacefowhichisadjacenttotheothersareremoved,itbecomesatree,andthedegreeofeachvertexofV(fo)is3,andthenGiscalledaHalingraph;foiscalledtheouterfaceofG,andtheotherscalledtheinteriorfaces,thevenicesonthefacefoarecalledtheoutervenices,theoillersarecalledtheinterior...ti..,tll.ForanyplanargraphG(V,E,F),f,f'eF,fisadjacenttof'ifan…     

Cohomological characterization of pseudoconvexity in a Banach space

Let X be a Banach space with a countable unconditional basis (e.g., X=₂), X open. We show that is pseudoconvex if and only if for each affine complex line L in X the sheaf cohomology group H ¹ (,I) vanishes, where I is the ideal sheaf of all holomorphic functions on that vanish on L. We also give an example that the condition H ^q (,)=0 for all q1 unlike in finite dimensions does not imply the pseudoconvexity of . Lastly, we prove an interpolation result. Mathematics Subject Classification (2002): 32T05, 46G20.     

Reliable Broadcasting in Logarithmic Time with Byzantine Link Failures

Broadcasting is a process of transmitting a message held in one node of a communication network to all other nodes. Links of the network are subject to randomly and independently distributed faults with probability; faults are permanent and Byzantine, while all nodes are fault-free. In a unit of time, each node can communicate with at most one other node. We present a broadcasting algorithm which works fornnodes in timeO(log n) with probability of correctness exceeding 1 − 1/n, for sufficiently largen.     

On Singularities of Generating Functions of Pólya Frequency Sequences of Finite Order

Let E be a closed set in C satisfying the conditions: (i) E is symmetric with respect to the real axis, (ii) E {z:|z|1} = . For any r 1 there exists a function f(z) satisfying the properties: (i) f(z) is a generating function of a Pólya frequency sequence of order r, (ii) the singularity set of f(z) is E {1}.     

Frattini Theory for Classes of Finite Universal Algebras of Malcev Varieties

We extend the Frattini theory of formations and Schunck classes of finite groups to some Frattini theory of formations and Schunck classes of finite universal algebras of Malcev varieties. We prove that if F(1) is a nonempty formation (Schunck class) of algebras of a Malcev variety, then its Frattini subformation (Frattini Schunck subclass) (F) consists of all nongenerators of F; moreover, if M is a formation (Schunck class) in F; then (M) (F).     

On certain quotients of Hardy spaces

The quotient space of a Hardy space on a half-plane Imz> modulo the subspace of elements containing a factore ^iz is in some sense independent of . A formula is derived which exhibits a correspondence between any two such quotient spaces.Supported by the Göran Gustafsson Foundation for Research in Natural Sciences and Medicine.     

Difference sets in dihedral groups

We study the existence of nontrivial (2m, k, )-difference sets in dihedral groups. Some nonexistence results are proved. In particular, we show that n = k – is odd and (n)/n < 1/2. Finally, a computer search shows that, except 5 undecided cases, no nontrivial difference set exists in dihedral groups for n 10⁶.     

On computational aspects of the realization of local algorithms for solution of problems of discrete optimization

Results of a computer experiment for a local algorithm in combination with algorithms of the Dispro under the solution of quasiblock problems of discrete programming are considered. The use of the relaxation scheme in the local algorithm is given.Translated from Dinamicheskie Sistemy, No. 9, pp. 117–122, 1990.     

Exact rates of convergence as <Emphasis Type="Italic">t</Emphasis> → +∞ for solutions of nonlinear evolution equations

We study the asymptotic behavior of solutions for a class of evolution problems in a Hilbert space, including those of the form

On hyperplanes and polytopes

We call a convex subsetN of a convexd-polytopePE ^d ak-nucleus ofP ifN meets everyk-face ofP, where 0<k<d. We note thatP has disjointk-nuclei if and only if there exists a hyperplane inE ^d which bisects the (relative) interior of everyk-face ofP, and that this is possible only if [d+2/2]kd–1. Our main results are that any convexd-polytope with at most 2d–1 vertices (d3) possesses disjoint (d–1)-nuclei and that 2d–1 is the largest possible number with this property. Furthermore, every convexd-polytope with at most 2d facets (d3) possesses disjoint (d–1)-nuclei, 2d cannot be replaced by 2d+2, and ford=3, six cannot be replaced by seven.Partially supported by Hung. Nat. Found. for Sci. Research number 1238.Partially supported by the Natural Sciences and Engineering Council of Canada.Partially supported by N.S.F. grant number MCS-790251.     

Cayley transform of the generator of a uniformly bounded <Emphasis Type="Italic">C</Emphasis><Subscript>0</Subscript>-semigroup of operators

We consider the problem of estimates for the powers of the Cayley transform V = (A + I)(A - I)^–1 of the generator of a uniformly bounded C ₀-semigroup of operators e ^tA , t 0, that acts in a Hilbert space H. In particular, we establish the estimate . We show that the estimate is true in the following cases: (a) the semigroups e ^tA and are uniformly bounded; (b) the semigroup e ^tA uniformly bounded for t is analytic (in particular, if the generator of the semigroup is a bounded operator).Translated from Ukrainskyi Matematychnyi Zhurnal, Vol. 56, No. 8, pp. 1018–1029, August, 2004.     

An efficient algorithm for solving semi-infinite inequality problems with box constraints

Many design objectives may be formulated as semi-infinite constraints. Examples in control design, for example, include hard constraints on time and frequency responses and robustness constraints. A useful algorithm for solving such inequalities is the outer approximations algorithm. One version of an outer approximations algorithm for solving an infinite set of inequalities(x, y) 0 for allyY proceeds by solving, at iterationi of the master algorithm, a finite set of inequalities ((x, y) 0 for allyY _i) to yieldx _i and then updatingY _i toY _i+1=Y _i {y_i } wherey _i arg max {(x _i,y)¦y Y}. Since global optimization is computationally extremely expensive, it is desirable to reduce the number of such optimizations. We present, in this paper, a modified version of the outer approximations algorithm which achieves this objective.The research reported herein was sponsored by the National Science Foundation Grants ECS-9024944, ECS-8816168, the Air Force Office of Scientific Research Contract AFOSR-90-0068, and the NSERC of Canada under Grant OGPO-138352.