Optimality relationships forp-cyclic SOR

Summary The optimality question for blockp-cyclic SOR iterations discussed in Young and Varga is answered under natural conditions on the spectrum of the block Jacobi matrix. In particular, it is shown that repartitioning a blockp-cyclic matrix into a blockq-cyclic form,q, results in asymptotically faster SOR convergence for the same amount of work per iteration. As a consequence block 2-cyclic SOR is optimal under these conditions.Research supported in part by the US Air Force under Grant no. AFOSR-88-0285 and the National Science Foundation under grant no. DMS-85-21154 Present address: Boeing Computer Services, P.O. Box 24346, MS 7L-21, Seattle, WA 98124-0346, USA     

Structural studies of Cr-doped mullite derived from single-phase precursors

Cr-doped mullites were prepared from single-phase precursors containing up to 9.60 wt% Cr₂O₃ using a sol-gel technique followed by thermal treatment. Particle induced X-ray emission spectroscopy and X-ray powder diffraction were used to characterize the samples. Mullites were orthorhombic, space group Pbam. Cr doping caused the increase of unit-cell parameters. Strongest expansion was noticed along c-axis followed by a and b (Δc/c=0.089, Δa/a=0.061, Δb/b=0.045% per mole Cr₂O₃). A second phase, namely θ-(Al,Cr)₂O₃, was revealed by XRD in the sample containing 9.60 wt% Cr₂O₃. The structure of mullites was refined by the Rietveld method, location of Cr³⁺ was performed by the EPR spectroscopy. At low chromium doping level (Cr₂O₃ content less than ∼5 wt%) Cr³⁺ ions were substituted for Al³⁺ in the AlO₆ octahedra of the mullite structure (M1 site). For higher doping level, Cr³⁺ ions were additionally substituted for Al³⁺ in the AlO₆ octahedra of the second phase [θ-(Al,Cr)₂O₃ at 1400 °C, or α-(Al,Cr)₂O₃ at 1600 °C] which segregated in the system. Substitution of Cr³⁺ for Al³⁺ on M1 site in the mullite structure resulted in increase of average distances in (M1)O₆ octahedron and decrease of average distances in T*O₄ tetrahedron, while average distances in TO₄ tetrahedron stayed almost constant.     

The existence of smooth densities for the prediction filtering and smoothing problems

The qualitative behavior of buckled states of two different models of elastic beams is studied. It is assumed that random imperfections affect the governing nonlinear equations. It is shown that near the first critical value of the buckling load the stochastic bifurcation is described asymptotically by an algebraic equation whose coeffficients are Gaussian random variables. The corresponding asymptotic expansion for the displacement is to lowest order a Gaussian stochastic process.Work supported by NSF Grant No. DCR81-14726.Work supported by NSF Grant No. DMS87-01895.     

Limits of parallelism in explicit ODE methods

Numerical methods for ordinary initial value problems that do not depend on special properties of the system are usually found in the class of linear multistage multivalue methods, first formulated by J.C. Butcher. Among these the explicit methods are easiest to implement. For these reasons there has been considerable research activity devoted to generating methods of this class which utilize independent function evaluations that can be performed in parallel. Each such group of concurrent function evaluations can be regarded as a stage of the method. However, it turns out that parallelism affords only limited opportunity for reducing the computing time with such methods. This is most evident for the simple linear homogeneous constant-coefficient test problem, whose solution is essentially a matter of approximating the exponential by an algebraic function. For a given number of stages and a given number of saved values, parallelism offers a somewhat enlarged set of algebraic functions from which to choose. However, there is absolutely no benefit in having the degree of parallelism (number of processors) exceed the number of saved values of the method. Thus, in particular, parallel one-step methods offer no speedup over serial one-step methods for the standard linear test problem. Although the implication of this result for general nonlinear problems is unclear, there are indications that dramatic speedups are not possible in general. Also given are some results relevant to the construction of methods.Work supported in part by National Science Foundation grants DMS 89 11410 and DMS 90 15533 and by US Department of Energy grant DOE DEFG02-87ER25026. Work of the second author was completed while at the University of Illinois.     

Conversion of single-stranded oligonucleotides into cloned duplexes and its consecutive application to short artificial genes.

A general method to convert single-stranded, chemically synthesized oligonucleotides into cloned duplexes is described. Oligonucleotides supplied with 3'-terminal extensions that are complementary to 3'-protruding ends obtained by certain restriction enzymes can be cloned either directly or with the help of an adapter molecule into double-stranded vectors. Two methods have also been developed for consecutive cloning applications. According to these methods, the synthetic oligonucleotides (and their enzymatically prepared complementary strands) are joined, one after the other, inside a cloning vector, each joining requiring one cloning step. Synthetic genes are thus built up from oligonucleotides corresponding to only one strand of the DNA. The sequential assembly of the cloned duplex takes place in the 5' to 3' direction. Each oligonucleotide is supplied with a four-nucleotide-long 3'-terminal extension, but this sequence is eliminated when the joining takes place, leaving no limiting sequence between the oligonucleotides. The two consecutive cloning methods, the adapter and the polycloning site methods, are illustrated by the assembly of short artificial genes.     

Scheduling real-time and non-real-time traffic under nonstationary conditions

In this paper a statistical multiplexer that processes a mixture of real-time and non-real-time traffic is studied under bursts of traffic. Different scheduling algorithms are compared under conditions when one of the classes of traffic has a sudden increase in its arrival rate during a short period of time. The results show a difference in the way the scheduling disciplines studied behave under short overloads of traffic even though the scheduling algorithms had been set up to give similar performance under steady-state arrivals. The lifetime of real-time packets is shown to have a great effect on the way in which the performance of the scheduling algorithms compare.Robert Lackman is an IBM employee in the IBM Resident Study Program.     

Sewings of crumpled cubes revisited

This paper sets forth three mismatch properties, strictly ordered in strength, about sewings of crumpled n-cubes. The strongest is a sufficient but not a necessary condition for a sewing to yield Sn, and the weakest, a necessary but not sufficient one. We show that when both crumpled cubes satisfies the Disjoint Disks Property, then the weakest property implies the sewing yields Sn, and we also show that the intermediate property leads to the same conclusion when just one of the crumpled cubes possesses the Disjoint Disks Property. In addition, we develop examples that confirm sharpness of the relevant Disjoint Disks conditions.     

On Two Measures of Problem Instance Complexity and their Correlation with the Performance of SeDuMi on Second-Order Cone Problems

We evaluate the practical relevance of two measures of conic convex problem complexity as applied to second-order cone problems solved using the homogeneous self-dual (HSD) embedding model in the software SeDuMi. The first measure we evaluate is Renegar's data-based condition measure C(d), and the second measure is a combined measure of the optimal solution size and the initial infeasibility/optimality residuals denoted by S (where the solution size is measured in a norm that is naturally associated with the HSD model). We constructed a set of 144 second-order cone test problems with widely distributed values of C(d) and S and solved these problems using SeDuMi. For each problem instance in the test set, we also computed estimates of C(d) (using Peña’s method) and computed S directly. Our computational experience indicates that SeDuMi iteration counts and log (C(d)) are fairly highly correlated (sample correlation R = 0.675), whereas SeDuMi iteration counts are not quite as highly correlated with S (R = 0.600). Furthermore, the experimental evidence indicates that the average rate of convergence of SeDuMi iterations is affected by the condition number C(d) of the problem instance, a phenomenon that makes some intuitive sense yet is not directly implied by existing theory.