Approximation of the solution of certain nonlinear ODEs with linear complexity

We study the positive stationary solutions of a standard finite-difference discretization of the semilinear heat equation with nonlinear Neumann boundary conditions. We prove that there exists a unique solution of such a discretization, which approximates the unique positive stationary solution of the “continuous” equation. Furthermore, we exhibit an algorithm computing an ε-approximation of such a solution by means of a homotopy continuation method. The cost of our algorithm is linear in the number of nodes involved in the discretization and the logarithm of the number of digits of approximation required.     

Homotopy method for generalized eigenvalue problems Ax= ΛBx

Generalized eigenvalue problems can be considered as a system of polynomials. The homotopy continuation method is used to find all the isolated zeros of the polynomial system which corresponds to the eigenpairs of the generalized eigenvalue problem. A special homotopy is constructed in such a way that there are exactly n distinct smooth curves connecting trivial solutions to desired eigenpairs. Since the curves followed by general homotopy curve following scheme are computed independently of one another, the algorithm is a likely candidate for exploiting the advantages of parallel processing to the generalized eigenvalue problems.     

A homotopy method for nonlinear semidefinite programming

In this paper, for solving the nonlinear semidefinite programming problem, a homotopy is constructed by using the parameterized matrix inequality constraint. Existence of a smooth path determined by the homotopy equation, which starts from almost everywhere and converges to a Karush–Kuhn–Tucker point, is proven under mild conditions. A predictor-corrector algorithm is given for numerically tracing the smooth path. Numerical tests with nonlinear semidefinite programming formulations of several control design problems with the data contained in COMPl _e ib are done. Numerical results show that the proposed algorithm is feasible and applicable.     

Decomposable norm minimization with proximal-gradient homotopy algorithm

We study the convergence rate of the proximal-gradient homotopy algorithm applied to norm-regularized linear least squares problems, for a general class of norms. The homotopy algorithm reduces the regularization parameter in a series of steps, and uses a proximal-gradient algorithm to solve the problem at each step. Proximal-gradient algorithm has a linear rate of convergence given that the objective function is strongly convex, and the gradient of the smooth component of the objective function is Lipschitz continuous. In many applications, the objective function in this type of problem is not strongly convex, especially when the problem is high-dimensional and regularizers are chosen that induce sparsity or low-dimensionality. We show that if the linear sampling matrix satisfies certain assumptions and the regularizing norm is decomposable, proximal-gradient homotopy algorithm converges with a linear rate even though the objective function is not strongly convex. Our result generalizes results on the linear convergence of homotopy algorithm for \(\ell _1\)-regularized least squares problems. Numerical experiments are presented that support the theoretical convergence rate analysis.     

Weak convergence of semimartingales and discretisation methods

Given a semimartingale one can construct a system (λ, A, B, C) where λ is the distribution of the initial value and (A, B, C) is the triple of global characteristics. Thus, given a process X and a system (λ, A, B, C) one can look for all probability measures P such that X is a P-semimartingale with initial distribution λ and global characteristics (A, B, C). We say that such a measure P is a solution to the semimartingale problem (λ, A, B, C).The paper is devoted to the study of a special type of semimartingale problem. We look for sufficient conditions to insure the existence of solutions and we develop a method to construct them by means of time-discretised schemes, using weak topology for probability measures.     

Implications of large-cardinal principles in homotopical localization

The existence of arbitrary cohomological localizations on the homotopy category of spaces has remained unproved since Bousfield settled the same problem for homology theories in the decade of 1970. This is related with another open question, namely whether or not every homotopy idempotent functor on spaces is an f-localization for some map f. We prove that both questions have an affirmative answer assuming the validity of a suitable large-cardinal axiom from set theory (Vopěnka's principle). We also show that it is impossible to prove that all homotopy idempotent functors are f-localizations using the ordinary ZFC axioms of set theory (Zermelo-Fraenkel axioms with the axiom of choice), since a counterexample can be displayed under the assumption that all cardinals are nonmeasurable, which is consistent with ZFC.     

An application of homotopy to solving linear programs

Consider a linear program inm inequality constraints andn nonnegative variables. An application of homotopy to the problem gives an algorithm similar to Dantzig's self-dual method. Howeve, the homotopy approach allows one to recognize several previously undescribed and potentially interesting properties. For example, the algorithm can be initiated in such a way as to produce a path which is primal-dual feasible. Moreover, one can theoretically identify an orthant with the property that if one initiates the algorithm at any point in that orthant then, after a ‘phase I’ requiring at most min{m, n} pivots, convergence is obtained in one step.     

Simultaneous semi-eigenvectors for matrices over an extremal algebra

We consider a process withn jobs which is repeated in a periodic manner. This problem can be described by a “simultaneous semi-eigenvector problem”: Find all feasible periods λ for which there exists a time schedule x fulfilling $$\max _{u = 1}^n \left( {x_u + \alpha _{uv} } \right) \leqslant x_v $$ . Letd(λ): =x _n ?x ₁ be the minimum duration of one single process during one cycle under the restriction that the complete system is operated with period λ. We show thatd(λ) is a decreasing and piecewise linear function and we present a polynomial algorithm to calculate this function explicitly.     

Regenerative cascade homotopies for solving polynomial systems

A key step in the numerical computation of the irreducible decomposition of a polynomial system is the computation of a witness superset of the solution set. In many problems involving a solution set of a polynomial system, the witness superset contains all the needed information. Sommese and Wampler gave the first numerical method to compute witness supersets, based on dimension-by-dimension slicing of the solution set by generic linear spaces, followed later by the cascade homotopy of Sommese and Verschelde. Recently, the authors of this article introduced a new method, regeneration, to compute solution sets of polynomial systems. Tests showed that combining regeneration with the dimension-by-dimension algorithm was significantly faster than naively combining it with the cascade homotopy. However, in this article, we combine an appropriate randomization of the polynomial system with the regeneration technique to construct a new cascade of homotopies for computing witness supersets. Computational tests give strong evidence that regenerative cascade is superior in practice to previous methods.     

An adaptive homotopy approach for non-selfadjoint eigenvalue problems

This paper presents adaptive algorithms for eigenvalue problems associated with non-selfadjoint partial differential operators. The basis for the developed algorithms is a homotopy method which departs from a well-understood selfadjoint problem. Apart from the adaptive grid refinement, the progress of the homotopy as well as the solution of the iterative method are adapted to balance the contributions of the different error sources. The first algorithm balances the homotopy, discretization and approximation errors with respect to a fixed stepsize τ in the homotopy. The second algorithm combines the adaptive stepsize control for the homotopy with an adaptation in space that ensures an error below a fixed tolerance ε. The outcome of the analysis leads to the third algorithm which allows the complete adaptivity in space, homotopy stepsize as well as the iterative algebraic eigenvalue solver. All three algorithms are compared in numerical examples.     

k L-list λ colouring of graphs

The k L-list λ colouring of a graph G is an L-list colouring (with positive integers) where any two colours assigned to adjacent vertices do not belong to a set λ, where the avoided assignments are listed. Moreover, the length of the list L(x), for every vertex x of G, must be less than or equal to a positive integer k, where k is the number of colours. This problem is NP-complete and we present an efficient heuristic algorithm to solve it. A fundamental aspect of the algorithm we developed is a particular technique of backtracking that permits the direct reassignment of the vertices causing the conflict if, at the moment of assigning a colour to a vertex, no colour on the list associated to it is available. An application of this algorithm to the problem of assigning arriving or leaving trains to the available tracks at a railway station is also discussed.     

On homotopy varieties

Given an algebraic theory T, a homotopy T-algebra is a simplicial set where all equations from T hold up to homotopy. All homotopy T-algebras form a homotopy variety. We will give a characterization of homotopy varieties analogous to the characterization of varieties.     

A stable approach to the equivariant Hopf theorem

Let G be a finite group. For semi-free G-manifolds which are oriented in the sense of Waner [S. Waner, Equivariant RO(G)-graded bordism theories, Topology and its Applications 17 (1984) 1-26], the homotopy classes of G-equivariant maps into a G-sphere are described in terms of their degrees, and the degrees occurring are characterised in terms of congruences. This is first shown to be a stable problem, and then solved using methods of equivariant stable homotopy theory with respect to a semi-free G-universe.     

Optimization and homotopy methods for the Gibbs free energy of simple magmatic mixtures

In this paper we consider a mathematical model for magmatic mixtures based on the Gibbs free energy. Different reformulations of the problem are presented and some theoretical results about the existence and number of solutions are derived. Finally, two homotopy methods and a global optimization one are introduced and computationally tested. One of the homotopy methods returns a single solution of the problem, while the other is able to return multiple solutions (often all of them). The global optimization method is a branch-and-reduce one with a theoretical guarantee of detecting all the solutions, although some numerical difficulties, resulting in a loss of a few of them, may have to be faced.     

Strong homotopy induced by adjacency structure

This paper generalizes the concept of SA-homotopy in finite topological adjacency category, which is introduced in our previous work, to graph category and discusses its properties. We prove that every SA-strong deformation retract of a simple graph G could be obtained by removing trivial vertices one by one, which makes it possible to allow an iterative algorithm of finding all SA-strong deformation retracts of G. We also obtain that two simple graphs are SA-homotopy equivalent if and only if they have graph isomorphic cores. Compared with the graph homotopy transformation defined by S.T. Yau et al. and the s-homotopy transformation defined by R. Boulet et al., the main advantage of SA-homotopy transformation is that it could reflect correspondences between vertices, and hence it more accurately describe the transformation process than the graph homotopy transformation and s-homotopy transformation. As an application of SA-homotopy on graphs, we introduce the mapping class group of a graph, which also shows its advantage over the graph homotopy transformation and the s-homotopy transformation.     

Homotopy theory and simplicial groupoids

The homotopy theory of simplical groups is well known [2, Ch. VI] to be equivalent to the pointed homotopy theory of reduced (i.e. only one vertex) simplicial sets (by means of a pair of adjoint functors G and W̄.The aim of this note is to show that similarly, the homotopy theory of simplical groupoids is equivalent to the (unpointed) homotopy theory of (all) simplical sets. This we do by

• 1.(i) showing that the category of simplicial groupoids admits a closed model catagory structure in the sense of Quillen [3], and
• 2.(ii) extending the functors G and W̄ to pair of adjoint functors

G: (simplicial sets)↔(simplicial groupoids): W̄ which induce the desired equivalence of homotopy theories.We also show that the category of simplical groupoids admits a simplical structure which produces “function complexes” and “simplical monoids of self homotopy equivalences” of the correct homotopy types.     

Linear splicing and syntactic monoid

Splicing systems were introduced by Head in 1987 as a formal counterpart of a biological mechanism of DNA recombination under the action of restriction and ligase enzymes. Despite the intensive studies on linear splicing systems, some elementary questions about their computational power are still open. In particular, in this paper we face the problem of characterizing the proper subclass of regular languages which are generated by finite (Paun) linear splicing systems. We introduce here the class of marker languages L, i.e., regular languages with the form L=L₁[x]₁L₂, where L₁,L₂ are regular languages, [x] is a syntactic congruence class satisfying special conditions and [x]₁ is either equal to [x] or equal to [x]∪{1}, 1 being the empty word. Using classical properties of formal language theory, we give an algorithm which allows us to decide whether a regular language is a marker language. Furthermore, for each marker language L we exhibit a finite Paun linear splicing system and we prove that this system generates L.     

Small embeddings of partial directed triple systems and partial triple systems with even λ

In 1976, Lindner and Rosa (Ars Combin. 1 (1976), 159–166) showed that a partial triple system with λ > 1 can be embedded in a finite triple system with the same λ. This result is improved in the case when λ is even by embedding a partial triple system on υ symbols in a triple system on t symbols, t ≡ 0,1 (mod 3), for all t >/ 3(λυ² + υ(2 ? λ) + 1). In the process, it is shown that for any λ >/ 1, a partial directed triple system on υ symbols can be embedded in a directed triple system on t symbols, t ≡ 0, 1 (mod 3), for all t ? 6λv² + 6v(1 ? λ) + 3, thus generalizing a result of Hamm (Proceedings, 14th Southeastern Conf. on Combinatorics, Graph Theory, and Computing, Boca Raton, Florida, 1983).