Numerical comparisons of nonlinear programming algorithms on serial and vector processors using automatic differentiation

It is shown by numerical computation that real-world optimal electrical power flow problems can be solved in real-time using vector processors. These problems are nonlinear optimization problems characterized by highly nonlinear constraints and a large number of variables, and cannot be solved in real-time even on mainframe computers. The speedup achieved in our vectorized computations is two orders of magnitude for some problems.This work was partly supported by the Italian Ministry of Education—special project (40%) M.A.O. 1987.     

Two commodity network flows and linear programming

This paper shows that the linear programming formulation of the two-commodity network flow problem leads to a direct derivation of the known results concerning this problem. An algorithm for solving the problem is given which essentially consists of two applications of the Ford—Fulkerson max flow computation. Moreover, the algorithm provides constructive proofs for the results. Some new facts concerning feasible integer flows are also given.     

Data parallel computing for network-structured optimization problems

Data level parallelism is a type of parallelism whereby operations are performed on many data elements concurrently, by many processors. These operations are (more or less) identical, and are executed in a synchronous, orderly fashion. This type of parallelism is used by massively parallel SIMD (i.e., Single Instruction, Multiple Data) architectures, like the Connection Machine CM-2, the AMT DAP and Masspar, and MIMD (i.e., Multiple Instruction, Multiple Data) architectures, like the Connection Machine CM-5. Data parallelism can also be described by a theoretical model of computation: the Vector-Random Access Machine (V-RAM).In this paper we discuss practical approaches to the data-parallel solution of large scale optimization problems with network—or embedded-network—structures. The following issues are addressed: (1) The concept of dataparallelism, (2) algorithmic principles that lead to data-parallel decomposition of optimization problems with network—or embedded-network—structures, (3) specific algorithms for several network problems, (4) data-structures needed for efficient implementations of the algorithms, and (5) empirical results that highlight the performance of the algorithms on a data-parallel computer, the Connection Machine CM-2.     

Discrete linearized least-squares rational approximation on the unit circle

We already generalized the Rutishauser—Gragg—Harrod—Reichel algorithm for discrete least-squares polynomial approximation on the real axis to the rational case. In this paper, a new method for discrete least-squares linearized rational approximation on the unit circle is presented. It generalizes the algorithms of Reichel—Ammar—Gragg for discrete least-squares polynomial approximation on the unit circle to the rationale case. The algorithm is fast in the sense that it requires order m computation time where m is the number of data points and is the degree of the approximant. We describe how this algorithm can be implemented in parallel. Examples illustrate the numerical behavior of the algorithm.     

Determination of acoustic parameters in flow fields using OpenFOAM

In the present paper a Computational Aero Acoustics approach based on Lighthill's and Curle's Acoustic Analogies was implemented in OpenFOAM 2.1.1. The novel developed OpenFOAM application solvers acousticFoam and acousticRhoFoam can be used for transient incompressible and compressible simulations respectively. The CAA approach takes High Performance Computing environment into account and realize the computation of flow and acoustic fields within the acoustical near field on one mesh only. (© 2014 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

A systematization of the saddle point method. Application to the Airy and Hankel functions

The standard saddle point method of asymptotic expansions of integrals requires to show the existence of the steepest descent paths of the phase function and the computation of the coefficients of the expansion from a function implicitly defined by solving an inversion problem. This means that the method is not systematic because the steepest descent paths depend on the phase function on hand and there is not a general and explicit formula for the coefficients of the expansion (like in Watson's Lemma for example). We propose a more systematic variant of the method in which the computation of the steepest descent paths is trivial and almost universal: it only depends on the location and the order of the saddle points of the phase function. Moreover, this variant of the method generates an asymptotic expansion given in terms of a generalized (and universal) asymptotic sequence that avoids the computation of the standard coefficients, giving an explicit and systematic formula for the expansion that may be easily implemented on a symbolic manipulation program. As an illustrative example, the well-known asymptotic expansion of the Airy function is rederived almost trivially using this method. New asymptotic expansions of the Hankel function Hn(z) for large n and z are given as non-trivial examples.     

Some orthogonal polynomials on the finite interval and Gaussian quadrature rules for fractional Riemann‐Liouville integrals

Inspired with papers by Bokhari, Qadir, and Al‐Attas (2010) and by Rapai?, ?ekara, and Govedarica (2014), in this paper we investigate a few types of orthogonal polynomials on finite intervals and derive the corresponding quadrature formulas of Gaussian type for efficient numerical computation of the left and right fractional Riemann‐Liouville integrals. Several numerical examples are included to demonstrate the numerical efficiency of the proposed procedure.     

LOOK: A Lazy Object-Oriented Kernel design for geometric computation

In this paper we describe and discuss a new kernel design for geometric computation in the plane. It combines different kinds of floating-point filter techniques and a lazy evaluation scheme with the exact number types provided by LEDA allowing for efficient and exact computation with rational and algebraic geometric objects.

It is the first kernel design which uses floating-point filter techniques on the level of geometric constructions.

The experiments we present—partly using the CGAL framework—show a great improvement in speed and—maybe even more important for practical applications—memory consumption when dealing with more complex geometric computations.     

Dependence of the aeroelastic stability of a slender U-beam on the realized flow pattern

We investigate the aeroelastic behaviour of a slender U-beam in cross-flow. Two distinct, time periodic flow patterns are observed in simulations of the flow around this beam. Its aeroelastic properties depend on the realized flow pattern, especially so for low reduced velocities: One flow pattern leads to pronounced torsional vortex-induced vibrations. No such vibrations could be observed under the other flow pattern. (© 2014 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Strategies for the Computation of Configurational Forces in Dissipative Media

Configurational forces can be interpreted as driving forces on material inhomogeneities such as crack tips. In dissipative media the total configurational force on an inhomogeneity consists of an elastic contribution and a contribution due to the dissipative processes in the material. For the computation of discrete configurational forces acting at the nodes of a finite element mesh, the elastic and dissipative contributions must be evaluated at integration point level. While the evaluation of the elastic contribution is straightforward, the evaluation of the dissipative part is faced with certain difficulties. This is because gradients of internal variables are necessary in order to compute the dissipative part of the configurational force. For the sake of efficiency, these internal variables are usually treated as local history data at integration point level in finite element (FE) implementations. Thus, the history data needs to be projected to the nodes of the FE mesh in order to compute the gradients by means of shape function interpolations of nodal data as it is standard practice. However, this is a rather cumbersome method which does not easily integrate into standard finite element frameworks. An alternative approach which facilitates the computation of gradients of local history data is investigated in this work. This approach is based on the definition of subelements within the elements of the FE mesh and allows for a straightforward integration of the configurational force computation into standard finite element software. The suitability and the numerical accuracy of different projection approaches and the subelement technique are discussed and analyzed exemplarily within the context of a crystal plasticity model. (© 2014 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Vortex generated fluid flows in multiply connected domains

A fluid flow in a multiply connected domain generated by an arbitrary number of point vortices is considered. A stream function for this flow is constructed as a limit of a certain functional sequence using the method of images. The convergence of this sequence is discussed, and the speed of convergence is determined explicitly. The presented formulas allow for an easy computation of the values of the stream function with arbitrary precision in the case of well-separated cylinders. The considered problem is important for applications such as eddy flows in oceans. Moreover, since finding the stream function of the flow is essentially identical to finding the modified Green’s function for Laplace’s equation, the presented method can be applied to a more general class of applied problems which involve solving the Dirichlet problem for Laplace’s equation.     

A numerical approach to optimization problems with variational inequality constraints

Optimization problems with variational inequality constraints are converted to constrained minimization of a local Lipschitz function. To this minimization a non-differentiable optimization method is used; the required subgradients of the objective are computed by means of a special adjoint equation. Besides tests with some academic examples, the approach is applied to the computation of the Stackelberg—Cournot—Nash equilibria and to the numerical solution of a class of quasi-variational inequalities.Corresponding author.     

Entropy methods for identifying hedonic models

This paper contributes to the literature on hedonic models in two ways. First, it makes use of Queyranne’s reformulation of a hedonic model in the discrete case as a network flow problem in order to provide a proof of existence and integrality of a hedonic equilibrium and efficient computation of hedonic prices. Second, elaborating on entropic methods developed in Galichon and Salanié (Cupid’s invisible hand: social surplus and identification in matching models. Working Paper, 2014), this paper proposes a new identification strategy for hedonic models in a single market. This methodology allows one to introduce heterogeneities in both consumers’ and producers’ attributes and to recover producers’ profits and consumers’ utilities based on the observation of production and consumption patterns and the set of hedonic prices.     

Maximizing the minimum source-sink path subject to a budget constraint

Given a linear cost function for lengthening arcs, a technique is shown for maximizing, within a budget, the shortest source—sink path length in a graph. The computation is equivalent to the parametric solution of a minimum cost flow problem.This work was done while G.C. Harding was at Cornell University.The work of D.R. Fulkerson was supported by the National Science Foundation under Grant MPS74-24026 and by the Office of Naval Research under Grant NR 044-439.     

An efficient approach to solve very large dense linear systems with verified computing on clusters

Automatic result verification is an important tool to guarantee that completely inaccurate results cannot be used for decisions without getting remarked during a numerical computation. Mathematical rigor provided by verified computing allows the computation of an enclosure containing the exact solution of a given problem. Particularly, the computation of linear systems can strongly benefit from this technique in terms of reliability of results. However, in order to compute an enclosure of the exact result of a linear system, more floating‐point operations are necessary, consequently increasing the execution time. In this context, parallelism appears as a good alternative to improve the solver performance. In this paper, we present an approach to solve very large dense linear systems with verified computing on clusters. This approach enabled our parallel solver to compute huge linear systems with point or interval input matrices with dimensions up to 100,000. Numerical experiments show that the new version of our parallel solver introduced in this paper provides good relative speedups and delivers a reliable enclosure of the exact results. Copyright © 2014 John Wiley & Sons, Ltd.     

Optimal egress time calculation and path generation for large evacuation networks

Finding the optimal clearance time and deciding the path and schedule of evacuation for large networks have traditionally been computationally intensive. In this paper, we propose a new method for finding the solution for this dynamic network flow problem with considerably lower computation time. Using a three phase solution method, we provide solutions for required clearance time for complete evacuation, minimum number of evacuation paths required for evacuation in least possible time and the starting schedules on those paths. First, a lower bound on the clearance time is calculated using minimum cost dynamic network flow model on a modified network graph representing the transportation network. Next, a solution pool of feasible paths between all O-D pairs is generated. Using the input from the first two models, a flow assignment model is developed to select the best paths from the pool and assign flow and decide schedule for evacuation with lowest clearance time possible. All the proposed models are mixed integer linear programing models and formulation is done for System Optimum (SO) scenario where the emphasis is on complete network evacuation in minimum possible clearance time without any preset priority. We demonstrate that the model can handle large size networks with low computation time. A numerical example illustrates the applicability and effectiveness of the proposed approach for evacuation.     

On the preliminary design of axial fans: extending the validity of the flow assumptions over the whole hydraulic characteristic and improvement of modeling

In order to carry out a preliminary axial fan design, established assumptions are made onto the flow structure within the fan at the design point. As an example the very common hypothesis of radial equilibrium, states that the radial velocity component downstream the fan is zero, and that the flow in this area is axisymmetric. With the help of this hypothesis, the flow is idealized in order to draw quantitative conclusions. The present communication aims at extending these assumptions on the whole flow regime in order to help fan designers to reduce the try-and-error cycle number. An analytical formulation for axial fan velocity distributions at design and off design conditions is proposed for an arbitrary work distribution. It is shown that the total pressure characteristics can be described by means of hyperbola and straight line. (© 2014 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Numerical analysis of heat transfer characteristics in energy piles

Single energy pile is studied numerically by both commercial code (CFX 13.0) and open-source software (OpenFOAM). Both fluid and solid domains are simulated. The temperature distribution in the soil and fluid shows the consistency of the two software. Because of the high computational cost for the simulation of multiple piles, a simplification approach is proposed. The fluid temperatures are updated by iterative analytical calculation while the soil temperatures are simulated by conductive heat transfer equation using OpenFOAM. By this effort, the computation of the whole energy pile system is feasible. (© 2014 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Parallel and sequential computation: a statistician's view

I borrow themes from statistics—epsecially the Bayesian ideas underlying average-case analysis and ideas of sequential design of experiments—to discuss when parallel computation is likely to be an attractive technique.     

Effective discretization of the two-dimensional wave equation

The wave equation and associated spherical means are a widespread model in modern imaging modalities like photoacoustic tomography. We consider a discretization for the Cauchy problem of the two dimensional wave equation by plane waves. The considered frequencies lie on a Cartesian or on a polar grid which gives rise to efficient algorithms for the computation of the spherical means. The theoretical findings are illustrated by a some numerical experiments. (© 2014 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)