Determinantal singularities and newton polyhedra

Topological invariants of determinantal singularities are studied in terms of Newton polyhedra. The approach is based on the notion of a toric resolution of a determinantal singularity. Computations are carried out in the more general setting of “elimination theory in the context of Newton polyhedra.”     

On Goulden-Jackson’s Determinantal Formula for the Immanant

In 1992, Goulden and Jackson found a beautiful determinantal expression for the immanant of a matrix. This paper proves the same result combinatorially. We also present a β-extension of the theorem and a simple determinantal expression for the irreducible characters of the symmetric group.     

The Bhattacharya Function of Complete Monomial Ideals in Two Variables

We give explicit formulas for the Bhattacharya function of 𝔪-primary complete monomial ideals in two variables in terms of the vertices of the Newton polyhedra or in terms of the decompositions of the ideals as products of simple ideals.     

Element number of the Platonic solids

Let Σ be a set of polyhedra. A set Ω of polyhedra is said to be an element set for Σ if each polyhedron in Σ is the union of a finite number of polyhedra in Ω. We call each polyhedron of the element set Ω an element for Σ. In this paper, we determine one element set for the set Π of the Platonic solids, and prove that this element set is, in fact, best possible; it achieves the minimum in terms of cardinality among all the element sets for Π. We also introduce the notion of indecomposability of a polyhedron and present a conjecture in Sect. 3.     

Newton polyhedra (resolution of singularities)

Some results are presented on the resolution of singularities and compactification of an algebraic manifold determined by a system of algebraic equations with fixed Newton polyhedra and rather general coefficients. Resolution and compactification are carried out by means of smooth toric manifolds which are described in the first half of the survey.Translated from Itogi Nauki i Tekhniki, Seriya Sovremennye Problemy Matematiki, Vol. 22, pp. 207–239, 1983.     

On The Effective Computation Of Łojasiewicz Exponents Via Newton Polyhedra

In this paper we give some conclusions on Newton non-degenerate analytic map germs on Kn (K = ? or ?), using information from their Newton polyhedra. As a consequence, we obtain the exact value of the Lojasiewicz exponent at the origin of Newton non-degenerate analytic map germs. In particular, we establish a connection between Newton non-degenerate ideals and their integral closures, thus leading to a simple proof of a result of Saia. Similar results are also considered to polynomial maps which are Newton non-degenerate at infinity.     

Generating functions for plane partitions of a given shape

For fixed integers α and β, planar arrays of integers of a given shape, in which the entries decrease at least by α along rows and at least by β along columns, are considered. For various classes of these (α,β)-plane partitions we compute three different kinds of generating functions. By a combinatorial method, determinantal expressions are obtained for these generating functions. In special cases these determinants may be evaluated by a simple determinant lemma. All known results concerning plane partitions of a given shape are included. Thus our approach of a given shape provides a uniform proof method and yields numerous generalizations of known results.     

Packing and covering a tree by subtrees

For two polyhedra associated with packing subtrees of a tree, the structure of the vertices is described, and efficient algorithms are given for optimisation over the polyhedra. For the related problem of covering a tree by subtrees, a reduction to a packing problem, and an efficient algorithm are presented when the family of trees is “fork-free”.     

On the convergence of the Newton/log-barrier method

In the Newton/log-barrier method, Newton steps are taken for the log-barrier function for a fixed value of the barrier parameter until a certain convergence criterion is satisfied. The barrier parameter is then decreased and the Newton process is repeated. A naive analysis indicates that Newton’s method does not exhibit superlinear convergence to the minimizer of each instance of the log-barrier function until it reaches a very small neighborhood, namely within O(μ²) of the minimizer, where μ is the barrier parameter. By analyzing the structure of the barrier Hessian and gradient in terms of the subspace of active constraint gradients and the associated null space, we show that this neighborhood is in fact much larger –O(μ^σ) for any σ∈(1,2] – thus explaining why reasonably fast local convergence can be attained in practice. Moreover, we show that the overall convergence rate of the Newton/log-barrier algorithm is superlinear in the number of function/derivative evaluations, provided that the nonlinear program is formulated with a linear objective and that the schedule for decreasing the barrier parameter is related in a certain way to the step length and convergence criteria for each Newton process. Received: October 10, 1997 / Accepted: September 10, 2000?Published online February 22, 2001     

Stein domains and branched shadows of 4-manifolds

We provide sufficient conditions assuring that a suitably decorated 2-polyhedron can be thickened to a compact four-dimensional Stein domain. We also study a class of flat polyhedra in 4-manifolds and find conditions assuring that they admit Stein, compact neighborhoods. We base our calculations on Turaev’s shadows suitably “smoothed”; the conditions we find are purely algebraic and combinatorial. Applying our results, we provide examples of hyperbolic 3-manifolds admitting “many” positive and negative Stein fillable contact structures, and prove a four-dimensional analog of Oertel’s result on incompressibility of surfaces carried by branched polyhedra.      

A feasible semismooth asymptotically Newton method for mixed complementarity problems

 Semismooth Newton methods constitute a major research area for solving mixed complementarity problems (MCPs). Early research on semismooth Newton methods is mainly on infeasible methods. However, some MCPs are not well defined outside the feasible region or the equivalent unconstrained reformulations of other MCPs contain local minimizers outside the feasible region. As both these problems could make the corresponding infeasible methods fail, more recent attention is on feasible methods. In this paper we propose a new feasible semismooth method for MCPs, in which the search direction asymptotically converges to the Newton direction. The new method overcomes the possible non-convergence of the projected semismooth Newton method, which is widely used in various numerical implementations, by minimizing a one-dimensional quadratic convex problem prior to doing (curved) line searches. As with other semismooth Newton methods, the proposed method only solves one linear system of equations at each iteration. The sparsity of the Jacobian of the reformulated system can be exploited, often reducing the size of the system that must be solved. The reason for this is that the projection onto the feasible set increases the likelihood of components of iterates being active. The global and superlinear/quadratic convergence of the proposed method is proved under mild conditions. Numerical results are reported on all problems from the MCPLIB collection [8]. Received: December 1999 / Accepted: March 2002 Published online: September 5, 2002 RID="★" ID="★" This work was supported in part by the Australian Research Council. Key Words. mixed complementarity problems – semismooth equations – projected Newton method – convergence AMS subject classifications. 90C33, 90C30, 65H10     

On switching paths polyhedra

A class of integer polyhedra with totally dual integral (tdi) systems is proposed, which generalizes and unifies the “Switching Paths Polyhedra” of Hoffman (introduced in his generalization of Max Flow-Min Cut) and such polyhedra as the convex hull of (the incidence vectors of) all “path-closed sets” of an acyclic digraph, or the convex hull of all sets partitionable intok path-closed sets. As an application, new min-max theorems concerning the mentioned sets are given. A general lemma on when a tdi system of inequalities is box tdi is also given and used.     

On transformations of special spines and special polyhedra

Special spines of 3-manifolds and special polyhedra are examined. Special transformations of spines and polyhedra are considered. Two triangulations of the same 3-manifold are known to have a common stellar subdivision, and two Heegaard splittings of the same 3-manifold are stably equivalent. We prove similar assertions for spines and polyhedra. Spines with the structure of a branched surface are studied. Translated fromMatematicheskie Zametki, Vol. 65, No. 3, pp. 354–361, March, 1999.     

Nonflexible polyhedra with a small number of vertices

The paper shows which embedded and immersed polyhedra with no more than eight vertices are nonflexible. It turns out that all embedded polyhedra are nonflexible, except possibly for polyhedra of one of the combinatorial types, for which the problem still remains open. __________ Translated from Fundamentalnaya i Prikladnaya Matematika, Vol. 12, No. 1, pp. 143–165, 2006.     

Simple vertices of maximal minor polytopes

Themaximal minor polytope Π _{m, n} is the Newton polytope of the product of all maximal minors of anm×n matrix of indeterminates. The family of polytopes {Π _{m, n} } interpolates between the symmetric transportation polytope (form=n−1) and the permutohedron (form=2). Both transportation polytope and the permutohedron aresimple polytopes but in general Π _{m, n} is not simple. The main result of this paper is an explicit construction of a class of simple vertices of Π _{m, n} for generalm andn. We call themvertices of diagonal type. For every such vertexv we explicitly describe all the edges and facets of Π _{m, n} which containv. Simple vertices of Π _{m, n} have an interesting algebro-geometric application: they correspond tononsingular extreme toric degenerations of the determinantal variety ofm×n matrices not of full rank. Andrei Zelevinsky was partially supported by the NSF under Grant DMS-9104867.     

Simple geometric constructions of quadratically and cubically convergent iterative functions to solve nonlinear equations

In this paper, we derive one-parameter families of Newton, Halley, Chebyshev, Chebyshev-Halley type methods, super-Halley, C-methods, osculating circle and ellipse methods respectively for finding simple zeros of nonlinear equations, permitting f ′ (x) = 0 at some points in the vicinity of the required root. Halley, Chebyshev, super-Halley methods and, as an exceptional case, Newton method are seen as the special cases of the family. All the methods of the family and various others are cubically convergent to simple roots except Newton’s or a family of Newton’s method.      

On the Jacobian Newton polygon of plane curve singularities

We investigate the Jacobian Newton polygon of plane curve singularities. This invariant was introduced by Teissier in the more general context of hypersurfaces. The Jacobian Newton polygon determines the topological type of a branch (Merle’s result) but not of an arbitrary reduced curve (Eggers example). Our main result states that the Jacobian Newton Polygon determines the topological type of a non-degenerate unitangent singularity. The Milnor number, the Łojasiewicz exponent, the Hironaka exponent of maximal contact and the number of tangents are examples of invariants that can be calculated by means of the Jacobian Newton polygon. We show that the number of branches and the Newton number defined by Oka do not have this property. Dedicated to Professor Arkadiusz Płoski on his 60th birthday     

一类平面齐次多项式系统的局部相图

平面系统在动力系统的研究中起着重要的和基础的作用．在实系数系统情况下,本文利用奇点指数和牛顿多边形方法,讨论了一类平面齐次多项式系统在其孤立点附近的相图,同时给出一些奇点稳定的充要条件．     

Finite-element approximation for singularly perturbed nonlinear elliptic boundary-value problems

Numerical solution of a two-dimensional nonlinear singularly perturbed elliptic partial differential equation ∈ Δu = f(x, u), 0 < x, y < 1, with Dirichlet boundary condition is discussed here. The modified Newton method of third-order convergence is employed to linearize the nonlinear problem in place of the standard Newton method. The finite-element method is used to find the solution of the nonlinear differential equation. Numerical results are provided to demonstrate the usefulness of the method.     

Integral decomposition of polyhedra and some applications in mixed integer programming

 This paper addresses the question of decomposing an infinite family of rational polyhedra in an integer fashion. It is shown that there is a finite subset of this family that generates the entire family. Moreover, an integer analogue of Carathéodory's theorem carries over to this general setting. The integer decomposition of a family of polyhedra has some applications in integer and mixed integer programming, including a test set approach to mixed integer programming. Received: May 22, 2000 / Accepted: March 19, 2002 Published online: December 19, 2002 Key words. mixed integer programming – test sets – indecomposable polyhedra – Hilbert bases – rational polyhedral cones This work was supported partially by the DFG through grant WE1462, by the Kultusministerium of Sachsen Anhalt through the grants FKZ37KD0099 and FKZ 2945A/0028G and by the EU Donet project ERB FMRX-CT98-0202. The first named author acknowledges the hospitality of the International Erwin Schr?dinger Institute for Mathematical Physics in Vienna, where a main part of his contribution to this work has been completed. Mathematics Subject Classification (1991): 52C17, 11H31