Narrow Results

We investigate the computational power of parallel models with directed reconfigurable buses and with shared memory. Based on feasibility considerations present in the literature, we split these models into "heavyweight" (directed reconfigurable buses, the Combining PRAM, and the BSR) and "lightweight" (all the other PRAMs) and then find that the heavyweight class is strictly more powerful than the lightweight class, as expected. On the other hand, we contradict the long held belief that the heavyweight models form a hierarchy, showing that all of them are identical in computational power with each other. We start the process by showing that the Collision write conflict resolution rule is universal on models with reconfigurable buses (in the sense that complex conflict resolution rules such as Priority and Combining can be simulated with constant overhead by Collision).

The question of whether quantum real-time one-counter automata (rtQ1CAs) can outperform their probabilistic counterparts has been open for more than a decade. We provide an affirmative answer to this question, by demonstrating a non-context-free language that can be recognized with perfect soundness by a rtQ1CA. This is the first demonstration of the superiority of a quantum model to the corresponding classical one in the real-time case with an error bound less than 1. We also introduce a generalization of the rtQ1CA, the quantum one-way one-counter automaton (1Q1CA), and show that they too are superior to the corresponding family of probabilistic machines. For this purpose, we provide general definitions of these models that reflect the modern approach to the definition of quantum finite automata, and point out some problems with previous results. We identify several remaining open problems.

We assume the multitape real-time Turing machine as a formal model for parallel real-time computation. Then, we show that, for any positive integer k, there is at least one language L_k which is accepted by a k-tape real-Turing machine, but cannot be accepted by a (k - 1)-tape real-time Turing machine. It follows therefore that the languages accepted by real-time Turing machines form an infinite hierarchy with respect to the number of tapes used. Although this result was previously obtained elsewhere, our proof is considerably shorter, and explicitly builds the languages L_k. The ability of the real-time Turing machine to model practical real-time and/or parallel computations is open to debate. Nevertheless, our result shows how a complexity theory based on a formal model can draw interesting results that are of more general nature than those derived from examples. Thus, we hope to offer a motivation for looking into realistic parallel real-time models of computation.

This paper focuses on the improvement in the quality of computation provided by parallelism. The problem of interest is that of computing the maximum of a nonlinear feedback function in a real-time environment. We show that the solution obtained in parallel is significantly, provably, and consistently better than a sequential one. It is important to note that our purpose is not to demonstrate merely that a parallel computer can obtain a solution to a computational problem that is of higher quality than one derived sequentially. The latter is an interesting (and often surprising) observation in its own right, but we wish to go further. It is shown here that the improvement in quality due to parallelism can be arbitrarily high. To be specific, the ratio of the parallel solution to the sequential one is typically superlinear in the number of processors used by the parallel computer. This result is akin to superlinear speedup—a phenomenon itself originally thought to be impossible.

A new computational paradigm is described which offers the possibility of superlinear (and sometimes unbounded) speedup, when parallel computation is used. The computations involved are subject only to given mathematical constraints and hence do not depend on external circumstances to achieve superlinear performance. The focus here is on geometric transformations. Given a geometric object A with some property, it is required to transform A into another object B which enjoys the same property. If the transformation requires several steps, each resulting in an intermediate object, then each of these intermediate objects must also obey the same property. We show that in transforming one triangulation of a polygon into another, a parallel algorithm achieves a superlinear speedup. In the case where a convex decomposition of a set of points is to be transformed, the improvement in performance is unbounded, meaning that a parallel algorithm succeeds in solving the problem as posed, while all sequential algorithms fail.

It is shown that the concept of a Universal Computer cannot be realized. Specifically, instances of a computable function are exhibited that cannot be computed on any machine that is capable of only a finite and fixed number of operations per step. This remains true even if the machine is endowed with an infinite memory and the ability to communicate with the outside world while it is attempting to compute . It also remains true if, in addition, is given an indefinite amount of time to compute . This result applies not only to idealized models of computation, such as the Turing Machine and the like, but also to all known general-purpose computers, including existing conventional computers (both sequential and parallel), as well as contemplated unconventional ones such as biological and quantum computers. Even accelerating machines (that is, machines that increase their speed at every step) cannot be universal.

In this paper we present reduced basis (RB) approximations and associated rigorous a posteriori error bounds for the parametrized unsteady Boussinesq equations. The essential ingredients are Galerkin projection onto a low-dimensional space associated with a smooth parametric manifold — to provide dimension reduction; an efficient proper orthogonal decomposition–Greedy sampling method for identification of optimal and numerically stable approximations — to yield rapid convergence; accurate (online) calculation of the solution-dependent stability factor by the successive constraint method — to quantify the growth of perturbations/residuals in time; rigorous a posteriori bounds for the errors in the RB approximation and associated outputs — to provide certainty in our predictions; and an offline–online computational decomposition strategy for our RB approximation and associated error bound — to minimize marginal cost and hence achieve high performance in the real-time and many-query contexts. The method is applied to a transient natural convection problem in a two-dimensional "complex" enclosure — a square with a small rectangle cutout — parametrized by Grashof number and orientation with respect to gravity. Numerical results indicate that the RB approximation converges rapidly and that furthermore the (inexpensive) rigorous a posteriori error bounds remain practicable for parameter domains and final times of physical interest.

We present reduced basis approximations and associated rigorous a posteriori error bounds for the Stokes equations in parametrized domains. The method, built upon the penalty formulation for saddle point problems, provides error bounds not only for the velocity but also for the pressure approximation, while simultaneously admitting affine geometric variations with relative ease. The essential ingredients are: (i) dimension reduction through Galerkin projection onto a low-dimensional reduced basis space; (ii) stable, good approximation of the pressure through supremizer-enrichment of the velocity reduced basis space; (iii) optimal and numerically stable approximations identified through an efficient greedy sampling method; (iv) certainty, through rigorous a posteriori bounds for the errors in the reduced basis approximation; and (v) efficiency, through an offline-online computational strategy. The method is applied to a flow problem in a two-dimensional channel with a (parametrized) rectangular obstacle. Numerical results show that the reduced basis approximation converges rapidly, the effectivities associated with the (inexpensive) rigorous a posteriori error bounds remain good even for reasonably small values of the penalty parameter, and that the effects of the penalty parameter are relatively benign.