Symbolic computation of conservation laws for nonlinear partial differential equations in multiple space dimensions

A method for symbolically computing conservation laws of nonlinear partial differential equations (PDEs) in multiple space dimensions is presented in the language of variational calculus and linear algebra. The steps of the method are illustrated using the Zakharov–Kuznetsov and Kadomtsev–Petviashvili equations as examples.The method is algorithmic and has been implemented in Mathematica. The software package, ConservationLawsMD.m, can be used to symbolically compute and test conservation laws for polynomial PDEs that can be written as nonlinear evolution equations.The code ConservationLawsMD.m has been applied to multi-dimensional versions of the Sawada–Kotera, Camassa–Holm, Gardner, and Khokhlov–Zabolotskaya equations.     

Fast parallel solution of boundary integral equations and related problems

This article is concerned with the efficient numerical solution of Fredholm integral equations on a parallel computer with shared or distributed memory. Parallel algorithms for both, the approximation of the discrete operator by hierarchical matrices using adaptive cross approximation (ACA) and the parallel matrix-vector multiplication of such matrices by a vector, are presented. The first algorithm has a complexity of order p ^-1 N log^2d-1 N, while the latter is of order p ^-1 N log ^d N, where N, d and p are the number of unknowns, the spatial dimension and the number of processors, respectively. The approximant needs Ω(p ^-1 N log ^d N) units of storage on each processor. Dedicated to George C. Hsiao on the occasion of his 70th birthday. Mathematics Subject Classification (2000)65D05 65D15 65F05 65F30 Communicated by: U. Langer     

Iterative methods to compute weighted normal pseudosolutions with positive definite weights

We construct iterative processes to compute the weighted normal pseudosolution with positive definite weights (weighted least squares solutions with weighted minimum Euclidean norm) for systems of linear algebraic equations (SLAE) with an arbitrary rectangular real matrix. We examine two iterative processes based on the expansion of the weighted pseudoinversc matrix into matrix power series. The iterative processes are applied to solve constrained least squares problems that arise in mathematical programming and to findL-pseudosolutions. Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 116–124, March–April, 1998.     

High-order discontinuous Galerkin computation of axisymmetric transonic flows in safety relief valves

This paper presents a discontinuous Galerkin (DG) discretization of the compressible RANS and k–ω turbulence model equations for two-dimensional axisymmetric flows. The developed code has been applied to investigate the transonic flow in safety relief valves.This new DG implementation has evolved from the DG method presented in [1]. An “exact” Riemann solver is used to compute the interface numerical inviscid flux while the viscous flux discterization relies on the BRMPS scheme [2] and [3]. Control of oscillations of high-order solutions around shocks is obtained by means of a shock-capturing technique developed and assessed within the EU ADIGMA project [4].The code has been applied to compute the flow in a spring loaded safety valve at several back pressures and different disk lifts. The predicted device flow capacity and the pressure inside its bonnet have been checked against experimental data. The CFD simulations allow to clarify the complex flow patterns occurring and to explain the measured trends.     

Fast qz decomposition and its applications

The ability to introduce zeros in a selective fashion makes the Givens Rotations an important zeroing tool in certain structured matrix problems. Evans and Yalamov [2] combined two Givens Rotations in one step to annihilate two elements simultaneously in order to transform the original matrix to a “Z” form pattern. The composite scheme was called the QZ decomposition method and is suitable for parallel computation, which is confirmed by the numerical results [1].

In this paper, firstly the fast computation of the QZ decomposition is given, which eliminates the square roots and reduces the number of multiplications by 37.5%. Finally, the applications of the fast QZ decomposition method to the linear system of equations, least squares problem and the weighted least squares problem are considered.     

Solving the block–Toeplitz least‐squares problem in parallel

In this paper we present two versions of a parallel algorithm to solve the block–Toeplitz least‐squares problem on distributed‐memory architectures. We derive a parallel algorithm based on the seminormal equations arising from the triangular decomposition of the product T^TT. Our parallel algorithm exploits the displacement structure of the Toeplitz‐like matrices using the Generalized Schur Algorithm to obtain the solution in O(mn) flops instead of O(mn²) flops of the algorithms for non‐structured matrices. The strong regularity of the previous product of matrices and an appropriate computation of the hyperbolic rotations improve the stability of the algorithms. We have reduced the communication cost of previous versions, and have also reduced the memory access cost by appropriately arranging the elements of the matrices. Furthermore, the second version of the algorithm has a very low spatial cost, because it does not store the triangular factor of the decomposition. The experimental results show a good scalability of the parallel algorithm on two different clusters of personal computers. Copyright © 2005 John Wiley & Sons, Ltd.     

An iterative algorithm for a least squares solution of a matrix equation

In this article, we propose an iterative algorithm to compute the minimum norm least-squares solution of AXB+CYD=E, based on a matrix form of the algorithm LSQR for solving the least squares problem. We then apply this algorithm to compute the minimum norm least-squares centrosymmetric solution of min _X ‖AXB?E‖ _F . Numerical results are provided to verify the efficiency of the proposed method.     

Pseudospectral method of solution of the Fitzhugh–Nagumo equation

We present a study of the convergence of different numerical schemes in the solution of the Fitzhugh–Nagumo equations in the form of two coupled reaction diffusion equations for activator and inhibitor variables. The diffusion coefficient for the inhibitor is taken to be zero. The Fitzhugh–Nagumo equations, have spatial and temporal dynamics in two different scales and the solutions exhibit shock-like waves. The numerical schemes employed are a Chebyshev multidomain method, a finite difference method and the method developed by Barkley [D. Barkley, A model for fast computer simulation of excitable media, Physica D, 49 (1991) 61–70]. We consider two different models for the local dynamics. We present results for plane wave propagation in one dimension and spiral waves for two dimensions. We use an operator splitting method with the Chebyshev multidomain approach in order to reduce the computational time. Zero flux boundary conditions are imposed on the solutions.     

Parallel implementation of the Kronecker product technique for numerical solution of parabolic partial differential equations

Using the alternating directional Galerkin technique we show that the approximate solution of the initial boundary value problem of parabolic partial differential equations is equivalent to the least squares solution of the linear system A B = b. In the full rank case, an efficient method for obtaining the solution of the least squares problem suitable for distributive memory computers was presented in (Fausett et al., 1994). This method is extended to solve the rank deficient case using the RRQR factorization of matrices A and B together with the commutatively property of the Kronecker product. Solution algorithm and parallel implementation are discussed. Timing results are presented and compared with previous work.     

Fast QR factorization of low-rank changes of Vandermonde-like matrices

This paper is concerned with the solution of linear systems with coefficient matrices which are Vandermonde-like matrices modified by adding low-rank corrections. Hereafter we refer to these matrices as modified Vandermonde-like matrices. The solution of modified Vandermonde-like linear systems arises in approximation theory both when we use Remez algorithms for finding minimax approximations and when we consider least squares problems with constraints. Our approach relies on the computation of an inverse QR factorization. More specifically, we show that some classical orthogonalization schemes for m×n, m≥n, Vandermonde-like matrices can be extended to compute efficiently an inverse QR factorization of modified Vandermonde-like matrices. The resulting algorithm has a cost of O(mn) arithmetical operations. Moreover it requires O(m) storage since the matrices Q and R are not stored. Received: January 1997 / Accepted: November 1997     

A conservative discontinuous Galerkin scheme for the 2D incompressible Navier–Stokes equations

In this paper we consider a conservative discretization of the two-dimensional incompressible Navier–Stokes equations. We propose an extension of Arakawa’s classical finite difference scheme for fluid flow in the vorticity–stream function formulation to a high order discontinuous Galerkin approximation. In addition, we show numerical simulations that demonstrate the accuracy of the scheme and verify the conservation properties, which are essential for long time integration. Furthermore, we discuss the massively parallel implementation on graphic processing units.     

Some generalizations of comparison results for fractional differential equations

In this paper, by using the technique of upper and lower solutions together with the theory of strict and nonstrict fractional differential inequalities involving Riemann–Liouville differential operator of order q, 0<q<1, some necessary comparison results for further generalizations of several dynamical concepts are obtained. Furthermore, these results are extended to the finite systems of fractional differential equations.     

The Boltzmann–Hamel equations for the optimal control of mechanical systems with nonholonomic constraints

In this paper, we generalize the Boltzmann–Hamel equations for nonholonomic mechanics to a form suited for the kinematic or dynamic optimal control of mechanical systems subject to nonholonomic constraints. In solving these equations one is able to eliminate the controls and compute the optimal trajectory from a set of coupled first‐order differential equations with boundary values. By using an appropriate choice of quasi‐velocities, one is able to reduce the required number of differential equations by m and 3m for the kinematic and dynamic optimal control problems, respectively, where m is the number of nonholonomic constraints. In particular we derive a set of differential equations that yields the optimal reorientation path of a free rigid body. In the special case of a sphere, we show that the optimal trajectory coincides with the cubic splines on SO(3). Copyright © 2010 John Wiley & Sons, Ltd.     

Mixed operator problems using least squares finite element collocation

A finite element method based on least squares collocation on an element is formulated for problems of mixed type. The least squares method is developed using an incomplete quintic (C¹) element and overdetermined element collocation equations. Numerical experiments are conducted for the classical Tricomi equation, and the accuracy of computed solutions is examined at points in elliptic and hyperbolic subdomains.     

Identification of multi-input systems based on correlation techniques

This article proposes a correlation analysis-based identification method for multi-input single-output systems. The basic idea is to estimate the equivalent FIR model parameters with the orders increasing, and to compute the parameter estimates of the original systems (i.e. each fictitious subsystem) using the system inputs and the outputs of the estimated FIR models and using the least squares optimisation. Simulation results indicate that the proposed algorithm can work well.     

Computational simulation of model and full scale Class 8 trucks with drag reduction devices

Numerical solutions of the unsteady Reynolds-averaged Navier–Stokes equations using a parallel implicit flow solver are given to investigate unsteady aerodynamic flows affecting the fuel economy of Class 8 trucks. Both compressible and incompressible forms of the equations are solved using a finite-volume discretization for unstructured grids and using Riemann-based interfacial fluxes and characteristic-variable numerical boundary conditions. A preconditioned primitive-variable formulation is used for compressible solutions, and the incompressible solutions employ artificial compressibility. Detached eddy simulation (DES) versions of the one-equation Menter SAS and the two-equation k − ?/k − ω hybrid turbulence models are used. A fully nonlinear implicit backward-time approximation is solved using a parallel Newton-iterative algorithm with numerically computed flux Jacobians. Unsteady three-dimensional aerodynamic simulations with grids of 18–20 million points and 50,000 time steps are given for the Generic Conventional Model (GCM), a 1:8 scale tractor–trailer model that was tested in the NASA Ames 7 × 10 tunnel. Computed pressure coefficients and drag force are in good agreement with measurements for a zero-incidence case. Similar computations for a case with 10° yaw gave reasonable agreement for drag force, while the pressure distributions suggested the need for tighter grid resolution or possibly improved turbulence models. Unsteady incompressible flow simulations were performed for a modified full scale version of the GCM geometry to evaluate drag reduction devices. All of these simulations were performed with a moving ground plane and rotating rear wheels. A simulation with trailer base flaps is compared with drag reduction data from wind tunnels and track and road tests. A front spoiler and three mud-flap designs with modest drag reduction potential are also evaluated.     

Approximate factorization of multivariate polynomials using singular value decomposition

We describe the design, implementation and experimental evaluation of new algorithms for computing the approximate factorization of multivariate polynomials with complex coefficients that contain numerical noise. Our algorithms are based on a generalization of the differential forms introduced by W. Ruppert and S. Gao to many variables, and use singular value decomposition or structured total least squares approximation and Gauss–Newton optimization to numerically compute the approximate multivariate factors. We demonstrate on a large set of benchmark polynomials that our algorithms efficiently yield approximate factorizations within the coefficient noise even when the relative error in the input is substantial (10⁻³).     

Piece wise linear least–squares approximation of planar curves

Two algorithms for solving the piecewise linear least–squares approximation problem of plane curves are presented. The first is for the case when the L ₂ residual (error) norm in any segment is not to exceed a pre–assigned value. The second algorithm is for the case when the number of segments is given and a (balanced) L ₂ residual norm solution is required. The given curve is first digitized and either algorithm is then applied to the discrete points. For each segment, we obtain the upper triangular matrix R in the QR factorization of the (augmented) coefficient matrix of the resulting system of linear equations. The least–squares solutions are calculated in terms of the R (and Q) matrices. The algorithms then work in an iterative manner by updating the least–squares solutions for the segments via up dating the R matrices. The calculation requires as little computational effort as possible. Numerical results and comments are given. This, in a way, is a tutorial paper.     

FFTs in external or hierarchical memory

Conventional algorithms for computing large one-dimensional fast Fourier transforms (FFTs), even those algorithms recently developed for vector and parallel computers, are largely unsuitable for systems with external or hierarchical memory. The principal reason for this is the fact that most FFT algorithms require at least m complete passes through the data set to compute a 2 ^m -point FFT. This paper describes some advanced techniques for computing an ordered FFT on a computer with external or hierarchical memory. These algorithms (1) require as few as two passes through the external data set, (2) employ strictly unit stride, long vector transfers between main memory and external storage, (3) require only a modest amount of scratch space in main memory, and (4) are well suited for vector and parallel computation.Performance figures are included for implementations of some of these algorithms on Cray supercomputers. Of interest is the fact that a main memory version outperforms the current Cray library FFT routines on the CRAY-2, the CRAY X-MP, and the CRAY Y-MP systems. Using all eight processors on the CRAY Y-MP, this main memory routine runs at nearly two gigaflops.A condensed version of this paper previously appeared in the Proceedings of Supercomputing '89.     

Optimal expectile smoothing

Quantiles are computed by optimizing an asymmetrically weighted L₁ norm, i.e. the sum of absolute values of residuals. Expectiles are obtained in a similar way when using an L₂ norm, i.e. the sum of squares. Computation is extremely simple: weighted regression leads to the global minimum in a handful of iterations. Least asymmetrically weighted squares are combined with P-splines to compute smooth expectile curves. Asymmetric cross-validation and the Schall algorithm for mixed models allow efficient optimization of the smoothing parameter. Performance is illustrated on simulated and empirical data.