A new adaptive GMRES algorithm for achieving high accuracy

GMRES(k) is widely used for solving non-symmetric linear systems. However, it is inadequate either when it converges only for k close to the problem size or when numerical error in the modified Gram–Schmidt process used in the GMRES orthogonalization phase dramatically affects the algorithm performance. An adaptive version of GMRES(k) which tunes the restart value k based on criteria estimating the GMRES convergence rate for the given problem is proposed here. This adaptive GMRES(k) procedure outperforms standard GMRES(k), several other GMRES-like methods, and QMR on actual large scale sparse structural mechanics postbuckling and analog circuit simulation problems. There are some applications, such as homotopy methods for high Reynolds number viscous flows, solid mechanics postbuckling analysis, and analog circuit simulation, where very high accuracy in the linear system solutions is essential. In this context, the modified Gram–Schmidt process in GMRES, can fail causing the entire GMRES iteration to fail. It is shown that the adaptive GMRES(k) with the orthogonalization performed by Householder transformations succeeds whenever GMRES(k) with the orthogonalization performed by the modified Gram–Schmidt process fails, and the extra cost of computing Householder transformations is justified for these applications. © 1998 John Wiley & Sons, Ltd.     

Probability-one homotopy maps for mixed complementarity problems

Probability-one homotopy algorithms have strong convergence characteristics under mild assumptions. Such algorithms for mixed complementarity problems (MCPs) have potentially wide impact because MCPs are pervasive in science and engineering. A probability-one homotopy algorithm for MCPs was developed earlier by Billups and Watson based on the default homotopy mapping. This algorithm had guaranteed global convergence under some mild conditions, and was able to solve most of the MCPs from the MCPLIB test library. This paper extends that work by presenting some other homotopy mappings, enabling the solution of all the remaining problems from MCPLIB. The homotopy maps employed are the Newton homotopy and homotopy parameter embeddings.     

Characterization and comparison of the chromatographic performance of conventional,polar-embedded,and polar-endcapped reversed-phase liquid chromatography stationary phases

We have evaluated and compared the performance of several conventional C18 phases with those possessing either a polar-endcapping group or a polar-embedded group within the primary alkyl ligand and found distinct differences in the chromatographic behavior among the three groups, as well as a high degree of variability within each group. The trend is for the polar-endcapped phases to display similar hydrophobic retention characteristics as the conventional C18 columns, but to express higher hydrogen bonding capacities and silanol activity. The polar-embedded phases displayed the opposite behavior, with a greatly reduced hydrophobic nature compared to the conventional and polar-endcapped C18 phases, and also a very much reduced silanol activity. Most interestingly, it appears that ionic or dipole interactions play a significant role in the overall retention behavior of the polar-embedded phases towards basic and acidic analytes.     

Volume-load capacity in fast-gradient liquid chromatography effect of sample solvent composition and injection volume on chromatographic performance

We studied the effects of sample solvent composition and injection volumes on the chromatographic performance of ODS-bonded silica columns under fast-gradient running conditions. Chromatographic performance is compromised as a function of both sample injection volume and sample solvent strength, with earlier-eluting analytes being much more affected than later-eluting ones. In general, when injecting samples dissolved in a strong solvent, performance was improved by diluting the strong injection solvent and injecting a proportionally larger volume. Volume loading capacity can be increased by using a longer column, or by using a column of equivalent length, but with a larger inner diameter. Data also suggest that sample solvent strength, not viscosity, is responsible for the noted effects.     

Viscoelastic suppression of gravity-driven counterflow instability

Attempts to achieve "top kill" of flowing oil wells by pumping dense drilling "muds," i.e., slurries of dense minerals, from above will fail if the Kelvin-Helmholtz instability in the gravity-driven counterflow produces turbulence that breaks up the denser fluid into small droplets. Here we estimate the droplet size to be submillimeter for fast flows and suggest the addition of a shear-thickening or viscoelastic polymer to suppress turbulence. We find in laboratory experiments a variety of new physical effects for a viscoelastic shear-thickening liquid in a gravity-driven counterstreaming flow. There is a progression from droplet formation to complete turbulence suppression at the relevant high velocities. Thick descending columns show a viscoelastic analogue of the viscous buckling instability. Thinner streams form structures resembling globules on a looping filament.     

Probability-one homotopies in computational science

Probability-one homotopy algorithms are a class of methods for solving nonlinear systems of equations that, under mild assumptions, are globally convergent for a wide range of problems in science and engineering. Convergence theory, robust numerical algorithms, and production quality mathematical software exist for general nonlinear systems of equations, and special cases such as Brouwer fixed point problems, polynomial systems, and nonlinear constrained optimization. Using a sample of challenging scientific problems as motivation, some pertinent homotopy theory and algorithms are presented. The problems considered are analog circuit simulation (for nonlinear systems), reconfigurable space trusses (for polynomial systems), and fuel-optimal orbital rendezvous (for nonlinear constrained optimization). The mathematical software packages HOMPACK90 and POLSYS_PLP are also briefly described.     

Computational study of a nonhierarchical decomposition algorithm

Optimizing the design of complex ground and flight vehicles involves multiple disciplines and multilayered computer codes stitched together from mostly incompativle disciplinary codes. The application of established, large-scale, optimization algorithms to the complete model is nearly impossible. Hierarchical decompositions are inappropriate for these types of problems and do not parallelize well. Sobieszczanski-Sobieski has proposed a nonhierarchical decomposition strategyfor nonlinear constrained optimization that is naturally parallel. Despite some successes on engineering problems, the algorithm as originally proposed fails on simple two-dimensional quadratic programs. This paper demonstrates the failure of the algorithm for quadratic programs and suggests a number of possible modifications.     

Parallel deterministic and stochastic global minimization of functions with very many minima

The optimization of three problems with high dimensionality and many local minima are investigated under five different optimization algorithms: DIRECT, simulated annealing, Spall’s SPSA algorithm, the KNITRO package, and QNSTOP, a new algorithm developed at Indiana University.     

Design and implementation of a massively parallel version of DIRECT

This paper describes several massively parallel implementations for a global search algorithm DIRECT. Two parallel schemes take different approaches to address DIRECT’s design challenges imposed by memory requirements and data dependency. Three design aspects in topology, data structures, and task allocation are compared in detail. The goal is to analytically investigate the strengths and weaknesses of these parallel schemes, identify several key sources of inefficiency, and experimentally evaluate a number of improvements in the latest parallel DIRECT implementation. The performance studies demonstrate improved data structure efficiency and load balancing on a 2200 processor cluster.