Alternatives for parallel Krylov subspace basis computation

Numerical methods related to Krylov subspaces are widely used in large sparse numerical linear algebra. Vectors in these subspaces are manipulated via their representation onto orthonormal bases. Nowadays, on serial computers, the method of Arnoldi is considered as a reliable technique for constructing such bases. However, although easily parallelizable, this technique is not as scalable as expected for communications. In this work we examine alternative methods aimed at overcoming this drawback. Since they retrieve upon completion the same information as Arnoldi's algorithm does, they enable us to design a wide family of stable and scalable Krylov approximation methods for various parallel environments. We present timing results obtained from their implementation on two distributed-memory multiprocessor supercomputers: the Intel Paragon and the IBM Scalable POWERparallel SP2. (C) 1997 by John Wiley & Sons, Ltd.

QRT: A Qr-based tridiagonalization algorithm for nonsymmetric matrices

The stable similarity reduction of a nonsymmetric square matrix to tridiagonal form has been a long-standing problem in numerical linear algebra. The biorthogonal Lanczos process is in principle a candidate method for this task, but in practice it is confined to sparse matrices and is restarted periodically because roundoff errors affect its three-term recurrence scheme and degrade the biorthogonality after a few steps. This adds to its vulnerability to serious breakdowns or near-breakdowns, the handling of which involves recovery strategies such as the look-ahead technique, which needs a careful implementation to produce a block-tridiagonal form with unpredictable block sizes. Other candidate methods, geared generally towards full matrices, rely on elementary similarity transformations that are prone to numerical instabilities. Such concomitant difficulties have hampered finding a satisfactory solution to the problem for either sparse or full matrices. This study focuses primarily on full matrices. After outlining earlier tridiagonalization algorithms from within a general framework, we present a new elimination technique combining orthogonal similarity transformations that are stable. We also discuss heuristics to circumvent breakdowns. Applications of this study include eigenvalue calculation and the approximation of matrix functions.

Extended GCD and Hermite normal form algorithms via lattice basis reduction

Extended gcd calculation has a long history and plays an important role in computational number theory and linear algebra. Recent results have shown that finding optimal multipliers in extended gcd calculations is difficult. We present an algorithm which uses lattice basis reduction to produce small integer multipliers x(1), ..., x(m) for the equation s = gcd (s(1), ..., s(m)) = x(1)s(1) + ... + x(m)s(m), where s1, ... , s(m) are given integers. The method generalises to produce small unimodular transformation matrices for computing the Hermite normal form of an integer matrix.

Matrix-product codes over Fq

Codes C-1,...,C-M of length it over F-q and an M x N matrix A over F-q define a matrix-product code C = [C-1 (...) C-M] (.) A consisting of all matrix products [c(1) (...) c(M)] (.) A. This generalizes the (u/u + v)-, (u + v + w/2u + v/u)-, (a + x/b + x/a + b + x)-, (u + v/u - v)- etc. constructions. We study matrix-product codes using Linear Algebra. This provides a basis for a unified analysis of /C/, d(C), the minimum Hamming distance of C, and C-perpendicular to. It also reveals an interesting connection with MDS codes. We determine /C/ when A is non-singular. To underbound d(C), we need A to be 'non-singular by columns (NSC)'. We investigate NSC matrices. We show that Generalized Reed-Muller codes are iterative NSC matrix-product codes, generalizing the construction of Reed-Muller codes, as are the ternary 'Main Sequence codes'. We obtain a simpler proof of the minimum Hamming distance of such families of codes. If A is square and NSC, C-perpendicular to can be described using C-1(perpendicular to),...,C-M(perpendicular to) and a transformation of A. This yields d(C-perpendicular to). Finally we show that an NSC matrix-product code is a generalized concatenated code.

A simple proof of the strong subadditivity inequality

Arguably the deepest fact known about the von Neumann entropy, the strong subadditivity inequality is a potent hammer in the quantum information theorist's toolkit. This short tutorial describes a simple proof of strong subadditivity due to Petz [Rep. on Math. Phys. 23 (1), 57-65 (1986)]. It assumes only knowledge of elementary linear algebra and quantum mechanics.

Theoretical and numerical analyses of convective instability in porous media with upward throughflow

Exact analytical solutions have been obtained for a hydrothermal system consisting of a horizontal porous layer with upward throughflow. The boundary conditions considered are constant temperature, constant pressure at the top, and constant vertical temperature gradient, constant Darcy velocity at the bottom of the layer. After deriving the exact analytical solutions, we examine the stability of the solutions using linear stability theory and the Galerkin method. It has been found that the exact solutions for such a hydrothermal system become unstable when the Rayleigh number of the system is equal to or greater than the corresponding critical Rayleigh number. For small and moderate Peclet numbers (Pe less than or equal to 6), an increase in upward throughflow destabilizes the convective flow in the horizontal layer. To confirm these findings, the finite element method with the progressive asymptotic approach procedure is used to compute the convective cells in such a hydrothermal system. Copyright (C) 1999 John Wiley & Sons, Ltd.

Applying linear time-varying constraints to econometric models: With an application to demand systems

When linear equality constraints are invariant through time they can be incorporated into estimation by restricted least squares. If, however, the constraints are time-varying, this standard methodology cannot be applied. In this paper we show how to incorporate linear time-varying constraints into the estimation of econometric models. The method involves the augmentation of the observation equation of a state-space model prior to estimation by the Kalman filter. Numerical optimisation routines are used for the estimation. A simple example drawn from demand analysis is used to illustrate the method and its application.

Anisotropy-based performance analysis of linear discrete time invariant control systems

The anisotropic norm of a linear discrete-time-invariant system measures system output sensitivity to stationary Gaussian input disturbances of bounded mean anisotropy. Mean anisotropy characterizes the degree of predictability (or colouredness) and spatial non-roundness of the noise. The anisotropic norm falls between the H-2 and H-infinity norms and accommodates their loss of performance when the probability structure of input disturbances is not exactly known. This paper develops a method for numerical computation of the anisotropic norm which involves linked Riccati and Lyapunov equations and an associated special type equation.

Computation of the linear elastic properties of random porous materials with a wide variety of microstructure

A finite-element method is used to study the elastic properties of random three-dimensional porous materials with highly interconnected pores. We show that Young's modulus, E, is practically independent of Poisson's ratio of the solid phase, nu(s), over the entire solid fraction range, and Poisson's ratio, nu, becomes independent of nu(s) as the percolation threshold is approached. We represent this behaviour of nu in a flow diagram. This interesting but approximate behaviour is very similar to the exactly known behaviour in two-dimensional porous materials. In addition, the behaviour of nu versus nu(s) appears to imply that information in the dilute porosity limit can affect behaviour in the percolation threshold limit. We summarize the finite-element results in terms of simple structure-property relations, instead of tables of data, to make it easier to apply the computational results. Without using accurate numerical computations, one is limited to various effective medium theories and rigorous approximations like bounds and expansions. The accuracy of these equations is unknown for general porous media. To verify a particular theory it is important to check that it predicts both isotropic elastic moduli, i.e. prediction of Young's modulus alone is necessary but not sufficient. The subtleties of Poisson's ratio behaviour actually provide a very effective method for showing differences between the theories and demonstrating their ranges of validity. We find that for moderate- to high-porosity materials, none of the analytical theories is accurate and, at present, numerical techniques must be relied upon.

A compartmental model of hepatic disposition kinetics: 1. Model development and application to linear kinetics

The conventional convection-dispersion model is widely used to interrelate hepatic availability (F) and clearance (Cl) with the morphology and physiology of the liver and to predict effects such as changes in liver blood flow on F and Cl. The extension of this model to include nonlinear kinetics and zonal heterogeneity of the liver is not straightforward and requires numerical solution of partial differential equation, which is not available in standard nonlinear regression analysis software. In this paper, we describe an alternative compartmental model representation of hepatic disposition (including elimination). The model allows the use of standard software for data analysis and accurately describes the outflow concentration-time profile for a vascular marker after bolus injection into the liver. In an evaluation of a number of different compartmental models, the most accurate model required eight vascular compartments, two of them with back mixing. In addition, the model includes two adjacent secondary vascular compartments to describe the tail section of the concentration-time profile for a reference marker. The model has the added flexibility of being easy to modify to model various enzyme distributions and nonlinear elimination. Model predictions of F, MTT, CV2, and concentration-time profile as well as parameter estimates for experimental data of an eliminated solute (palmitate) are comparable to those for the extended convection-dispersion model.

Product form approximations for highly linear loss networks with trunk reservation

Admission controls, such as trunk reservation, are often used in loss networks to optimise their performance. Since the numerical evaluation of performance measures is complex, much attention has been given to finding approximation methods. The Erlang Fixed-Point (EFP) approximation, which is based on an independent blocking assumption, has been used for networks both with and without controls. Several more elaborate approximation methods which account for dependencies in blocking behaviour have been developed for the uncontrolled setting. This paper is an exploratory investigation of extensions and synthesis of these methods to systems with controls, in particular, trunk reservation. In order to isolate the dependency factor, we restrict our attention to a highly linear network. We will compare the performance of the resulting approximations against the benchmark of the EFP approximation extended to the trunk reservation setting. By doing this, we seek to gain insight into the critical factors in constructing an effective approximation. (C) 2003 Elsevier Ltd. All rights reserved.

Non-linear analysis of the thermo-electro-mechanical behaviour of shear deformable FGM plates with piezoelectric actuators

This paper investigates the non-linear bending behaviour of functionally graded plates that are bonded with piezoelectric actuator layers and subjected to transverse loads and a temperature gradient based on Reddy's higher-order shear deformation plate theory. The von Karman-type geometric non-linearity, piezoelectric and thermal effects are included in mathematical formulations. The temperature change is due to a steady-state heat conduction through the plate thickness. The material properties are assumed to be graded in the thickness direction according to a power-law distribution in terms of the volume fractions of the constituents. The plate is clamped at two opposite edges, while the remaining edges can be free, simply supported or clamped. Differential quadrature approximation in the X-axis is employed to convert the partial differential governing equations and the associated boundary conditions into a set of ordinary differential equations. By choosing the appropriate functions as the displacement and stress functions on each nodal line and then applying the Galerkin procedure, a system of non-linear algebraic equations is obtained, from which the non-linear bending response of the plate is determined through a Picard iteration scheme. Numerical results for zirconia/aluminium rectangular plates are given in dimensionless graphical form. The effects of the applied actuator voltage, the volume fraction exponent, the temperature gradient, as well as the characteristics of the boundary conditions are also studied in detail. Copyright (C) 2004 John Wiley Sons, Ltd.

Numerical simulation of abrupt contraction flows using the Double Convected Pom-Pom model

The Double Convected Pom-Pom model was recently introduced to circumvent some numerical and theological defects found in other formulations of the Pom-Pom concept. It is used here for the simulation of a benchmark problem: the flow in an abrupt planar contraction. The predictions are compared with birefringence measurements and show reasonable quantitative agreement with experimental data. A parametric study is also carried out with the aim of analysing the effect of the branching parameter on vortex dynamics and extrudate swell. The results show that the Double Convected Pom-Pom model (DCPP) model is able to discriminate between branched and linear macromolecular structures in accordance with experimental observations. In that respect, the role of the extensional properties in determining complex flow behaviour is stressed. Also, the ratio of the first normal stress difference to the shear stress appears to play a major role in die swell observation. For the time being, the role of the second normal stress difference appears to be less obvious to evaluate in this complex flow. (C) 2004 Elsevier B.V. All rights reserved.

Constriction flows of monodisperse linear entangled polymers: Multiscale modeling and flow visualization

We explore both the rheology and complex flow behavior of monodisperse polymer melts. Adequate quantities of monodisperse polymer were synthesized in order that both the materials rheology and microprocessing behavior could be established. In parallel, we employ a molecular theory for the polymer rheology that is suitable for comparison with experimental rheometric data and numerical simulation for microprocessing flows. The model is capable of matching both shear and extensional data with minimal parameter fitting. Experimental data for the processing behavior of monodisperse polymers are presented for the first time as flow birefringence and pressure difference data obtained using a Multipass Rheometer with an 11:1 constriction entry and exit flow. Matching of experimental processing data was obtained using the constitutive equation with the Lagrangian numerical solver, FLOWSOLVE. The results show the direct coupling between molecular constitutive response and macroscopic processing behavior, and differentiate flow effects that arise separately from orientation and stretch. (c) 2005 The Society of Rheology.