Nonstrictly hyperbolic systems of conservation laws of the conjugate type

We consider an inverse boundary problem for a general second order self-adjoint elliptic differential operator on a compact differential manifold with boundary. The inverse problem is that of the reconstruction of the manifold and operator via all but finite number of eigenvalues and traces on the boundary of the corresponding eigenfunctions of the operator. We prove that the data determine the manifold and the operator to within the group of the generalized gauge transformations. The proof is based upon a procedure of the reconstruction of a canonical object in the orbit of the group. This object, the canonical Schrödinger operator, is uniquely determined via its incomplete boundary spectral data.     

Understanding rigid geometric transformations: Jeff's learning path for translation

This article describes the development of knowledge and understanding of translations of Jeff, a prospective elementary teacher, during a teaching experiment that also included other rigid transformations. His initial conceptions of translations and other rigid transformations were characterized as undefined motions of a single object. He conceived of transformations as movement and showed no indication about what defines a transformation. The results of the study indicate that the development of his thinking about translations and other rigid transformations followed an order of (1) transformations as undefined motions of a single object, (2) transformations as defined motions of a single object, and (3) transformations as defined motions of all points on the plane. The case of Jeff is part of a bigger study that included four prospective teachers and analyzed their development in understanding of rigid transformations. The other participants also showed a similar evolution.     

Convex source support in three dimensions

This work extends the algorithm for computing the convex source support in the framework of the Poisson equation to a bounded three-dimensional domain. The convex source support is, in essence, the smallest (nonempty) convex set that supports a source that produces the measured (nontrivial) data on the boundary of the object. In particular, it belongs to the convex hull of the support of any source that is compatible with the measurements. The original algorithm for reconstructing the convex source support is inherently two-dimensional as it utilizes M?bius transformations. However, replacing the M?bius transformations by inversions with respect to suitable spheres and introducing the corresponding Kelvin transforms, the basic ideas of the algorithm carry over to three spatial dimensions. The performance of the resulting numerical algorithm is analyzed both for the inverse source problem and for electrical impedance tomography with a single pair of boundary current and potential as the measurement data.     

Homotopy Algorithm for Optimal Control Problems with a Second-order State Constraint

This paper deals with optimal control problems with a regular second-order state constraint and a scalar control, satisfying the strengthened Legendre-Clebsch condition. We study the stability of structure of stationary points. It is shown that under a uniform strict complementarity assumption, boundary arcs are stable under sufficiently smooth perturbations of the data. On the contrary, nonreducible touch points are not stable under perturbations. We show that under some reasonable conditions, either a boundary arc or a second touch point may appear. Those results allow us to design an homotopy algorithm which automatically detects the structure of the trajectory and initializes the shooting parameters associated with boundary arcs and touch points.     

An algorithm to solve polyhedral convex set optimization problems

An algorithm which computes a solution of a set optimization problem is provided. The graph of the objective map is assumed to be given by finitely many linear inequalities. A solution is understood to be a set of points in the domain satisfying two conditions: the attainment of the infimum and minimality with respect to a set relation. In the first phase of the algorithm, a linear vector optimization problem, called the vectorial relaxation, is solved. The resulting pre-solution yields the attainment of the infimum but, in general, not minimality. In the second phase of the algorithm, minimality is established by solving certain linear programs in combination with vertex enumeration of some values of the objective map.     

An iterative penalty method for the least squares solution of boundary value problems

This article is concerned with iterative techniques for linear systems of equations arising from a least squares formulation of boundary value problems. In its classical form, the solution of the least squares method is obtained by solving the traditional normal equation. However, for nonsmooth boundary conditions or in the case of refinement at a selected set of interior points, the matrix associated with the normal equation tends to be ill-conditioned. In this case, the least squares method may be formulated as a Powell multiplier method and the equations solved iteratively. Therein we use and compare two different iterative algorithms. The first algorithm is the preconditioned conjugate gradient method applied to the normal equation, while the second is a new algorithm based on the Powell method and formulated on the stabilized dual problem. The two algorithms are first compared on a one-dimensional problem with poorly conditioned matrices. Results show that, for such problems, the new algorithm gives more accurate results. The new algorithm is then applied to a two-dimensional steady state diffusion problem and a boundary layer problem. A comparison between the least squares method of Bramble and Schatz and the new algorithm demonstrates the ability of the new method to give highly accurate results on the boundary, or at a set of given interior collocation points without the deterioration of the condition number of the matrix. Conditions for convergence of the proposed algorithm are discussed. © 1997 John Wiley & Sons, Inc.     

Numerical solution of the plate bending and free vibrations problems

The problem of the bending and free vibrations of a clamped and edge-supported plate is considered. The proposed algorithm is the algorithm described in /1/, made specific for the case of the biharmonic equation. It does not have saturation /2/, i.e., its accuracy will be the higher, the smoother the solution. The program is constructed in such a manner that if the plate boundary is sufficiently smooth and given parametrically, then several of the first eigenvalues can be calculated and the bending problem can be solved. An illustration is presented of the eigenfrequency computation for an edge-supported plate whose boundary (an epitrochoid) has a curvature of the order of 10³ at twelve points (the curvatures enter explicitly in the appropriate boundary condition). The first eigenfrequencies are calculated with 7–8 places after the decimal point. The solution is obtained because of the accurate method of discretization and the study of the structure of the appropriate finitedimensional problem. This would permit execution of computations with a large number of points (up to 1230). A comparison is given with the results of computations of other authors for a circle and an ellipse /3–5/.     

Convergence analysis of a non-negative matrix factorization algorithm based on Gibbs random field modeling

Non-negative matrix factorization (NMF) is a new approach to deal with the multivariate nonnegative data. Although the classic multiplicative update algorithm can solve the NMF problems, it fails to find sparse and localized object parts. Then a Gibbs random field (GRF) modeling based NMF algorithm, called the GRF-NMF algorithm, try to directly model the prior object structure of the components into the NMF problem. In this paper, the convergence of the GRF-NMF algorithm and its advantages are investigated. Based on a classic model, the equilibrium points are obtained. Some invariant sets are constructed to prepare for the analysis of the convergence of the GRF-NMF algorithm. Then using stability theory of the equilibrium point, the convergence of the algorithm is proved and the convergence conditions of the algorithm are obtained. We theoretically present the advantages of the GRF-NMF algorithm in the end.     

Heuristics for Two-Level Hierarchical Transportation Networks

Given a set of points, we wish to design a network consisting of a primary link and a set of secondary links connecting the points to the primary link. The objective of the problem is to find the location and length of the primary link in order to minimize the sum of its weighted length and the weighted lengths of all secondary links. We assume that the weight of the secondary link from any point varies depending on the location of that point. In this paper, we describe efficient algorithms and their computer implementation for two scenarios of this problem. In the first scenario, only direct secondary links are allowed from each point to the primary link. In the second scenario, the secondary link from a point is allowed to pass through other points before reaching the primary link.     

Axially symmetric volume constrained anisotropic mean curvature flow

We study the long time existence theory for a non local flow associated to a free boundary problem for a trapped non liquid drop. The drop has free boundary components on two horizontal plates and its free energy is anisotropic and axially symmetric. For axially symmetric initial surfaces with sufficiently large volume in comparison with their initial surface energy, we show that the flow exists for all time. Numerical simulations of the curvature flow are presented.     

The problem of the contact between a linear elastic body and elastic and rigid bodies (a variational approach)

The problem of the contact between a linear elastic body and a rigid body is formulated as a one-sided problem. The solution is determined from the variational inequality, equivalent to the problem of minimizing the energy functional in a set of allowable displacements. The regularity of the solution is established down to internal points of the contact boundary. A measure is constructed in the subsets of the contact boundary that enables the effect of a stamp on an elastic body to be characterized. The absolute continuity of this measure is proved at the internal point. The problem of the contact of two elastic bodies is examined in a similar formulation. The regularity of the solution is established and the nature of the effect of one body on the other is clarified.     

A local search approximation algorithm for k-means clustering

In k-means clustering we are given a set of n data points in d-dimensional space and an integer k, and the problem is to determine a set of k points in  , called centers, to minimize the mean squared distance from each data point to its nearest center. No exact polynomial-time algorithms are known for this problem. Although asymptotically efficient approximation algorithms exist, these algorithms are not practical due to the very high constant factors involved. There are many heuristics that are used in practice, but we know of no bounds on their performance.

We consider the question of whether there exists a simple and practical approximation algorithm for k-means clustering. We present a local improvement heuristic based on swapping centers in and out. We prove that this yields a (9+)-approximation algorithm. We present an example showing that any approach based on performing a fixed number of swaps achieves an approximation factor of at least (9−) in all sufficiently high dimensions. Thus, our approximation factor is almost tight for algorithms based on performing a fixed number of swaps. To establish the practical value of the heuristic, we present an empirical study that shows that, when combined with Lloyd's algorithm, this heuristic performs quite well in practice.     

Equilibrium failure processes of granular composites

The macroscopic failure of inhomogeneous media results from damage accumulation on different structural levels. During rigid loading, when given displacements of boundary points are ensured, irrespective of the body's resistance, structural-failure processes of composite materials take place in an equilibrium regime and result in the manifestation of such nonlinear-behavior effects as a descending branch on the strain diagram. the structural elements of a granular composite are homogeneous and firmly connected along the interface. Their geometry and mutual arrangement are given and do not change during deformation and failure of the medium, and the medium itself is macrohomogenous. The strength of isotropic structural elementsis estimated by comparing the second invariant of the stress tensor with its critical value. Nonfulfillment of the indicated strength criterion is associated with loss of ability to resist changes in form; at this point, the positive value of the first invariant corresponds to loss of such ability to resist and increase in volume. The deformation and structural failure of the medium are investigated as a single process that can be described under quasi-static loading by a boundary problem consisting of a closed system of Eqs. (1) and (2) and boundary conditions providing for a macrohomogeneous strain state. A principal feature of the boundary problem under consideration is the possibility of considering in constitutive relationships the states of the inhomogeneous medium, which correspond to partial or complete loss of bearing capacity of the structural elements. The random structural strength constants correspond to three-parameter Weibull distribution (6). The representative volume of a granular composite, which fills a domain in the form of a cube, is modeled by a set of istropic elastobrittle strain diagrams containing a descending branch are obtained as a result of the mathematical modeling of deformation processes and structural failure to realized a representative volume containing 384 structural elements with different strength and similar elastic constants.Presented at the Ninth International Conference on the Mechanics of Composite Materials, Riga, October, 1995.Perm'State Mechanical University, Russia. Translated From Mekhanika Kompozitnykh Materialov, Vol. 32, No. 6, pp. 808–817, November–December, 1996.     

Gaussian spectral rules for second order finite-difference schemes

Earlier the authors suggested an algorithm of grid optimization for a second order finite-difference approximation of a two-point problem. The algorithm yields exponential superconvergence of the Neumann-to-Dirichlet map (or the boundary impedance). Here we extend that approach to PDEs with piecewise-constant coefficients and rectangular homogeneous subdomains. Examples of the numerical solution of the 2-dimensional oscillatory Helmholtz equation exhibit exponential convergence at prescribed points, where the cost per grid node is close to that of the standard five-point finite-difference scheme. Our scheme demonstrates high accuracy with slightly more than two grid points per wavelength and reduces the grid size by more than three orders as compared with the standard scheme.     

Explore Stochastic Instabilities of Periodic Points by Transition Path Theory

We consider the noise-induced transitions from a linearly stable periodic orbit consisting of T periodic points in randomly perturbed discrete logistic map. Traditional large deviation theory and asymptotic analysis at small noise limit cannot distinguish the quantitative difference in noise-induced stochastic instabilities among the T periodic points. To attack this problem, we generalize the transition path theory to the discrete-time continuous-space stochastic process. In our first criterion to quantify the relative instability among T periodic points, we use the distribution of the last passage location related to the transitions from the whole periodic orbit to a prescribed disjoint set. This distribution is related to individual contributions to the transition rate from each periodic points. The second criterion is based on the competency of the transition paths associated with each periodic point. Both criteria utilize the reactive probability current in the transition path theory. Our numerical results for the logistic map reveal the transition mechanism of escaping from the stable periodic orbit and identify which periodic point is more prone to lose stability so as to make successful transitions under random perturbations.     

带惩罚的相同容量k-均值问题的局部搜索算法

经典$k$-均值问题是一类应用广泛的聚类问题,它是指给定$\mathbb{R}^d$中观测点集合$D$和整数$k$,目的是在空间中寻找$k$个点作为中心集合$S$,使得集合$D$中的每个观测点到$S$中离它最近的中心的距离平方求和最小。这是个NP-难问题。经典$k$-均值问题有很多推广,本文研究的带惩罚的相同容量$k$-均值问题就是其中之一。与经典$k$-均值问题相比,惩罚性质是指每个观测点都给定惩罚费用,当某个观测点到最近中心的距离大于惩罚费用时,其对目标函数的贡献就用该观测点的惩罚费用来代替最近的距离的平方,相同容量约束要求每个中心至多连接$U$个观测点。针对这种问题,我们设计了局部搜索算法,该算法在至多选取$（3+\alpha）k$个中心的情况下,可以达到$\beta$-近似,其中,参数$\alpha>34$,$\beta>\frac{\alpha+34}{\alpha-34}$。     

带惩罚的相同容量k-均值问题的局部搜索算法

经典$k$-均值问题是一类应用广泛的聚类问题,它是指给定$\mathbb{R}^d$中观测点集合$D$和整数$k$,目的是在空间中寻找$k$个点作为中心集合$S$,使得集合$D$中的每个观测点到$S$中离它最近的中心的距离平方求和最小。这是个NP-难问题。经典$k$-均值问题有很多推广,本文研究的带惩罚的相同容量$k$-均值问题就是其中之一。与经典$k$-均值问题相比,惩罚性质是指每个观测点都给定惩罚费用,当某个观测点到最近中心的距离大于惩罚费用时,其对目标函数的贡献就用该观测点的惩罚费用来代替最近的距离的平方,相同容量约束要求每个中心至多连接$U$个观测点。针对这种问题,我们设计了局部搜索算法,该算法在至多选取$（3+\alpha）k$个中心的情况下,可以达到$\beta$-近似,其中,参数$\alpha>34$,$\beta>\frac{\alpha+34}{\alpha-34}$。     

Properness Defects of Projections and Computation of at Least One Point in Each Connected Component of a Real Algebraic Set

Computing at least one point in each connected component of a real algebraic set is a basic subroutine to decide emptiness of semi-algebraic sets, which is a fundamental algorithmic problem in effective real algebraic geometry. In this article we propose a new algorithm for the former task, which avoids a hypothesis of properness required in many of the previous methods. We show how studying the set of non-properness of a linear projection enables us to detect the connected components of a real algebraic set without critical points for . Our algorithm is based on this observation and its practical counterpoint, using the triangular representation of algebraic varieties. Our experiments show its efficiency on a family of examples.     

The conjunction problem for thin elastic and rigid inclusions in an elastic body

Under consideration is the conjunction problem for a thin elastic and a thin rigid inclusions that are in contact at one point and placed in an elastic body. Depending on what kind of conjunction conditions are set at the contact point of inclusions, we consider the two cases: the case of no fracture, where, as the conjunction conditions, we take the matching of displacements at the contact point and preservation of the angle between the inclusions, and the case with a fracture in which only the matching of displacements is assumed. At the point of conjunction, we obtain the boundary conditions for the differential formulation of the problem. On the positive face of the rigid inclusion, there is delamination. On the crack faces, some nonlinear boundary conditions of the type of inequalities are set, that prevent mutual penetration of the faces. The existence and uniqueness theorems for the solution of the equilibrium problem are proved in both cases.     

Continuous Parametrization of Attainable Sets by Solutions of Differential Inclusions

It is shown that if the Hamiltonian corresponding to a differential inclusion is sufficiently regular and solutions reaching the points in the boundary of the set which are attainable at some fixed time, are unique then the parametrization mentioned in the title exists – it is continuous with respect to the points attained at that time. No such parametrization may exist if at least one point of the boundary is reached by more than one solution.