Finding Mixed Cells in the Mixed Volume Computation

In practice, finding mixed cells in certain polyhedral subdivisions plays a dominating role when a polyhedral homotopy is employed to approximate all isolated zeros of polynomial systems. This paper gives a new algorithm for the mixed cell computation via a new formulation of the underlying linear programming problems. Numerical results show that the algorithm provides a major advance in the speed of computation with much less memory requirements.     

Mixed Volume Computation for Semi-Mixed Systems

Abstract. The Li—Li algorithm produced in [11] for the mixed volume computation of fully mixed polynomial systems is reconstructed in this article for general semi-mixed polynomial systems. Taking the special structure of the semi-mixed supports of the systems into account, the resulting algorithm, illustrated by numerical results, can dramatically speed up the mixed volume computation, especially when the systems are unmixed. Even when applied to fully mixed systems, the new algorithm improves the speed of the Li—Li algorithm by a considerable amount.     

Mixed Volume Computation for Semi-Mixed Systems

   Abstract. The Li—Li algorithm produced in [11] for the mixed volume computation of fully mixed polynomial systems is reconstructed in this article for general semi-mixed polynomial systems. Taking the special structure of the semi-mixed supports of the systems into account, the resulting algorithm, illustrated by numerical results, can dramatically speed up the mixed volume computation, especially when the systems are unmixed. Even when applied to fully mixed systems, the new algorithm improves the speed of the Li—Li algorithm by a considerable amount.     

非线性混合似变分不等式的扰动近似点-投影算法

In this paper we introduce a new perturbed proximal-projection algorithm for finding the common element of the set of fixed points of non-expansive mappings and the set of solutions of nonlinear mixed variational-like inequalities. The convergence criteria of the iterative sequences generated by the new iterative algorithm is also given. Our approach and results generalize many known results in this field.     

Boundary element methods for Maxwell's equations on non-smooth domains

Summary. Variational boundary integral equations for Maxwell's equations on Lipschitz surfaces in are derived and their well-posedness in the appropriate trace spaces is established. An equivalent, stable mixed reformulation of the system of integral equations is obtained which admits discretization by Galerkin boundary elements based on standard spaces. On polyhedral surfaces, quasioptimal asymptotic convergence of these Galerkin boundary element methods is proved. A sharp regularity result for the surface multipliers on polyhedral boundaries with plane faces is established. Received January 5, 2001 / Revised version received August 6, 2001 / Published online December 18, 2001 Correspondence to: C. Schwab     

A note on the numerical solution of linear recurrence relations

Summary A numerical algorithm for the computation of non-dominant solutions of linear recurrence relations is analysed. Several non-trivial improvements are made and the efficiency of the new algorithm is illustrated by means of some numerical examples.     

Fast computation of adaptive wavelet expansions

In this paper we describe and analyze an algorithm for the fast computation of sparse wavelet coefficient arrays typically arising in adaptive wavelet solvers. The scheme improves on an earlier version from Dahmen et al. (Numer. Math. 86, 49–101, 2000) in several respects motivated by recent developments of adaptive wavelet schemes. The new structure of the scheme is shown to enhance its performance while a completely different approach to the error analysis accommodates the needs put forward by the above mentioned context of adaptive solvers. The results are illustrated by numerical experiments for one and two dimensional examples.     

The relation between the Jacobi algorithm and inverse iteration and a Jacobi algorithm based on elementary reflections

It is shown that the cyclic Jacobi algorithm for the computation of eigenvalues of a symmetric matrix behaves asymptotically like inverse iteration with Rayleigh Quotient shift (RQI). The asymptotic expression for the transformation matrix is used to develop a new Jacobi algorithm which uses elementary reflections (Householder transformations) instead of rotations. The new algorithm has the same asymptotic behaviour, but each sweep needs half the number of arithmetic operations and has one level of looping less than the traditional one. Numerical tests of an APL implementation are reported.     

Counterexamples to the Connectivity Conjecture of the Mixed Cells

In [4] a conjecture concerning the connectivity of mixed cells of subdivisions for Minkowski sums of polytopes was formulated. This conjecture was, in fact, originally proposed by Pedersen [3]. It turns out that a positive confirmation of this conjecture can substantially speed up the algorithm for the ``dynamical lifting' developed in [4]. In the mean time, when the polyhedral method is used for solving polynomial systems by homotopy continuation methods [2], the positiveness of this conjecture also plays an important role in the efficiency of the algorithm. Very unfortunately, we found that this conjecture is inaccurate in general. In Section 1 a counterexample is presented for a general subdivision. In Section 2 another counterexample shows that even restricted to ``regular' subdivisions induced by liftings, this conjecture still fails to be true. Received September 18, 1996, and in revised form February 17, 1997.     

Mixed finite element methods for elastic rods of arbitrary geometry

Summary The boundary-value problem for rods having arbitrary geometry, and subjected to arbitrary loading, is studied within the context of the small-strain theory. The basic assumptions underlying the rod kinematics are those corresponding to the Timoshenko hypotheses in the plane rectilinear case: that is, plane sections normal to the line of centroids in the undeformed state remain plane, but not necessarily normal. The problem is formulated in both the standard and mixed variational forms, and after establishing the existence and uniqueness of solutions to these equivalent problems, the corresponding discrete problems are studied. Finite element approximations of the mixed problem are shown to be stable and convergent. It is shown that the equivalence between the mixed problem and the standard problem with selective reduced integration holds only for the case of rods having constant curvature and torsion, though. The results of numerical experiments are presented; these confirm the convergent behaviour of the mixed problem.     

Mixed-volume computation by dynamic lifting applied to polynomial system solving

The aim of this paper is to present a flexible approach for the efficient computation of the mixed volume of a tuple of polytopes. In order to compute the mixed volume, a mixed subdivision of the tuple of polytopes is needed, which can be obtained by embedding the polytopes in a higher-dimensional space, i.e., by lifting them. Dynamic lifting is opposed to the static approach. This means that one considers one point at a time and only fixes the value of the lifting function when the point really influences the mixed volume. Conservative lifting functions have been developed for this purpose. This provides us with a deterministic manipulation of the lifting for computing mixed volumes, which rules out randomness conditions. Cost estimates for the algorithm are given. The implications of dynamic lifting on polyhedral homotopy methods for the solution of polynomial systems are investigated and applications are presented.     

A Rigorous ODE Solver and Smale's 14th Problem

We present an algorithm for computing rigorous solutions to a large class of ordinary differential equations. The main algorithm is based on a partitioning process and the use of interval arithmetic with directed rounding. As an application, we prove that the Lorenz equations support a strange attractor, as conjectured by Edward Lorenz in 1963. This conjecture was recently listed by Steven Smale as one of several challenging problems for the twenty-first century. We also prove that the attractor is robust, i.e., it persists under small perturbations of the coefficients in the underlying differential equations. Furthermore, the flow of the equations admits a unique SRB measure, whose support coincides with the attractor. The proof is based on a combination of normal form theory and rigorous computations. July 27, 2000. Final version received: June 30, 2001.     

Mixed finite elements on sparse grids

Summary. This paper generalizes the idea of approximation on sparse grids to discrete differential forms that include )- and -conforming mixed finite element spaces as special cases. We elaborate on the construction of the spaces, introduce suitable nodal interpolation operators on sparse grids and establish their approximation properties. We discuss how nodal interpolation operators can be approximated. The stability of -conforming finite elements on sparse grids, when used to approximate second order elliptic problems in mixed formulation, is investigated both theoretically and in numerical experiments. Received November 2, 2000 / Revised version received October 23, 2001 / Published online January 30, 2002 This work was supported by DFG. This paper is dedicated to Ch. Zenger on the occasion of his 60th birthday.     

Strictly feasible equation-based methods for mixed complementarity problems

Summary.   We introduce a new algorithm for the solution of the mixed complementarity problem (MCP) which has stronger properties than most existing methods. In fact, typical solution methods for the MCP either generate feasible iterates but have to solve relatively complicated subproblems (like quadratic programs or linear complementarity problems), or they have relatively simple subproblems (like linear systems of equations) but generate not necessarily feasible iterates. The method to be presented here combines the nice features of these two classes of methods: It has to solve only one linear system of equations (of reduced dimension) at each iteration, and it generates feasible (more precisely: strictly feasible) iterates. The new method has some nice global and local convergence properties. Some preliminary numerical results will also be given. Received August 26, 1999 / Revised version recived April 11, 2000 / Published online February 5, 2001     

Dynamic allocation indices for restless projects and queueing admission control: a polyhedral approach

 This paper develops a polyhedral approach to the design, analysis, and computation of dynamic allocation indices for scheduling binary-action (engage/rest) Markovian stochastic projects which can change state when rested (restless bandits (RBs)), based on partial conservation laws (PCLs). This extends previous work by the author [J. Ni?o-Mora (2001): Restless bandits, partial conservation laws and indexability. Adv. Appl. Probab. 33, 76–98], where PCLs were shown to imply the optimality of index policies with a postulated structure in stochastic scheduling problems, under admissible linear objectives, and they were deployed to obtain simple sufficient conditions for the existence of Whittle's (1988) RB index (indexability), along with an adaptive-greedy index algorithm. The new contributions include: (i) we develop the polyhedral foundation of the PCL framework, based on the structural and algorithmic properties of a new polytope associated with an accessible set system -extended polymatroid}); (ii) we present new dynamic allocation indices for RBs, motivated by an admission control model, which extend Whittle's and have a significantly increased scope; (iii) we deploy PCLs to obtain both sufficient conditions for the existence of the new indices (PCL-indexability), and a new adaptive-greedy index algorithm; (iv) we interpret PCL-indexability as a form of the classic economics law of diminishing marginal returns, and characterize the index as an optimal marginal cost rate; we further solve a related optimal constrained control problem; (v) we carry out a PCL-indexability analysis of the motivating admission control model, under time-discounted and long-run average criteria; this gives, under mild conditions, a new index characterization of optimal threshold policies; and (vi) we apply the latter to present new heuristic index policies for two hard queueing control problems: admission control and routing to parallel queues; and scheduling a multiclass make-to-stock queue with lost sales, both under state-dependent holding cost rates and birth-death dynamics. Received: April 2000 / Accepted: October 2002 Published online: December 9, 2002 RID="★" ID="★" Work partly supported by the Spanish Ministry of Science and Technology (grant BEC2000-1027), NATO (Collaborative Linkage Grant PST.CLG.976568), and the Joint Spanish-US (Fulbright) Commission for Scientific and Technical Exchange (project 2000-20132) Key words. Markov decision process – restless bandits – polyhedral combinatorics – extended polymatroid – adaptive-greedy algorithm – dynamic allocation index – stochastic scheduling – threshold policy – index policy – Gittins index – Klimov index – Whittle index – control of queues – admission control – routing – make-to-stock – multiclass queue – finite buffers – conservation laws – achievable performance Mathematics Subject Classification (1991): (AMS 2000 Subject Classification): 90B36, 90B22, 90C40, 90C57, 90C08     

A New Finite Element Space for Expanded Mixed Finite Element Method

In this article, we propose a new finite element space Λ$_h$ for the expanded mixed finite element method (EMFEM) for second-order elliptic problems to guarantee its computing capability and reduce the computation cost. The new finite element space Λ$_h$ is designed in such a way that the strong requirement V$_h\subset$Λ$_h$ in [9] is weakened to {v$_h\in$V$_h$; divv$_h$=0}$\subset$Λ$_h$ so that it needs fewer degrees of freedom than its classical counterpart. Furthermore, the new Λ$_h$ coupled with the Raviart-Thomas space satisfies the inf-sup condition, which is crucial to the computation of mixed methods for its close relation to the behavior of the smallest nonzero eigenvalue of the stiff matrix, and thus the existence, uniqueness and optimal approximate capability of the EMFEM solution are proved for rectangular partitions in $\mathbb{R}^d, d=2,3$ and for triangular partitions in $\mathbb{R}^2$. Also, the solvability of the EMFEM for triangular partition in $\mathbb{R}^3$ can be directly proved without the inf-sup condition. Numerical experiments are conducted to confirm these theoretical findings.     

Some remarks on an ODE-solver of Kirchgraber

Summary Kirchgraber derived in 1988 an integration procedure (called the LIPS-code) for long-term prediction of the solutions of equations which are perturbations of systems having only periodic solutions. His basic idea is to use the Poincaré map to define a new system which can be integrated with large step-size; the method is specially successful when the period is close to the unperturbed one. Obviously the size of the perturbation modifies the period and therefore affects the precision of the algorithm. In this paper we propose a double modification of Kirchgraber's code: to use a first-order approximation of the perturbed period instead of the unperturbed one, and a scheme specially designed for integration of orbits instead of the Runge-Kutta method. We show that this new code permits a spectacular improvement in accuracy and computation time.     

Oriented Mixed Area and Discrete Minimal Surfaces

Recently a curvature theory for polyhedral surfaces has been established, which associates with each face a mean curvature value computed from areas and mixed areas of that face and its corresponding Gauss image face. Therefore a study of minimal surfaces requires studying pairs of polygons with vanishing mixed area. We show that the mixed area of two edgewise parallel polygons equals the mixed area of a derived polygon pair which has only the half number of vertices. Thus we are able to recursively characterize vanishing mixed area for hexagons and other n-gons in an incidence-geometric way. We use these geometric results for the construction of discrete minimal surfaces and a study of equilibrium forces in their edges, especially those with the combinatorics of a hexagonal mesh.     

An optimal C $^0$ finite element algorithm for the 2D biharmonic problem: theoretical analysis and numerical results

Summary. The aim of this paper is to give a new method for the numerical approximation of the biharmonic problem. This method is based on the mixed method given by Ciarlet-Raviart and have the same numerical properties of the Glowinski-Pironneau method. The error estimate associated to these methods are of order O(h) for k The algorithm proposed in this paper converges even for k, without any regularity condition on or . We have an error estimate of order O(h) in case of regularity. Received February 5, 1999 / Revised version received February 23, 2000 / Published online May 4, 2001     

The product-product singular value decomposition of matrix triplets

A new decomposition of a matrix triplet (A, B, C) corresponding to the singular value decomposition of the matrix productABC is developed in this paper, which will be termed theProduct-Product Singular Value Decomposition (PPSVD). An orthogonal variant of the decomposition which is more suitable for the purpose of numerical computation is also proposed. Some geometric and algebraic issues of the PPSVD, such as the variational and geometric interpretations, and uniqueness properties are discussed. A numerical algorithm for stably computing the PPSVD is given based on the implicit Kogbetliantz technique. A numerical example is outlined to demonstrate the accuracy of the proposed algorithm.The work was partially supported by NSF grant DCR-8412314.