New protocols for solving geometric calculation problems incorporating dynamic geometry and computer algebra software

The ready availability today of both software for geometric construction, measurement and calculation, and software for numerical calculation and symbolic analysis, when taken together allow new approaches to the solution of geometric problems. These computer-aided graphical, numerical and algebraic methods of solution are illustrated and discussed by means of examples, using an appropriate choice of software tools, and provide an indication of the possible future when fully integrated software is available.     

Parallel geometric algorithms for multi-core computers

Computers with multiple processor cores using shared memory are now ubiquitous. In this paper, we present several parallel geometric algorithms that specifically target this environment, with the goal of exploiting the additional computing power. The algorithms we describe are (a) 2-/3-dimensional spatial sorting of points, as is typically used for preprocessing before using incremental algorithms, (b) d-dimensional axis-aligned box intersection computation, and finally (c) 3D bulk insertion of points into Delaunay triangulations, which can be used for mesh generation algorithms, or simply for constructing 3D Delaunay triangulations. For the latter, we introduce as a foundational element the design of a container data structure that both provides concurrent addition and removal operations and is compact in memory. This makes it especially well-suited for storing large dynamic graphs such as Delaunay triangulations.We show experimental results for these algorithms, using our implementations based on the Computational Geometry Algorithms Library (CGAL). This work is a step towards what we hope will become a parallel mode for CGAL, where algorithms automatically use the available parallel resources without requiring significant user intervention.     

Test problems used for evaluation of computers

For comparison of performance and prices of certain computers, artificial test problems were designed by a Swedish governmental committee and (theoretically) solved by the manufacturers. Tested were Bull Gamma 30—RCA 301, IBM 1401, ICT 1301, and Saab D21. Winner was the Swedish Saab D21, loser IBM 1401, with wide margins, but the committee selected IBM 1401, mainly—it is assumed—because IBM 1401 was considered more thoroughly tested; the project (for 20 computers) was considered extremely important, and the committee apparently did not want to accept any risks for delay.—The decision of the committee has been criticized.     

On the solution of steady-state elastodynamic crack problems by using complex variable methods

Summary Solutions in a closed-form, or in a series-expansion form, are given, concerning steady-state elastodynamic crack problems. The configuration of the problems treated consists, either of an infinite body under plane extension, or a strip-like body under anti-plane shear. The loading mode consisted of constant stresses, acting on the crack faces and moving with the velocity of the crack tip. In the domain of elliptic wave-equations, viz. for subsonic crack velocities, the solution of the problems was reduced to a solution of a Dirichlet problem, whereas in the case of hyperbolic wave-equations, viz. for transonic crack velocities, a Riemann-Hilbert problem was formulated and solved.

---

Résumé On donne des solutions sous forme explicite ou sous forme de séries infinies pour des problèmes de fissures stables elastodynamiques. La configuration des problèmes traités consiste soit en un corps infini soumis à une extension plane, soit en un corps en forme de bande soumis à un cisaillement anti-plan. Les plaques étaient soumises à un état plan de contraintes constantes, agissant sur les faces de la fissure et suivant l'extrémité de la fissure avec la même vitesse. On a montré que dans le cas où le problème peut être exprimé par des équations d'ondes elliptiques, c.à.d. pour des vitesses de propagation de la fissure d'ordre subsonique, la solution a été réduite à une solution d'un problème de Dirichlet, tandis que dans le cas des équations d'ondes hyperboliques, c.à.d. pour des vitesses transoniques, le problème a été formulé et résolu comme un problème de Riemann-Hilbert.

     

Partitioning heuristics for two geometric maximization problems

Given n points randomly selected from a uniform distribution on the unit square, we describe linear-time partitioning heuristics which will construct a matching or a tour of these points. We show that the heuristics closely approximate the optimum values as n → ∞. Hence we show that the asymptotic values of the maximum matching and tour are about 0·3826n and twice this value respectively.     

On using cubic spline for the solution of problems in calculus of variations

Two different approaches based on cubic B-spline are developed to approximate the solution of problems in calculus of variations. Both direct and indirect methods will be described. It is known that, when using cubic spline for interpolating a function g∈C⁴[a,b] on a uniform partition with the step size h, the optimal order of convergence derived is O(h⁴). In Zarebnia and Birjandi (J. Appl. Math. 1–10, 2012) a non-optimal O(h²) method based on cubic B-spline has been used to solve the problems in calculus of variations. In this paper at first we will obtain an optimal O(h⁴) indirect method using cubic B-spline to approximate the solution. The convergence analysis will be discussed in details. Also a locally superconvergent O(h⁶) indirect approximation will be describe. Finally the direct method based on cubic spline will be developed. Some test problems are given to demonstrate the efficiency and applicability of the numerical methods.     

On the solution of large-scale SDP problems by the modified barrier method using iterative solvers

The limiting factors of second-order methods for large-scale semidefinite optimization are the storage and factorization of the Newton matrix. For a particular algorithm based on the modified barrier method, we propose to use iterative solvers instead of the routinely used direct factorization techniques. The preconditioned conjugate gradient method proves to be a viable alternative for problems with a large number of variables and modest size of the constrained matrix. We further propose to avoid explicit calculation of the Newton matrix either by an implicit scheme in the matrix–vector product or using a finite-difference formula. This leads to huge savings in memory requirements and, for certain problems, to further speed-up of the algorithm. Dedicated to the memory of Jos Sturm.     

Parallel solution of elasticity problems using overlapping aggregations

The finite element (FE) solution of geotechnical elasticity problems leads to the solution of a large system of linear equations. For solving the system, we use the preconditioned conjugate gradient (PCG) method with two-level additive Schwarz preconditioner. The preconditioning is realised in parallel. A coarse space is usually constructed using an aggregation technique. If the finite element spaces for coarse and fine problems on structural grids are fully compatible, relations between elements of matrices of the coarse and fine problems can be derived. By generalization of these formulae, we obtain an overlapping aggregation technique for the construction of a coarse space with smoothed basis functions. The numerical tests are presented at the end of the paper.     

A numerical method using the Prfer transformation for the calculation of eigenpairs of two-parameter Sturm-Liouville problems

A shooting method for coupled Prfer equations is discussedfor numerical solution of two-parameter Sturm-Liouville problems. Research supported in part by grants from the NSERC of Canada.     

Adaptive sampling for geometric problems over data streams

Geometric coordinates are an integral part of many data streams. Examples include sensor locations in environmental monitoring, vehicle locations in traffic monitoring or battlefield simulations, scientific measurements of earth or atmospheric phenomena, etc. This paper focuses on the problem of summarizing such geometric data streams using limited storage so that many natural geometric queries can be answered faithfully. Some examples of such queries are: report the smallest convex region in which a chemical leak has been sensed, or track the diameter of the dataset, or track the extent of the dataset in any given direction. One can also pose queries over multiple streams: for instance, track the minimum distance between the convex hulls of two data streams, report when datasets A and B are no longer linearly separable, or report when points of data stream A become completely surrounded by points of data stream B, etc. These queries are easily extended to more than two streams.

In this paper, we propose an adaptive sampling scheme that gives provably optimal error bounds for extremal problems of this nature. All our results follow from a single technique for computing the approximate convex hull of a point stream in a single pass. Our main result is this: given a stream of two-dimensional points and an integer r, we can maintain an adaptive sample of at most 2r+1 points such that the distance between the true convex hull and the convex hull of the sample points is O(D/r²), where D is the diameter of the sample set. The amortized time for processing each point in the stream is O(logr). Using the sample convex hull, all the queries mentioned above can be answered approximately in either O(logr) or O(r) time.     

A solution for the local plane strain problems using elliptic integrals of Cauchy type

We consider a parallel fiber‐reinforced periodic elastic composite that present an imperfect contact of spring type between the fiber and the matrix. We use the elliptic integral of Cauchy type for solving the plane strain local problems that arise from the asymptotic homogenization method. Several general conditions are assumed, which include that the fibers are disposed of arbitrary manner in the local cell, that all fibers present contact perfect with different constants of imperfection, and that their cross section is a smooth closed arbitrary curve. We find that there are infinity solutions for these problems, and we find relations between these solutions and effective coefficients of the composite. Finally, we obtain analytic formulae for the circular fiber case and show some numerical examples. Copyright © 2016 John Wiley & Sons, Ltd.     

Numerical solution of boundary value problems by using an optimized two-step block method

Numerical Algorithms - This paper aims at the application of an optimized two-step hybrid block method for solving boundary value problems with different types of boundary conditions. The proposed...     

An approach to the solution of recognition problems using neural networks

Conditions are determined under which, for pattern recognition problems with standard information (Ω-regular problems), a correct algorithm and a six-level spatial neural network reproducing the calculations performed by the correct algorithm can be constructed. The proposed approach to constructing the neural network is not related to the traditional approach based on minimizing a functional.     

On the solution of problems of elasticity theory using the perturbation method

We discuss methods of choosing the perturbation based on physical or geometric properties of the bodies being studied. We propose new types of perturbations that significantly simplify the solution of problems of the theory of elasticity. Bibliography: 3 titles. Translated fromTeoreticheskaya i Prikladnaya Mekhanika, No. 26, 1996, pp. 147–151     

New interpolation formulas of using geometric assumptions in the algebraic multigrid method

In this paper, new interpolation formulas for using geometric assumptions in the algebraic multigrid (AMG) method are reported. The theoretical and convergence analysis will be presented. The effectiveness and robustness of these interpolation formulas are demonstrated by numerical experiments. Not only is a rapid rate of convergence achieved, but the AMG algorithm used in conjunction with these formulas can also be used to solve various ill-conditioned systems of equations. The principal contribution of the present method is to extend the range of applications of the AMG method developed by Ruge and Stüben.     

Computational aspects of cutting-plane algorithms for geometric programming problems

This paper presents the results of computational studies of the properties of cutting plane algorithms as applied to posynomial geometric programs. The four cutting planes studied represent the gradient method of Kelley and an extension to develop tangential cuts; the geometric inequality of Duffin and an extension to generate several cuts at each iteration. As a result of over 200 problem solutions, we will draw conclusions regarding the effectiveness of acceleration procedures, feasible and infeasible starting point, and the effect of the initial bounds on the variables. As a result of these experiments, certain cutting plane methods are seen to be attractive means of solving large scale geometric programs.This author's research was supported in part by the Center for the Study of Environmental Policy, The Pennsylvania State University.