Computing curve intersection by homotopy methods

Intersection problems are fundamental in computational geometry, geometric modeling and design and manufacturing applications, and can be reduced to solving polynomial systems. This paper introduces two homotopy methods, i.e. polyhedral homotopy method and linear homotopy method, to compute the intersections of two plane rational parametric curves. Extensive numerical examples show that computing curve intersection by homotopy methods has better accuracy, efficiency and robustness than by the Ehrlich–Aberth iteration method. Finally, some other applications of homotopy methods are also presented.     

Computing curve intersection by means of simultaneous iterations

A new algorithm is proposed for computing the intersection of two plane curves given in rational parametric form. It relies on the Ehrlich–Aberth iteration complemented with some computational tools like the properties of Sylvester and Bézout matrices, a stopping criterion based on the concept of pseudo-zero, an inclusion result and the choice of initial approximations based on the Newton polygon. The algorithm is implemented as a Fortran 95 module. From the numerical experiments performed with a wide set of test problems it shows a better robustness and stability with respect to the Manocha–Demmel approach based on eigenvalue computation. In fact, the algorithm provides better approximations in terms of the relative error and performs successfully in many critical cases where the eigenvalue computation fails.     

A Lyndon-Hochschild-Serre spectral sequence for certain homotopy fixed point spectra

Let and be closed subgroups of the extended Morava stabilizer group and suppose that is normal in . We construct a strongly convergent spectral sequence

where and are the continuous homotopy fixed point spectra of Devinatz and Hopkins. This spectral sequence turns out to be an Adams spectral sequence in the category of -local -modules.

     

A boundary perturbation interior point homotopy method for solving fixed point problems

In this paper, a boundary perturbation interior point homotopy method is proposed to give a constructive proof of the general Brouwer fixed point theorem and thus solve fixed point problems in a class of nonconvex sets. Compared with the previous results, by using the newly proposed method, initial points can be chosen in the whole space of Rn, which may improve greatly the computational efficiency of reduced predictor-corrector algorithms resulted from that method. Some numerical examples are given to illustrate the results of this paper.     

On exact solutions to partial differential equations by the modified homotopy perturbation method

Based on the modified homotopy perturbation method (MHPM), exact solutions of certain partial differential equations are constructed by separation of variables and choosing the finite terms of a series in p as exact solutions. Under suitable initial conditions, the PDE is transformed into an ODE. Some illustrative examples reveal the effciency of the proposed method.     

A simplicial homotopy algorithm for computing zero points on polytopes

ＡＳＩＭＰＬＩＣＩＡＬＨＯＭＯＴＯＰＹＡＬＧＯＲＩＴＨＭＦＯＲＣＯＭＰＵＴＩＮＧＺＥＲＯＰＯＩＮＴＳＯＮＰＯＬＹＴＯＰＥＳＣＨＥＮＫＡＩＺＨＯＵ（陈开周）;ＹＡＮＧＺＡＩＦＵ（杨再福）;ＬＩＡＮＧＺＨＥＮＧＬＩ（梁正礼）（ＤｅｐａｒｔｍｅｎｔｏｆＡｐ...     

Computing Numerical Singular Points of Plane Algebraic Curves

Given an irreducible plane algebraic curve of degree d ≥ 3,we compute its numerical singular points,determine their multiplicities,and count the number of distinct tangents at each to decide whether th...     

Edge intersection graphs of linear 3-uniform hypergraphs

Let be the class of edge intersection graphs of linear 3-uniform hypergraphs. It is known that the problem of recognition of the class is NP-complete. We prove that this problem is polynomially solvable in the class of graphs with minimum vertex degree ≥10. It is also proved that the class is characterized by a finite list of forbidden induced subgraphs in the class of graphs with minimum vertex degree ≥16.     

On the homotopy fixed point problem for free loop spaces and other function complexes

Let G be a finite group, let X and Y be finite G-complexes, and suppose that for each K G, Y ^K is dim(X ^K)-connected and simple. G acts on the function complex F(X, Y) by conjugation of maps. We give a complete analysis of the homotopy fixed point set of the space F(X, Y). As a corollary, we are able to analyze at a prime p, the homotopy fixed point set of the circle action on X, where X denotes the free loop space of X, and X is a simply connected finite complex.Supported in part by NSF DMS 86-02430.To A. Grothendieck on the occasion of his sixtieth birthday     

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.     

Enhanced intersection cutting-plane approach for linear complementarity problems

In this paper, we develop an enhanced intersection cutting-plane algorithm for solving a mixed integer 0–1 bilinear programming formulation of the linear complementarity problem (LCP). The matrixM associated with the LCP is not assumed to possess any special structure, except that the corresponding feasible region is assumed to be bounded. A procedure is described to generate cuts that are deeper versions of the Tuy intersection cuts, based on a relaxation of the usual polar set. The proposed algorithm then attempts to find an LCP solution in the process of generating either a single or a pair of such strengthened intersection cuts. The process of generating these cuts involves a vertexranking scheme that either finds an LCP solution, or else these cuts eliminate the entire feasible region leading to the conclusion that no LCP solution exists. Computational experience on various test problems is provided.This material is based upon work supported by the National Science Foundation under Grant No. DMII-9121419 to the first author and Grant No. DMII-9114489 to the third author. The authors gratefully acknowledge the constructive suggestions of a referee that helped focus the approach and its presentation.     

Optimal design by a homotopy method

An optimal design problem is formulated as a system of nonlinear equations rather than the extremum of a functional. Based on a new homotopy method, an algorithm is developed for solving the nonlinear system which is globally convergent with probability one. Since no convexity is required, the nonlinear system may have more than one solution. The algorithm will produce an optimal design solution for a given starting point. For most engineering problems, the initial prototype design is already well conceived and close to the global optimal solution. Such a starting point usually leads to the optimal design by the homotopy method, even though Newton's method may diverge from that starting point. A simple example is given.     

The combined Laplace transform and new homotopy perturbation methods for stiff systems of ODEs

In this paper, we propose new technique for solving stiff system of ordinary differential equations. This algorithm is based on Laplace transform and homotopy perturbation methods. The new technique is applied to solving two mathematical models of stiff problem. We show that the present approach is relatively easy, efficient and highly accurate.     

Application of homotopy perturbation methods for solving systems of linear equations

In this paper, homotopy perturbation methods (HPMs) are applied to obtain the solution of linear systems, and conditions are deduced to check the convergence of the homotopy series. Moreover, we have adapted the Richardson method, the Jacobi method, and the Gauss-Seidel method to choose the splitting matrix. The numerical results indicate that the homotopy series converges much more rapidly than the direct methods for large sparse linear systems with a small spectrum radius.     

Solution of Davey-Stewartson equations by homotopy perturbation method

In this paper, we extend the homotopy perturbation method to solve the Davey-Stewartson equations. The homotopy perturbation method is employed to compute an approximation to the solution of the equations. Computation the absolute errors between the exact solutions of the Davey-Stewartson equations and the HPM solutions are presented. Some plots are given to show the simplicity the method. The article is published in the original.     

Analytical solutions to nonlinear equations arising in heat transfer by variational iteration,homotopy perturbation,and Adomian decomposition methods

As thermal conductivity plays an important role on fin efficiency, we tried to solve heat transfer equation with thermal conductivity as a function of temperature. In this research, some new analytical methods called homotopy perturbation method, variational iteration method, and Adomian decomposition method are introduced to be applied to solve the nonlinear heat transfer equations, and also the comparison of the applied methods (together) is shown graphically. © 2009 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 2010     

Generalized inflection points of very general line bundles on smooth curves

Let L be an invertible sheaf on a smooth curve C. A generalized inflection point of L is an inflection point of for some integer n > 0. A generalized inflection point P of L is called strongly normal if there is a unique integer n > 0 such that P is an inflection point of and moreover its inflection weight is equal to 1. In case L is a very general invertible sheaf of degree x on C then all generalized inflection points of L are strongly normal. The author is affiliated with the University of Leuven as a research fellow Partially supported by the Fund of Scientific Research, Flanders (G.0318.06).     

Exact solutions for nonlinear Burgers' equation by homotopy perturbation method

The aim of this article is to construct a new efficient recurrent relation to solve nonlinear Burgers' equation. The homotopy perturbation method is used to solve this equation. Because Burgers' equation arises in many applications, it is worth trying new solution methods. Comparison of the results with those of Adomian's decomposition method leads to significant consequences. Four standard problems are used to illustrate the method. © 2008 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2009     

Numerical solutions of partial differential equations by discrete homotopy analysis method

This paper introduces a discrete homotopy analysis method (DHAM) to obtain approximate solutions of linear or nonlinear partial differential equations (PDEs). The DHAM can take the many advantages of the continuous homotopy analysis method. The proposed DHAM also contains the auxiliary parameter ?, which provides a simple way to adjust and control the convergence region of solution series. The convergence of the DHAM is proved under some reasonable hypotheses, which provide the theoretical basis of the DHAM for solving nonlinear problems. Several examples, including a simple diffusion equation and two-dimensional Burgers’ equations, are given to investigate the features of the DHAM. The numerical results obtained by this method have been compared with the exact solutions. It is shown that they are in good agreement with each other.