Computing hyperbolic choreographies

An algorithm is presented for numerical computation of choreographies in spaces of constant negative curvature in a hyperbolic cotangent potential, extending the ideas given in a companion paper [14] for computing choreographies in the plane in a Newtonian potential and on a sphere in a cotangent potential. Following an idea of Diacu, Pérez-Chavela and Reyes Victoria [9], we apply stereographic projection and study the problem in the Poincaré disk. Using approximation by trigonometric polynomials and optimization methods with exact gradient and exact Hessian matrix, we find new choreographies, hyperbolic analogues of the ones presented in [14]. The algorithm proceeds in two phases: first BFGS quasi-Newton iteration to get close to a solution, then Newton iteration for high accuracy.     

Optimization on flag manifolds

A flag is a sequence of nested subspaces. Flags are ubiquitous in numerical analysis, arising in finite elements, multigrid, spectral, and pseudospectral methods for numerical pde; they arise in the form of Krylov subspaces in matrix computations, and as multiresolution analysis in wavelets constructions. They are common in statistics too—principal component, canonical correlation, and correspondence analyses may all be viewed as methods for extracting flags from a data set. The main goal of this article is to develop the tools needed for optimizing over a set of flags, which is a smooth manifold called the flag manifold, and it contains the Grassmannian as the simplest special case. We will derive closed-form analytic expressions for various differential geometric objects required for Riemannian optimization algorithms on the flag manifold; introducing various systems of extrinsic coordinates that allow us to parameterize points, metrics, tangent spaces, geodesics, distances, parallel transports, gradients, Hessians in terms of matrices and matrix operations; and thereby permitting us to formulate steepest descent, conjugate gradient, and Newton algorithms on the flag manifold using only standard numerical linear algebra.

     

A Hybrid Smoothing-Nonsmooth Newton-Type Algorithm Yielding an Exact Solution of the $P_0$-LCP

We propose a hybrid smoothing-nonsmooth Newton-type algorithm for solving the P0 linear complementarity problem (P0-LCP) based on the techniques used in the non-smooth Newton method and smoothing Newton method. Under some assumptions, the proposed algorithm can find an exact solution of P0-LCP in finite steps. Preliminary numerical results indicate that the proposed algorithm is promising.     

An alogrithm for monotonic global optimization problems ∗

We propose an algorithm to locate a global maximum of an increasing function subject to an increasing constraint on the cone of vectors with nonnegative coordinates. The algorithm is based on the outer approximation of the feasible set. We eastablish the con vergence of the algorithm and provide a number of numerical experiments. We also discuss the types of constraints and objective functions for which the algorithm is best suited     

Solving Quadratically Constrained Least Squares Problems Using a Differential-Geometric Approach

A quadratically constrained linear least squares problem is usually solved using a Lagrange multiplier for the constraint and then solving iteratively a nonlinear secular equation for the optimal Lagrange multiplier. It is well-known that, due to the closeness to a pole for the secular equation, standard methods for solving the secular equation can be slow, and sometimes it is not easy to select a good starting value for the iteration. The problem can be reformulated as that of minimizing the residual of the least squares problem on the unit sphere. Using a differential-geometric approach we formulate Newton's method on the sphere, and thereby avoid the difficulties associated with the Lagrange multiplier formulation. This Newton method on the sphere can be implemented efficiently, and since it is easy to find a good starting value for the iteration, and the convergence is often quite fast, it has a clear advantage over the Lagrange multiplier method. A numerical example is given.     

Reference free structure determination through eigenvectors of center of mass operators

Recovering the three-dimensional structure of molecules is important for understanding their functionality. We describe a spectral graph algorithm for reconstructing the three-dimensional structure of molecules from their cryo-electron microscopy images taken at random unknown orientations.We first identify a one-to-one correspondence between radial lines in three-dimensional Fourier space of the molecule and points on the unit sphere. The problem is then reduced to determining the coordinates of points on the sphere given a subset of their pairwise geodesic distances. To recover those coordinates, we exploit the special geometry of the problem, as rendered by the Fourier projection–slice theorem, to construct a weighted graph whose vertices are the radial Fourier lines and whose edges are linked using the common line property. The graph organizes the radial lines on the sphere in a global manner that reveals the acquisition direction of each image. This organization is derived from a global computation of a few eigenvectors of the graph's sparse adjacency matrix. Once the directions are obtained, the molecule can be reconstructed using classical tomography methods.The presented algorithm is direct (as opposed to iterative refinement schemes), does not require any prior model for the reconstructed object, and is shown to have favorable computational and numerical properties. Moreover, the algorithm does not impose any assumption on the distribution of the projection orientations. Physically, this means that the algorithm is applicable to molecules that have unknown spatial preference.     

Computer system for kinematic and dynamic analysis synthesis of rigid and flexible multibody systems

In the paper an overview of a general numerical algorithm and program system library for deriving the kinematic constraint equations and dynamic equations of motion, as well as, computation of their first and second order partial derivatives with respect to kinematic parameters of motion, design parameters and mass and inertia characteristics for rigid and flexible multibody systems is presented. These are the main basic computational modules for implementation of kinematic and dynamic synthesis, optimization and design. The main theoretical basis consists in matrix methods for deriving the kinematic constraints and dynamic equations, as well as, the generalized Newton – Euler dynamic equations for rigid and flexible bodies, and finite element discretization in relative coordinates. Block–scheme of the computational procedures and problem oriented program compilation is presented. An example of kinematic synthesis of six–link path generating mechanism with singular points is presented. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

A fast and accurate algorithm for computing radial transonic flows

An efficient algorithm is described for calculating stationary one-dimensional transonic outflow solutions of the compressible Euler equations with gravity and heat source terms. The stationary equations are solved directly by exploiting their dynamical system form. Transonic expansions are the stable manifolds of saddle-point-type critical points, and can be obtained efficiently and accurately by adaptive integration outward from the critical points. The particular transonic solution and critical point that match the inflow boundary conditions are obtained by a two-by-two Newton iteration which allows the critical point to vary within the manifold of possible critical points. The proposed Newton Critical Point (NCP) method typically converges in a small number of Newton steps, and the adaptively calculated solution trajectories are highly accurate. A sample application area for this method is the calculation of transonic hydrodynamic escape flows from extrasolar planets and the early Earth. The method is also illustrated for an example flow problem that models accretion onto a black hole with a shock.     

Distributing points uniformly on the unit sphere under a mirror reflection symmetry constraint

Uniformly distributed point sets on the unit sphere with and without symmetry constraints have been found useful in many scientific and engineering applications. Here, a novel variant of the Thomson problem is proposed and formulated as an unconstrained optimization problem. While the goal of the Thomson problem is to find the minimum energy configuration of N electrons constrained on the surface of the unit sphere, this novel variant imposes a new symmetry constraint – mirror reflection symmetry with the x–y plane as the plane of symmetry. Qualitative features of the two-dimensional projection of the optimal configurations are briefly mentioned and compared to the ground-state configurations of the two dimensional system of charged particles laterally confined by a parabolic potential well.     

On the Finite Convergence of Newton-type Methods for P0 Atone Variational Inequalities

Based on the techniques used in non-smooth Newton methods and regularized smoothing Newton methods, a Newton-type algorithm is proposed for solving the P0 affine variational inequality problem. Under mild conditions, the algorithm can find an exact solution of the P0 affine variational inequality problem in finite steps. Preliminary numerical results indicate that the algorithm is promising.     

Einstein structures: Existence versus uniqueness

Two well-known questions in differential geometry are “Does every compact manifold of dimension greater than four admit an Einstein metric?” and “Does an Einstein metric of a negative scalar curvature exist on a sphere?” We demonstrate that these questions are related: For everyn≥5 the existence of metrics for which the deviation from being Einstein is arbitrarily small on every compact manifold of dimensionn (or even on every smooth homology sphere of dimensionn) implies the existence of metrics of negative Ricci curvature on the sphereS ⁿ for which the deviation from being Einstein is arbitrarily small. Furthermore, assuming either a version of the Palais-Smale condition or the plausible looking existence of an algorithm deciding when a given metric on a compact manifold is close to an Einstein metric, we show for anyn≥5 that: 1) If everyn-dimensional smooth homology sphere admits an Einstein metric thenS ⁿ admits infinitely many Einstein structures of volume one and of negative scalar curvature; 2) If every compactn-dimensional manifold admits an Einstein metric then every compactn-dimensional manifold admits infinitely many distinct Einstein structures of volume one and of negative scalar curvature.     

On the Construction of Geometric Integrators in the RKMK Class

We consider the construction of geometric integrators in the class of RKMK methods. Any differential equation in the form of an infinitesimal generator on a homogeneous space is shown to be locally equivalent to a differential equation on the Lie algebra corresponding to the Lie group acting on the homogeneous space. This way we obtain a distinction between the coordinate-free phrasing of the differential equation and the local coordinates used. In this paper we study methods based on arbitrary local coordinates on the Lie group manifold. By choosing the coordinates to be canonical coordinates of the first kind we obtain the original method of Munthe-Kaas [16]. Methods similar to the RKMK method are developed based on the different coordinatizations of the Lie group manifold, given by the Cayley transform, diagonal Padé approximants of the exponential map, canonical coordinates of the second kind, etc. Some numerical experiments are also given.     

Grassmann algorithms for low rank approximation of matrices with missing values

The problem of approximating a matrix by another matrix of lower rank, when a modest portion of its elements are missing, is considered. The solution is obtained using Newton’s algorithm to find a zero of a vector field on a product manifold. As a preliminary the algorithm is formulated for the well-known case with no missing elements where also a rederivation of the correction equation in a block Jacobi-Davidson method is included. Numerical examples show that the Newton algorithm grows more efficient than an alternating least squares procedure as the amount of missing values increases.     

Path and quasi-homotopy for Sobolev maps between manifolds

We study the relationship between quasi-homotopy and path homotopy for Sobolev maps between manifolds. By employing singular integrals on manifolds we show that, in the critical exponent case, path homotopic maps are quasi-homotopic – and observe the rather surprising fact that quasi-homotopic maps need not be path homotopic. We also study the case where the target is an aspherical manifold, e.g. a manifold with non-positive sectional curvature, and the contrasting case of the target being a sphere.     

The virtual mass of a sphere in a suspension of spherical particles

The problem of the virtual mass of a sphere, moving in an ideal incompressible fluid when there are other identical spherical particles of arbitrary mass present is considered. A solution is constructed for the velocity potential of the fluid in the form of the superposition of perturbation fields, introduced into the flow by each of the particles. The perturbation fields are obtained in the form of functional series, the coefficients of which are mutually consistent by a defined system of equations. An explicit expression is obtained for the hydrodynamic force acting on the sphere in the form of a function of the coordinates of all the particles. A simple analytical dependence of the mean value of the force and the virtual mass of the sphere on the particle-to-fluid density ratio in a first approximation of the volume fraction of the dispersed phase is obtained for a statistically uniform distribution of the dispersed particles in the suspension, using the procedure of averaging over their different possible configurations in space.     

Stability of the configurations of point vortices on a sphere

We study the motion of point vortices on a sphere and, using the methods of linear algebra, find the symmetric configurations of relative equilibrium. Furthermore, we give a catalog of symmetric configurations based on regular polyhedrons. Finally, we investigate the stability of the equilibrium configurations found.     

Relaxation,New Combinatorial and Polynomial Algorithms for the Linear Feasibility Problem

We consider the homogenized linear feasibility problem, to find an x on the unit sphere satisfying n linear inequalities a_i ^Tx \ge 0. To solve this problem we consider the centers of the inspheres of spherical simplices, whose facets are determined by a subset of the constraints. As a result we find a new combinatorial algorithm for the linear feasibility problem. If we allow rescaling, this algorithm becomes polynomial. We point out that the algorithm also solves the more general convex feasibility problem. Moreover, numerical experiments show that the algorithm could be of practical interest.     

Analysis of a Class of Symmetric Equilibrium Configurations for a Territorial Model

<正>Motivated by an animal territoriality model,we consider a centroidal Voronoi tessellation algorithm from a dynamical systems perspective.In doing so,we discuss the stability of an aligned equilibrium configuration for a rectangular domain that exhibits interesting symmetry properties.We also demonstrate the procedure for performing a center manifold reduction on the system to extract a set of coordinates which capture the long term dynamics when the system is close to a bifurcation.Bifurcations of the system restricted to the center manifold are then classified and compared to numerical results.Although we analyze a specific set-up,these methods can in principle be applied to any bifurcation point of any equilibrium for any domain.     

Manifold-theoretic compactifications of configuration spaces

We present new definitions for and give a comprehensive treatment of the canonical compactification of configuration spaces due to Fulton–MacPherson and Axelrod–Singer in the setting of smooth manifolds, as well as a simplicial variant of this compactification initiated by Kontsevich. Our constructions are elementary and give simple global coordinates for the compactified configuration space of a general manifold embedded in Euclidean space. We stratify the canonical compactification, identifying the difieomorphism types of the strata in terms of spaces of configurations in the tangent bundle, and give completely explicit local coordinates around the strata as needed to define a manifold with corners. We analyze the quotient map from the canonical to the simplicial compactification, showing it is a homotopy equivalence. Using global coordinates we define projection maps and diagonal maps, which for the simplicial variant satisfy cosimplicial identities.     

Primal-Dual Newton-Type Interior-Point Method for Topology Optimization

We consider the problem of minimization of energy dissipation in a conductive electromagnetic medium with a fixed geometry and a priori given lower and upper bounds for the conductivity. The nonlinear optimization problem is analyzed by using the primal-dual Newton interior-point method. The elliptic differential equation for the electric potential is considered as an equality constraint. Transforming iterations for the null space decomposition of the condensed primal-dual system are applied to find the search direction. The numerical experiments treat two-dimensional isotropic systems.