Quentin F. Stout Publications

Quentin Stout Publications

Primary areas:

Parallel Computing
Adaptive Sampling, Statistics
Space and Earth Modeling
Scientific Computing and Computational Science
Theoretical Computer Science
Serial Algorithms and Data Structures
Discrete Mathematics: Graph Theory, Combinatorics, Geometry, Codings, Probability
Operator Theory, Analysis
Other Research
Teaching-Related Publications

Most entries include keywords. Sometimes the best way to find what you are interested in is to use the keywords. Many papers are listed in more than one area. The links take you to an abstract, and many entries also have links to the paper. Documents are available in Postscript (paper.ps), compressed Postscript (paper.ps.Z), or PDF (paper.pdf).

Here is my standard academic vita if you want a listing of papers, awards, grants, etc. Several of the papers mentioned there are omitted here since an updated version was publshed later.

Here are some simple explanations of response adaptive sampling and parallel computing

Overview of Research Interests. Home page.

Parallel Computing

Talks

Space, Time, Power: Evolving Concerns for Parallel Algorithms, a talk about the evolution of goals/concerns of parallel models and algorithms, including cellular automata, mesh connected computers, reconfigurable meshes, and power-constrained algorithms for mesh connected computers. It mentions zebra networks and rat algorithms, along with more mundane computers such as the BlueGene and Earth Simulator, and abstract models such as PRAMs and quantum computers.

Books Authored

R. Miller and Q.F. Stout, Parallel Algorithms for Regular Architectures: Meshes and Pyramids, MIT Press, 1996.
Keywords: parallel computing, parallel algorithms, mesh computer, VLSI algorithms, pyramid, data movement operations, graph algorithms, image processing, computational geometry, lower bounds, optimal algorithms.
Q.F Stout and C. Jablonowski, Parallel Computing 101. While not a standard book, the notes for this tutorial are essentially a book overviewing parallel computing and how to develop efficient parallel programs. The tutorial and notes are continually being updated.
Keywords: parallel programming, performance, MPI, OpenMP, Amdahl's law, software engineering, scientific computing, supercomputing, vendors, load balancing, code tuning.

Books Edited

H. Li and Q.F. Stout, eds., Reconfigurable Massively Parallel Computers, Prentice Hall, 1991.
D.W. Walker and Q.F. Stout, eds., Proceedings 5th Distributed Memory Computing Conference, IEEE Computer Society, 2 vols., 1990.
M. Wolfe and Q.F. Stout, Proceedings 6th Distributed Memory Computing Conference, IEEE Computer Society, 1991.
Q.F. Stout, ed., Proceedings 1992 International Conference on Parallel Processing, Vol. III Algorithms and Applications, Computer Science Press.

Chapters in Books

Q.F. Stout and J. Hardwick, Parallel programs for adaptive designs, Handbook of Parallel Computing and Statistics, E. Kontoghiorghes, ed., Marcel Dekker, 2006, pp. 347-373.
Keywords: multi-arm bandit models, dynamic programming, clinical trial, delayed response, response adaptive sampling, parallelizing recursive equations, sequential analysis. abstract paper.pdf
T. Gombosi, D.L. DeZeeuw, K.G. Powell, A.J. Ridley, I.V. Sokolov, Q.F. Stout, and G.T. Toth, Adaptive mesh refinement MHD for global space weather simulations, Space Plasma Simulation, J. Buchner, C.T. Dum, M. Scholer, eds., Lecture Notes in Physics 615, Springer-Verlag, 2003, pp. 251-279.
Keywords: solution adaptive mesh refinement, AMR, MHD, space environment modeling, adaptive grid. abstract paper.pdf
J. Hardwick, R. Oehmke, and Q.F. Stout, Optimal adaptive designs for delayed response models: exponential case, MODA6: Model Oriented Data Analysis, A. Atkinson, P. Hackl, W. Mueller, eds., Physica Verlag, 2001, pp. 127-134.
Keywords: delayed response, sequential analysis, dynamic programming, computational learning theory, bandit models, parallel computing, response adaptive sampling, clinical trial, design of experiments, clinical trial. abstract paper.ps paper.pdf
R. Miller and Q.F. Stout, Algorithmic techniques for networks of processors, in CRC Handbook of Algorithms and Theory of Computation, M. Atallah, ed., CRC Press, 1999, pp. 46:1-46:19.
Keywords: algorithmic paradigms, divide-and-conquer, pipelining, master-slave, mapping problem, weak embeddings, mesh computer, pyramid, hypercube, PRAM, distributed memory, shared memory. abstract paper.ps paper.pdf
S. Colley, J.P. Hayes, T.N. Mudge, J. Palmer, and Q.F. Stout, A microprocessor-based hypercube supercomputer, in Multi-Microprocessors, A. Gupta, ed., IEEE Press, 1987, pp. 250-260. Reprint of article first appearing in IEEE Micro 6 (1986), pp. 6-17. This article won the IEEE Micro ``Best Article Award'' for 1986.
Keywords: hypercube computer, supercomputing, store-and-forward message passing, I/O systems, medium-grain parallel computer, software.
Q.F. Stout, Pyramid algorithms optimal for the worst case, in Parallel Computer Vision, L. Uhr, ed., Academic Press, 1987, pp. 147-168.
Keywords: mesh local, perimeter bound, strongly global, image processing, communication lower bounds, component labeling, data squares, data movement operations, data square pyramid computer, parallel computing.
Q.F. Stout, Hypercubes and pyramids, in Pyramidal Systems for Computer Vision, V. Cantoni and S. Levialdi, eds., NATO ASI Series ARW Vol. F 25, Springer-Verlag, 1986, pp. 75-89.
Keywords: hypercube computers, pyramid, stepwise simulation, embeddings, image processing, hyper-pyramid, pyramid algorithms.
Q.F. Stout, An algorithmic comparison of meshes and pyramids, in Evaluation of Multicomputers for Image Processing, L. Uhr, K. Preston, S. Levialdi, and M.J.B. Duff, eds., Academic Press, 1986, pp. 107-121.
Keywords: parallel computer, mesh, pyramid, image algorithms, convexity, component labeling, divide-and-conquer.

Journals and Conference Proceedings

J. Lipman and Q.F. Stout, A performance analysis of local synchronization, Symp. Parallelism in Algorithms and Architectures (SPAA) 2006.
Keywords: synchronization delay, overhead, performance analysis, barrier, performance analysis, geometric distribution, heavy-tailed distribution, stochastic task times, idle time. abstract paper.pdf
Q.F. Stout, Algorithms minimizing peak energy on mesh-connected systems, preliminary results in Symp. Parallelism in Algorithms and Architectures (SPAA) 2006.
Keywords: peak power consumption, energy, rat algorithm, image processing, graph algorithm, mesh. abstract paper.pdf
The talk Space, Time, Power: Evolving Concerns for Parallel Algorithms mentions some of these results.
C. Jablonowski, M. Herzog, J. Penner, R. Oehmke, Q.F. Stout, B. van Leer, K.G. Powell, Block-structured adaptive grids on the sphere: advection experiments, Monthly Weather Review 134 (2006), 3691-3713.
Keywords: adaptive mesh refinement, AMR, atmospheric modeling, spherical adaptive grid, adaptive block. abstract paper.pdf
J. Hardwick, R. Oehmke, Q.F. Stout, New adaptive designs for delayed responses, Journal of Statistical Planning and Inference 136 (2006), pp, 1940-1955.
Keywords: hyperopic design, bandit models, randomized play-the-winner, response adaptive sampling. abstract paper.pdf
J.E. Penner, M. Herzog, C. Jablonowski, B. van Leer, R.C. Oehmke, Q.F. Stout, K.G. Powell, ``Development of an atmospheric climate model with self-adapting grid and physics'', J. Physics Conf. Series 16 (2005), pp. 353-357.
Keywords: adaptive mesh refinement, AMR, atmospheric modeling, spherical adaptive grid, adaptive block. abstract paper.pdf
G. Toth, I.V. Sokolov, T.I. Gombosi, D.R. Chesney, C.R. Clauer, D.L. De Zeeuw, K.C. Jansen, K.J. Kane, W.B. Manchester, K.G. Powell, A.J. Ridley, I.I. Roussev, Q.F. Stout, O. Volberg, ``Space Weather Modeling Framework: a new tool for the space science community" (2005), J. Geophysical Research 110, A12226, doi:10.1029/2005JA011126.
Keywords: scientific computing framework, high performance computing, space environment modeling, grid coupling, SWMF. abstract paper.pdf
C. Jablonowski, M. Herzog, J.E. Penner, R.C. Oehmke, Q.F. Stout, B. van Leer, ``Adaptive grids for weather and climate models'', ECMWF Proc. Recent Developments in Numerical Methods for Atmospheric and Climate Modeling (2004), pp. 233-250.
Keywords: climate modeling, weather, solution adaptive mesh refinement, AMR, spherical adaptive grid, adaptive block. abstract paper.pdf
G. Toth, O. Volberg, A.J. Ridley, T.I. Gombosi, D. DeZeeuw, K.C. Hanson, D.R. Chesney, Q.F. Stout, K.G. Powell, K. Kane, R. Oehmke, ``A physics-based software framework for Sun-Earth connection modeling'', Multiscale Coupling of Sun-Earth Processes, Proc. Conf. on the Sun-Earth Connection, Kona, Hawaii, 2004, A. T. Y. Lui, Y. Kamide, and G. Consolini, eds., Elsevier, pp. 383-397.
Keywords: parallel computing, high-performance computing, software engineering, space environment modeling, coupling. abstract paper.pdf
T.I. Gombosi, K.G. Powell, D.I. De Zeeuw, C.R. Clauer, K.C. Hansen, W.B. Manchester, A.J. Ridley, I.I. Roussev, I.V. Sokolov, Q.F. Stout, G. Toth, ``Solution adaptive MHD for space plasmas: Sun-to-Earth simulations'', Computers in Science and Engineering 6 (2004), pp. 14-35.
Keywords: adaptive mesh refinement, parallel computing, geoscience. abstract paper.pdf
T. Gombosi, G. Toth, D. de Zeeuw, K.G. Powell, Q.F. Stout, ``Adaptive mesh refinement MHD for global simulations'', Proc. ISSS-6 (2001), 8 p.
Keywords: solution adaptive mesh refinement, AMR, space plasma simulations. abstract paper.pdf
R. Oehmke and Q.F. Stout, ``Parallel adaptive blocks on the sphere'', Proc. 10th SIAM Conf. Parallel Processing for Scientific Computing (2001).
Keywords: adaptive mesh refinement, AMR, data structure, parallel computing, geoscience, multi-scale modeling, spherical adaptive grid, geometric decomposition, high performance computing. abstract paper.ps paper.pdf
D.L. De Zeeuw, T.I. Gombosi, C.P.T. Groth, K.G. Powell, Q.F. Stout, ``An adaptive MHD method for global space weather simulations'', IEEE Trans. Plasma Science 28 (2000), pp. 1956-1965.
Keywords: space weather, adaptive mesh refinement, MHD, supercomputing, Sun-Earth, space physics, scientific computing. abstract paper.pdf
C.R. Clauer, T.I. Gombosi, D.L. De Zeeuw, J.J. Ridley, K.G. Powell, B. van Leer, Q F. Stout, C.P.T. Groth, T.E. Holzer, ``High performance computer methods applied to predictive space weather simulations'', IEEE Trans. Plasma Science 28 (2000), pp. 1931-1937.
Keywords: space weather, adaptive mesh refinement, MHD, supercomputing, Sun-Earth, space physics, scientific computing. abstract paper.pdf
R. Oehmke, J. Hardwick, and Q.F. Stout, ``Scalable algorithms for adaptive statistical designs'', Proceedings SC 2000 (Supercomputing), 16 p. Reprinted in Scientific Programming 8 (2001), pp. 183-193.
Keywords: dynamic programming, computational learning theory, bandit models, dynamic domain decomposition, memory-intensive computing, response adaptive sampling, message-passing, load balancing, sequential analysis, performance analysis, experimental algorithms, recursive equations, design of experiments, MPI, IBM SP, OpenMP, SGI Origin. abstract paper.ps paper.pdf
J. Hardwick, R. Oehmke, and Q.F. Stout, ``A program for sequential allocation of three Bernoulli populations'', Computational Statistics and Data Analysis 31 (1999), pp. 397-416.
Keywords: bandit models, dynamic programming, response adaptive sampling, sequential sampling, clinical trial, high-performance computing, load balancing, recursive equations. abstract paper.ps paper.pdf
A.A. Poe and Q.F. Stout, ``Load balancing 2-phased geometrically based problems'', Proc. 9th SIAM Conf. Parallel Processing for Scientific Computing (1999).
Keywords: multi-weight load balancing, graph partitioning, ham sandwich theorem, geometric decomposition, impact analysis, crash simulation, domain decomposition, discrete computational geometry, multiple constraints. abstract paper.ps paper.pdf
T. Tabe and Q.F. Stout, ``The use of the MPI communication library in the NAS Parallel Benchmarks'', submitted.
Keywords: message passing, trace analysis, performance evaluation, scientific computing, distributed memory, communication kernals. abstract paper.ps paper.pdf
Q.F. Stout, D.L. deZeeuw, T.I. Gombossi, C.P.T. Groth, H.G. Marshall, and K.G. Powell, ``Adaptive parallel computation of a grand-challenge problem: Prediction of the path of a solar-corona mass ejection'', Proc. SC98.
Keywords: magnetohydrodynamics (MHD), space weather prediction, adaptive mesh refinement, Cartesian, adaptive block, Riemann solver, upwind schemes, scientific computing. abstract paper.html paper.ps paper.pdf
M. Livingston and Q.F. Stout, ``Shift-product networks'', Mathematical and Computational Modeling, 1998, to appear.
Keywords: interconnection networks, scalable networks, shuffle-exchange networks, Cayley graphs, product graphs, de Bruijn network, commodity components. abstract paper.ps paper.pdf
P.D. MacKenzie and Q.F. Stout, ``Ultra-fast expected time parallel algorithms'', J. Algorithms 26 (1998), pp. 1-33.
Keywords: ultrafast, padded sort, geometry algorithms, CRCW PRAM, Voronoi diagram, all nearest neighbors, closest pair, relative neighborhood graph, Delaunay triangulation, largest empty circle, lower bounds, randomized algorithm. abstract paper.ps paper.pdf
Q.F. Stout, D.L. deZeeuw, T.I. Gombossi, C.P.T. Groth, H. Marshall, K.G. Powell, ``Adaptive blocks: A high-performance data structure'', Proc. SC97.
Keywords: adaptive data structure, Cartesian, cache, high performance computing, mesh, refinement, oct-tree, scientific computing. abstract paper.html paper.ps paper.pdf
T. Gombossi, K.G. Powell, Q.F. Stout, et al., ``Multiscale modeling of heliospheric plasmas'', High Performance Computing 1997, pp. 46-51.
Keywords: magnetohydrodynamics, MHD, adaptive mesh refinement (AMR), Riemann solver, Cray T3D, solar wind, high-performance computing, HPCC, NASA Grand Challenge Investigator Team, upwind scheme, space plasma, scientific computing. abstract paper.ps paper.pdf
D. Van Wieren and Q.F. Stout, ``Random graph algorithms for the mesh with row and column subbuses'', Proc. 2nd Work. on Reconfigurable Architectures (1995), pp. 1-13.
Keywords: ultrafast algorithms, reconfigurable mesh, rmesh, MasPar, edge cover, Hamiltonian cycle, spanning trees, randomized algorithm.
T. Tabe, J. Hardwick and Q.F. Stout, ``Statistical analysis of communication on the IBM SP2'', Computing Science and Statistics 27 (1995), pp. 347-351.
Keywords: all-to-all communication, resampling, performance evaluation, message passing, operating systems, interrupts, heavy tails, benchmarking. abstract paper.ps paper.pdf
R. Miller, V.K. Prasanna Kumar, D. Reisis and Q.F. Stout, ``Parallel computations on reconfigurable meshes'', IEEE Trans. on Computers 42 (1993), pp. 678-692.
Keywords: reconfigurable mesh, image algorithms, graph algorithms, parallel algorithms, VLSI, mesh, PRAM, mesh-of-trees, pyramid computer, component labeling, global or, prefix calculation, parity, xor. abstract paper.pdf
P.D. MacKenzie and Q.F. Stout, ``Optimal parallel construction of Hamiltonian cycles and spanning trees in random graphs'', Proc. 5th ACM Symp. Parallel Algorithms and Architectures (1993), pp. 224-229.
Keywords: ultrafast algorithms, CRCW PRAM, edge cover, lower bounds, parallel target shooting, randomized algorithm. abstract paper.ps paper.pdf
E. Cohen, R. Miller, E.M. Sarraf and Q.F. Stout, ``Efficient convexity and domination algorithms for fine- and medium-grain hypercube computers'', Algorithmica 7 (1992), pp. 51-75.
Keywords: convex hull, domination, sorting, hypercube algorithms, computational geometry, worst-case, expected case. abstract
Q.F. Stout, ``Ultrafast parallel algorithms and reconfigurable meshes'', Proc. DARPA Software Technology Conference (1992), pp. 184-188.
Keywords: pram, rmesh, randomization, lower bounds, padded sort, graph theory, image processing. abstract paper.ps paper.pdf
H. Li and Q.F. Stout, ``Reconfigurable SIMD parallel processors'', Proc. of the IEEE 79 (1991), pp. 429-443.
Keywords: reconfigurable mesh, rmesh, connected components, image processing, fault tolerance, ultrafast algorithm. abstract paper.pdf
M.L. Livingston and Q.F. Stout, ``Fault tolerance of the cyclic buddy subcube location scheme in hypercubes'', Proc. 6th Distributed Memory Computing Conf. (1991), IEEE, pp. 34-41.
Keywords: fault tolerance, subcube location, subcube allocation, hypercube computer, buddy system, gray-coding, folded hypercube, projective hypercube. abstract paper.ps paper.pdf
R. Miller and Q.F. Stout, ``Computing convexity properties of images on a pyramid computer'', Algorithmica 6 (1991), pp. 658-684.
Keywords: Pyramid computer, convexity, digitized pictures, digital geometry, image processing, parallel computing, parallel algorithms, data movement operations, bandwidth limitations, lower bounds. abstract
P.D. MacKenzie and Q.F. Stout, ``Asymptotically efficient hypercube algorithms for computational geometry (preliminary version)'', Proc. 3rd Symp. Frontiers Massively Parallel Computation, (1990), pp. 8-11.
Keywords: divide-and-conquer, hypercube sorting, domination, nearest neighbors, Voronoi diagram. abstract
P.D. MacKenzie and Q.F. Stout, ``Practical hypercube algorithms for computational geometry (preliminary version)'', Proc. 3rd Symp. Frontiers Massively Parallel Computation, (1990), pp. 75-80.
Keywords: divide-and-conquer, bitonic sort, domination, nearest neighbors, iso-oriented intersections, visibility, cross-stitching. abstract
Q.F. Stout and B. Wagar, ``Intensive hypercube communication: Prearranged communication in link-bound machines'', J. of Parallel and Distributed Computing 10 (1990), pp. 167-181.
Keywords: hypercube computer, n-cube, parallel communication, all-to-all communication, personalized communication, broadcasting, routing, permutations, matrix transpose, histogramming. abstract paper.ps paper.pdf
R. Miller and Q.F. Stout, ``Seymour: a portable parallel programming language'', Structured Programming 11 (1990), pp. 157-171.
Keywords: parallel programming paradigms, global data movement operations, portable parallel programs, efficiency. abstract
R. Miller and Q.F. Stout, ``Mesh computer algorithms for computational geometry'', IEEE Trans. on Computers C-38 (1989), pp. 321-340.
Keywords: parallel algorithms, mesh computer, computational geometry, planar point data, convexity, proximity, area, intersection. abstract paper.pdf
M.L. Livingston and Q.F. Stout, ``Parallel allocation algorithms for hypercubes and meshes'', Proc. 4th Conf. on Hypercubes, Concurrent Computers, and Applications (1989), pp. 59-66.
Keywords: subcube allocation, buddy system, cyclic buddy system, submesh allocation, torus. abstract paper.ps paper.pdf
R. Fenrich, R. Miller and Q.F. Stout, ``Hypercube algorithms for some NP-hard packing problems'', Proc. 4th Conf. on Hypercubes, Concurrent Computers, and Applications (1989), pp. 769-776.
Keywords: 2-dimensional bin packing, best fit, NP-hard, parallel computing, hypercube computer, level algorithms. abstract
R. Miller and Q.F. Stout, ``Optimal hypercube algorithms for labeled images'', Algorithms and Data Structures: Proc. WADS '89, Springer-Verlag Lec. Notes in Comp. Sci. 382 (1989), pp. 517-528.
Keywords: Parallel algorithms, hypercube computer, convexity, area, perimeter, diameter, smallest enclosing rectangle, image analysis, divide-and-conquer. abstract
M.L. Livingston and Q.F. Stout, ``Distributing resources in hypercube computers'', Proc. 3rd Conf. on Hypercube Concurrent Computers and Applications (1988), ACM, pp. 222-231.
Keywords: hypercube, subcube fault-tolerance, codes, buddy allocation, disk placement, parallel computing. abstract paper.ps paper.pdf
J. Gordon and Q.F. Stout, ``Hypercube message routing in the presence of faults'', Proc. 3rd Conf. on Hypercube Concurrent Computers and Applications (1988), ACM, pp. 318-327.
Keywords: hypercube computer, fault tolerance, randomized routing, random graph, communication link, processor. abstract paper.pdf
Q.F. Stout, ``Mapping vision algorithms to parallel architectures'', Proc. of the IEEE 76 (1988), pp. 982-995.
Keywords; simulation, parallel algorithms, mesh, pyramid, hypercube, mesh-of-trees, PRAM, shared memory, lower bounds, data movement operations, computational geometry, image processing, graph algorithms. abstract paper.pdf
Q.F. Stout, ``Constant-time geometry on PRAMs'', Proc. 1988 Int'l. Conf. on Parallel Processing, vol. III, IEEE, pp. 104-107.
abstract
D.A. Buell et al., ``Parallel algorithms and architectures: Report of a workshop'', J. Supercomputing 1 (1988), pp. 301-325.
R. Miller and Q.F. Stout, ``Efficient parallel convex hull algorithms'', IEEE Trans. Computers C-37 (1988), pp. 1605-1618.
Keywords: AKS network, computational geometry, convex hull, EREW PRAM, hypercube, mesh, mesh-of-trees, reconfigurable mesh, pyramid, parallel algorithms, divide-and-conquer. abstract paper.pdf
R. Miller and Q.F. Stout, ``Simulating essential pyramids'', IEEE Trans. Computers C-37 (1988), pp. 1642-1648.
Keywords: pyramid computer, image processing, hypercube, rmesh, mesh computer, mesh-of-trees. abstract paper.pdf
R. Miller and Q.F. Stout, ``Portable parallel algorithms for geometric problems'', Proc. 2nd Symp. Frontiers of Massively Parallel Computation (1988), pp. 195-198.
Keywords: portable parallel algorithms, computational geometry, data movement operations, distributed memory parallel computers. abstract paper.ps paper.pdf
M.L. Livingston and Q.F. Stout, ``Fault tolerance of allocation schemes in massively parallel computers'', Proc. 2nd Symp. Frontiers of Massively Parallel Computation (1988), pp. 491-494.
Keywords: fault tolerance, allocation, hypercube computer, mesh, torus, buddy system. abstract paper.ps paper.pdf
R. Miller and Q.F. Stout, ``Data movement techniques for the pyramid computer'', SIAM J. on Computing 16 (1987), pp. 38-60.
Keywords: pyramid computer, graph algorithms, image processing, component labeling, mesh computer, data movement operations.
abstract
Q.F. Stout, ``Supporting divide-and-conquer algorithms for image processing'', J. of Parallel and Distributed Computing 4 (1987), pp. 95-115.
Keywords: regular architectures, parallel algorithms, languages, bandwidth limitations, distributed memory, hypercube, mesh, pyramid, PRAM, shared memory, fine-grain, medium-grain, parallel programming paradigms. abstract paper.pdf
Q.F. Stout, ``Meshes with multiple buses'', Proc. 27th IEEE Symp. on Foundations of Computer Science (1986), pp. 264-273.
Keywords: broadcasting, mesh computer, cooperative problem solving, cooperative speedup, optimal stepwise simulation, or, minimum, component labeling, spanning forest, tree, pyramid, mesh-of-trees, layouts. abstract
R. Miller and Q.F. Stout, ``Geometric algorithms for digitized pictures on a mesh-connected computer'', IEEE Trans. on Pattern Analysis and Machine Intelligence 7 (1985), pp. 216-228.
Keywords: mesh computer, computational geometry, convexity, digitized images, digital geometry, minimal paths, nearest neighbors, diameter, farthest points, divide-and-conquer. abstract
Q.F. Stout, ``Mesh and pyramid computers inspired by geometric algorithms'', Proc. Work. on Algorithm-Guided Parallel Architectures for Automatic Target Recognition (1985), pp. 293-315.
Q.F. Stout, ``Pyramid computer solutions of the closest pair problem'', J. of Algorithms 6 (1985), pp. 200-212.
Keywords: pyramid cellular automata, self-organizing, pyramid computers, closest pair, computational geometry, nearest neighbors, parallel algorithms, finite automaton. abstract paper.pdf
Q.F. Stout, ``Tree-based graph algorithms for some parallel computers'', Proc. 1985 Int'l. Conf. on Parallel Processing, IEEE, pp. 727-730.
Keywords: parallel graph algorithms, component labeling, unordered edge input, spanning forest, descendant functions, ancestor functions, preorder, postorder. abstract paper.ps paper.pdf
R. Miller and Q.F. Stout, ``Varying diameter and problem size in mesh-connected computers'', Proc. 1985 Int'l. Conf. on Parallel Processing, IEEE, pp. 697-699.
Keywords: mesh computer, semigroup operations, component labeling, image algorithms, convex hull, minimal spanning forest, communication bounds. abstract paper.ps paper.pdf
Q.F. Stout, ``Topological matching'', Proc. 15th ACM Symp. on Theory of Computing (1983), pp. 24-31.
Keywords: image processing, deformation, self-organizing cellular automata (array), clerks, mesh computer, tree isomorphism. abstract paper.pdf
Q.F. Stout, ``Sorting, merging, selecting, and filtering on tree and pyramid machines'', Proc. 1983 Int'l. Conf. on Parallel Processing, IEEE, pp. 214-221.
Keywords: pyramid computer, x-tree, tree computer, sorting, merging, selection, median filtering, image processing. abstract
Q.F. Stout, ``Mesh-connected computers with broadcasting'', IEEE Trans. on Computers C-32 (1983), pp. 826-830.
Keywords: bus, broadcasting, mesh computer, median, selection, semigroup computation, sorting, communication lower bounds. abstract paper.pdf
Q.F. Stout, ``Drawing straight lines with a pyramid cellular automaton'', Information Processing Letters 15 (1982), pp. 233-237.
Keywords: self-organizing finite state automata, pyramid computer, digital line, clerks, parallel algorithms. abstract paper.pdf
Q.F. Stout, ``Broadcasting in mesh-connected computers'', Proc. 1982 Conf. Information Sciences and Systems, pp. 85-90.
Keywords: image algorithms, geometry, 2-dimensional, semigroup operations. abstract paper.pdf
Q.F. Stout, ``Using clerks in parallel processing'', Proc. 23rd IEEE Symp. on Foundations of Computer Science (1982), pp. 272-279.
Keywords: self-organizing cellular array, pyramid cellular automata, finite automata, mesh computer, pyramid computer, connected components, image processing, digital circle, clerks, simulation abstract paper.pdf

Overview of Research in Parallel Computing.

Adaptive Sampling, Statistics

For the papers in this section, there is a collection of keywords that could be applied to many of them, and hence they will be listed here but not with each individual paper. Unfortunately, different areas tend to use different terminology for the same concepts, and adaptive designs is an approach of wide utility. Some relevant key phrases are:

statistical computing, sequential allocation, response adaptive sampling, adaptive design, design of experiments, dynamic programming, backward induction, stochastic optimization, machine learning, computational learning theory, Bayesian design, dynamical systems, dynamic index, bandit models.

Book Chapters

Q.F. Stout and J. Hardwick, Parallel programs for adaptive designs, Handbook of Parallel Computing and Statistics, E. Kontoghiorghes, ed., Marcel Dekker, 2006, pp. 347-373.
Keywords: multi-arm bandit models, dynamic programming, speedup, clinical trial, delayed response, response adaptive sampling, parallelizing recursive equations, sequential analysis. abstract paper.pdf
J. Hardwick, R. Oehmke, and Q.F. Stout, Optimal adaptive designs for delayed response models: exponential case, MODA6: Model Oriented Data Analysis, A. Atkinson, P. Hackl, W. Mueller, eds., Physica Verlag, 2001, pp. 127-134.
Keywords: delayed response, sequential analysis, dynamic programming, computational learning theory, multi-arm bandit models, parallel computing, clinical trial, recursive equations, design of experiments, medical ethics, clinical trial, backward induction. abstract paper.ps paper.pdf
J. Hardwick and Q.F. Stout, Optimizing a unimodal response function for binary variables, in Optimum Design 2000, A. Atkinson, B. Bogacka, and A. Zhigljavsky, eds., Kluwer, 2001, pp. 195-208.
Keywords: nonparametric, shape-constrained, competing failure modes, unimodal regression, phase I/II, bandit, approximate Gittins index, stochastic approximation, Polya urn, up and down, Markov chain, random walk. abstract paper.ps paper.pdf
J. Hardwick and Q.F. Stout, Flexible algorithms for creating and analyzing adaptive sampling procedures, in New Developments and Applications in Experimental Design, N. Flournoy, W.F. Rosenberger, and W.K. Wong, eds., Institute of Math. Stat. Lecture Notes -- Monograph Series, vol. 34, 1998, pp. 91-105.
Keywords: bandit problems, algorithms, high-performance computing, staged procedure, group sampling, clinical trial, switching, robustness, path induction, parallel computing. abstract paper.ps paper.pdf
J. Hardwick and Q.F. Stout, Exact computational analyses for adaptive designs, in Adaptive Designs, N. Flournoy and W.F. Rosenberger, eds., Institute of Math. Stat. Lecture Notes Monograph Series Vol. 25, 1995, pp. 223-237.
Keywords: constrained dynamic programming, forward induction, path induction, backward induction, multiple criteria, ethical clinical trials, bandit problems, clinical trial. abstract paper.ps paper.pdf

Journals and Conferences

J. Hardwick and Q.F. Stout, Response adaptive designs for balancing complex objectives, submitted.
Keywords: controlled clinical trial, Gittins index, multiple objectives, dynamic programming, bandit problem, optimal tradeoff, multiple objectives, modified bandit design abstract paper.pdf
J. Hardwick and Q.F. Stout, Response adaptive designs that incorporate switching costs and constraints, Journal of Statistical Planning and Inference 137 (2007), 2654-2665.
Keywords: switching costs, constraints, hyperopic procedure, bandit problem, nonlinear Bayes risk, dynamic programming abstract paper.pdf
J. Hardwick, R. Oehmke, Q.F. Stout, New adaptive designs for delayed response models, Journal of Statistical Planning and Inference 136 (2006), pp. 940-1955.
Keywords: randomized play-the-winner, hyperopic design, bandit problem. abstract paper.pdf
Q.F. Stout and J. Hardwick, Optimal screening designs with flexible cost and constraint structures, Journal of Statistical Planning and Inference 132 (2005), pp. 149-162.
Keywords: drug testing, acceptance-rejection sampling, staged procedure, stopping rule, dynamic programming, design of experiments, decision theory, backward induction. abstract paper.pdf
J. Hardwick, M.C. Meyer, and Q.F. Stout, Directed walk designs for dose response problems with competing failure modes, Biometrics 59 (2003), pp. 229-236.
Keywords: adaptive sampling, phase I/II clinical trial, sequential allocation, random walk, shape-constrained regression, parametric, nonparamentric, Bayesian, frequentists, smooothed, curve estimation, design of experiments, toxic. abstract paper.ps paper.pdf
J. Hardwick and Q.F. Stout, Optimal few-stage designs, Journal Statistical Planning and Inference 104 (2002), pp. 121-145.
Keywords: two-stage, three-stage, clinical trial, medical ethics, group allocation, staged procedure, design of experiments, selection, estimation, bandit problems, product of means. abstract paper.ps paper.pdf
R. Oehmke, J. Hardwick, and Q.F. Stout, Scalable algorithms for adaptive statistical designs, Proc. SC 2000 (Supercomputing), 16 p. Reprinted in Scientific Programming 8 (2001), pp. 183-193.
Keywords: dynamic programming, computational learning theory, multi-arm bandit models, message-passing, dynamic domain decomposition, memory-intensive computing, load balancing, sequential analysis, performance analysis, experimental algorithms, parallel computing, clinical trial, recursive equations, design of experiments, medical ethics, clinical trial, delayed response, backward induction, MPI, OpenMP. abstract paper.ps paper.pdf
Q.F. Stout, Optimal algorithms for unimodal regression, Computing Science and Statistics 32 (2000), 8 p.
Keywords: nonparametric, shape-constrained, isotonic or monotonic regression, scan, parallel prefix, umbrella ordering, L_p regression, least squares, pool adjacent violators (PAV), median regression, mergeable heaps, persistent data structure. abstract paper.ps paper.pdf
J. Hardwick and Q.F. Stout, Using path induction to evaluate sequential allocation procedures, SIAM J. Scientific Computing 21 (1999), pp. 67-87.
Keywords: backward induction, forward induction, staged allocation, group sampling, sequential, path counting, Bayesian, bandit problems. abstract paper.ps paper.pdf
J. Hardwick, R. Oehmke, and Q.F. Stout, A program for sequential allocation of three Bernoulli populations, Computational Statistics and Data Analysis 31 (1999), pp. 397-416.
Keywords: parallel computing, clinical trial, high-performance computing, load balancing, recursive equations, design of experiments, medical ethics, clinical trial. abstract paper.ps paper.pdf
J. Hardwick, C. Page and Q.F. Stout, Sequentially deciding between two experiments for estimating a common success probability, J. Amer. Statistical Assoc. 93 (1998), pp. 1502-1511.
Keywords: batch testing, risk assessment, infection rate, grouped data, composite testing, pooled data, omniscient allocation. abstract paper.ps paper.pdf
J. Hardwick, R. Oehmke, and Q.F. Stout, Adaptive allocation in the presence of missing outcomes, Computing Science and Statistics 30 (1998), pp. 219-223.
Keywords: censored observations, bandit, clinical trial, dynamic programming. abstract paper.ps paper.pdf
J. Landrum, J. Hardwick, and Q.F. Stout, Predicting algorithm performance, Computing Science and Statistics 30 (1998), pp. 309-314.
Keywords: computer performance prediction, adaptive sampling, change-point, experimental algorithms, regression, extrapolation, design of experiments, benchmarking. abstract paper.ps paper.pdf
J. Hardwick and Q.F. Stout, Optimal allocation for estimating the mean of a bivariate polynomial, Sequential Analysis 15 (1996), pp. 71-90.
Keywords: nonlinear estimation, robustness, myopic, hyperopic, product, Bayesian, fault tolerance. abstract paper.ps with color figures paper.ps with grayscale figures paper.pdf with color figures paper.pdf with grayscale figures
Here is a web version of a hour-long Talk that overviews all of this material and more.
J. Hardwick and Q.F. Stout, Sequential allocation with minimal switching, Computing Science and Statistics 28 (1996), pp. 567-572.
Keywords: switching costs, constraints, bandit, estimation, dynamic programming, optimal tradeoffs, backward induction. abstract paper.ps paper.pdf
J. Hardwick and Q.F. Stout, Optimal adaptive equal allocation rules, Computing Science and Statistics 24 (1992), pp. 597-601.
Keywords: curtailment, probability of correct selection, equal allocation, vector at a time, clinical trial. abstract paper.ps paper.pdf
J. Hardwick and Q.F. Stout, Bandit strategies for ethical sequential allocation, Computing Science and Statistics 23 (1991), pp. 421-424.
Keywords: medical ethics, Gittins index, power, probability of correct selection, indifference region, adaptive clinical trial. abstract paper.ps paper.pdf

Overview of Research in Adaptive Designs.

Space and Earth Modeling

Most of my work in this area involves the Center for Space Environment Modeling (CSEM). Further, almost all of it involves parallel computing and adaptive mesh refinement.

Widget

We didn't create this, and I don't know who did, but a widget that shows images of the heliosphere's magnetic field generated by our programs appears in www.apple.com/downloads/dashboard/information/ccmcspaceweatherwidget.html

Chapters in Books

T. Gombosi, D.L. DeZeeuw, K.G. Powell, A.J. Ridley, I.V. Sokolov, Q.F. Stout, and G.T. Toth, Adaptive mesh refinement MHD for global space weather simulations, Space Plasma Simulation, J. Buchner, C.T. Dum, M. Scholer, eds., Lecture Notes in Physics 615, Springer-Verlag, 2003, pp. 251-279.
Keywords: solution adaptive mesh refinement, AMR, MHD, space environment modeling, Cartesian adaptive grid, adaptive block. abstract paper.pdf

Journals and Conference Proceedings

C. Jablonowski, M. Herzog, J. Penner, R. Oehmke, Q.F. Stout, B. van Leer, K.G. Powell, Block-structured adaptive grids on the sphere: advection experiments, Monthly Weather Review 134 (2006), 3691-3713.
Keywords: adaptive mesh refinement, AMR, atmospheric modeling, spherical adaptive grid, adaptive block. abstract paper.pdf
J.E. Penner, M. Herzog, C. Jablonowski, B. van Leer, R.C. Oehmke, Q.F. Stout, K.G. Powell, ``Development of an atmospheric climate model with self-adapting grid and physics'', J. Physics Conf. Series 16 (2005), pp. 353-357.
Keywords: adaptive mesh refinement, AMR, atmospheric modeling, spherical adaptive grid, adaptive block. abstract paper.pdf
G. Toth, I.V. Sokolov, T.I. Gombosi, D.R. Chesney, C.R. Clauer, D.L. De Zeeuw, K.C. Jansen, K.J. Kane, W.B. Manchester, K.G. Powell, A.J. Ridley, I.I. Roussev, Q.F. Stout, O. Volberg, ``Space Weather Modeling Framework: a new tool for the space science community" (2005), J. Geophysical Research 110, A12226, doi:10.1029/2005JA011126.
Keywords: scientific computing framework, high performance computing, space environment modeling, grid coupling, SWMF. abstract paper.pdf
C. Jablonowski, M. Herzog, J.E. Penner, R.C. Oehmke, Q.F. Stout, B. van Leer, ``Adaptive grids for weather and climate models'', ECMWF Proc. Recent Developments in Numerical Methods for Atmospheric and Climate Modeling (2004), pp. 233-250.
Keywords: climate modeling, weather, solution adaptive mesh refinement, AMR, spherical adaptive grid, adaptive block. abstract paper.pdf
G. Toth, O. Volberg, A.J. Ridley, T.I. Gombosi, D. DeZeeuw, K.C. Hanson, D.R. Chesney, Q.F. Stout, K.G. Powell, K. Kane, R. Oehmke, ``A physics-based software framework for Sun-Earth connection modeling'', Multiscale Coupling of Sun-Earth Processes, Proc. Conf. on the Sun-Earth Connection, Kona, Hawaii, 2004, A. T. Y. Lui, Y. Kamide, and G. Consolini, eds., Elsevier, pp. 383-397.
Keywords: parallel computing, high-performance computing, software engineering, space environment modeling, coupling. abstract paper.pdf
T.I. Gombosi, K.G. Powell, D.I. De Zeeuw, C.R. Clauer, K.C. Hansen, W.B. Manchester, A.J. Ridley, I.I. Roussev, I.V. Sokolov, Q.F. Stout, G. Toth, ``Solution adaptive MHD for space plasmas: Sun-to-Earth simulations'', Computers in Science and Engineering 6 (2004), pp. 14-35.
Keywords: adaptive mesh refinement, parallel computing, geoscience. abstract paper.pdf
T. Gombosi, G. Toth, D. de Zeeuw, K.G. Powell, Q.F. Stout, ``Adaptive mesh refinement MHD for global simulations'', Proc. ISSS-6 (2001), 8 p.
Keywords: solution adaptive mesh refinement, AMR, space plasma simulations. abstract paper.pdf
R. Oehmke and Q.F. Stout, ``Parallel adaptive blocks on the sphere'', Proc. 10th SIAM Conf. Parallel Processing for Scientific Computing (2001).
Keywords: adaptive mesh refinement, data structure, parallel computing, geoscience, multi-scale modeling, adaptive spherical grid, geometric decomposition, high performance computing. abstract paper.ps paper.pdf
D.L. De Zeeuw, T.I. Gombosi, C.P.T. Groth, K.G. Powell, Q.F. Stout, ``An adaptive MHD method for global space weather simulations'', IEEE Trans. Plasma Science 28 (2000), pp. 1956-1965.
Keywords: space weather, adaptive mesh refinement, MHD, supercomputing, Sun-Earth, space physics, scientific computing. abstract paper.pdf
C.R. Clauer, T.I. Gombosi, D.L. De Zeeuw, J.J. Ridley, K.G. Powell, B. van Leer, Q F. Stout, C.P.T. Groth, T.E. Holzer, ``High performance computer methods applied to predictive space weather simulations'', IEEE Trans. Plasma Science 28 (2000), pp. 1931-1937.
Keywords: space weather, adaptive mesh refinement, MHD, supercomputing, Sun-Earth, space physics, scientific computing. abstract paper.pdf
T.I. Gombossi, D.L. De Zeeuw, C.P.T. Groth, K.G. Powell, Q.F. Stout, ``Multiscale MHD simulation of a coronal mass ejection and its interaction with the magnetosphere-ionosphere system'', J. Atmospheric and Solar-Terrestrial Physics 62 (2000), pp. 1515-1525.
Keywords: space weather, coronal mass ejection, magnetosphere, ionosphere abstract paper.pdf
C.P.T Groth, D.L. deZeeuw, K.G. Powell, T.I. Gombosi, Q.F. Stout, ``A parallel solution-adaptive scheme for ideal magnetohydrodynamics'', Proc. 14th AIAA Conf. Computational Fluid Dynamics (1999), 17p.
Keywords: MHD, approximate Riemann solver, upwind finite-volume abstract paper.pdf
Q.F. Stout, D.L. deZeeuw, T.I. Gombossi, C.P.T. Groth, H.G. Marshall, and K.G. Powell, ``Adaptive parallel computation of a grand-challenge problem: Prediction of the path of a solar-corona mass ejection'', Proc. SC98.
Keywords: magnetohydrodynamics (MHD), space weather prediction, adaptive mesh refinement, Cartesian, adaptive blocks, Riemann solver, upwind schemes, scientific computing. abstract paper.html paper.ps paper.pdf
Q.F. Stout, D.L. deZeeuw, T.I. Gombossi, C.P.T. Groth, H. Marshall, K.G. Powell, ``Adaptive blocks: A high-performance data structure'', Proc. SC97.
Keywords: adaptive data structure, Cartesian, cache, high performance computing, mesh, adaptive mesh refinement, AMR, oct-tree, scientific computing. abstract paper.html paper.ps paper.pdf
T. Gombossi, K.G. Powell, Q.F. Stout, et al., ``Multiscale modeling of heliospheric plasmas'', High Performance Computing 1997, pp. 46-51.
Keywords: magnetohydrodynamics, MHD, adaptive mesh refinement (AMR), Riemann solver, Cray T3D, solar wind, high-performance computing, HPCC, NASA Grand Challenge Investigator Team, upwind scheme, space plasma, scientific computing. abstract paper.ps paper.pdf

Scientific Computing and Computational Science

Essentially all of the publications listed in the Adaptive Designs and Space and Earth Modeling sections involve scientific computing, as do many of the publications listed in the Parallel Computing section. Only papers involving rather general tools, or not included in those sections, are included here.

Books Authored

Q.F Stout and C. Jablonowski, Parallel Computing 101. While not a standard book, the notes for this tutorial are essentially a book overviewing parallel computing and how to develop efficient parallel programs. The tutorial and notes are continually being updated.
Keywords: parallel programming, performance, MPI, OpenMP, Amdahl's law, software engineering, scientific computing, supercomputing, vendors, load balancing, code tuning.

Chapters in Books

Q.F. Stout and J. Hardwick, Parallel programs for adaptive designs, Handbook of Parallel Computing and Statistics, E. Kontoghiorghes, ed., Marcel Dekker, 2006, pp. 347-373.
Keywords: multi-arm bandit models, dynamic programming, speedup, clinical trial, delayed response, response adaptive, parallelizing recursive equations, sequential analysis. abstract paper.pdf

Journals and Conference Proceedings

G. Toth, I.V. Sokolov, T.I. Gombosi, D.R. Chesney, C.R. Clauer, D.L. De Zeeuw, K.C. Jansen, K.J. Kane, W.B. Manchester, K.G. Powell, A.J. Ridley, I.I. Roussev, Q.F. Stout, O. Volberg, Space Weather Modeling Framework: a new tool for the space science community (2005), J. Geophysical Research 110, A12226, doi:10.1029/2005JA011126.
Keywords: scientific computing framework, high performance computing, space environment modeling, grid coupling, SWMF. abstract paper.pdf
R. Oehmke and Q.F. Stout, Parallel adaptive blocks on the sphere, Proc. 10th SIAM Conf. Parallel Processing for Scientific Computing (2001).
Keywords: adaptive mesh refinement, data structure, parallel computing, geoscience, multi-scale modeling, spherical adaptive grid, geometric decomposition, high performance computing. abstract paper.ps paper.pdf
J. Hardwick and Q.F. Stout, Using path induction to evaluate sequential allocation procedures, SIAM J. Scientific Computing 21 (1999), pp. 67-87.
Keywords: backward induction, forward induction, staged allocation, group sampling, sequential, path counting, Bayesian, bandit problems. abstract paper.ps paper.pdf
A.A. Poe and Q.F. Stout, Load balancing 2-phased geometrically based problems, Proc. 9th SIAM Conf. Parallel Processing for Scientific Computing (1999).
Keywords: multi-weight load balancing, graph partitioning, ham sandwich theorem, geometric decomposition, impact analysis, crash simulation, domain decomposition, discrete computational geometry, multiple constraints. abstract paper.ps paper.pdf
J. Landrum, J. Hardwick, and Q.F. Stout, Predicting algorithm performance, Computing Science and Statistics 30 (1998), pp. 309-314.
Keywords: computer performance prediction, adaptive sampling, change-point, experimental algorithms, regression, extrapolation, design of experiments, benchmarking. abstract paper.ps paper.pdf
Q.F. Stout, D.L. deZeeuw, T.I. Gombossi, C.P.T. Groth, H. Marshall, K.G. Powell, Adaptive blocks: A high-performance data structure, Proc. SC97.
Keywords: adaptive data structure, Cartesian, cache, high performance computing, mesh, refinement, oct-tree, scientific computing. abstract paper.html paper.ps paper.pdf

Theoretical Computer Science

Many of my publications could be classified as theoretical computer science, in that they deal with the design and analysis of algorithms, lower bounds, etc. Unfortunately the field known as ``theoretical computer science'' tends to ignore some areas. For example, in parallel computing, algorithms for PRAMS are commonly viewed as being in theoretical computer science, but ones for SIMD hypercubes typically aren't. Here I've collected together those papers that have been, or could have been, presented at conferences such as FOCS, STOC, SODA, SPAA, or which contain substantial relevant content. However, many of those listed in the Parallel Computing, Algorithms and Data Structures, and Discrete Mathematics sections are also in theoretical computer science, more broadly interpreted.

R. Miller and Q.F. Stout, Parallel Algorithms for Regular Architectures: Meshes and Pyramids, MIT Press, 1996.
Keywords: parallel computing, parallel algorithms, mesh computer, VLSI algorithms, pyramid, data movement operations, graph algorithms, image processing, computational geometry, lower bounds, optimal algorithms.
J. Lipman and Q.F. Stout, A performance analysis of local synchronization, Symp. Parallelism in Algorithms and Architectures (SPAA) 2006, pp. 254-260.
Keywords: synchronization delay, overhead, performance analysis, barrier, performance analysis, geometric distribution, heavy-tailed distribution, stochastic task times, idle time abstract paper.pdf
Q.F. Stout, Algorithms minimizing peak energy on mesh-connected systems, preliminary results in Symp. Parallelism in Algorithms and Architectures (SPAA) 2006.
Keywords: peak power consumption, energy, rat algorithm, image processing, graph algorithm, mesh. abstract paper.pdf
A.A. Poe and Q.F. Stout, Load balancing 2-phased geometrically based problems, Proc. 9th SIAM Conf. Parallel Processing for Scientific Computing (1999).
Keywords: multi-weight load balancing, graph partitioning, ham sandwich theorem, geometric decomposition, impact analysis, crash simulation, domain decomposition, discrete computational geometry, multiple constraints. abstract paper.ps paper.pdf
P.D. MacKenzie and Q.F. Stout, Ultra-fast expected time parallel algorithms, J. Algorithms 26 (1998), pp. 1-33.
Keywords: ultrafast, padded sort, geometry algorithms, CRCW PRAM, Voronoi diagram, all nearest neighbors, closest pair, relative neighborhood graph, Delaunay triangulation, largest empty circle, lower bounds, randomized algorithm. abstract paper.ps paper.pdf
D. Van Wieren and Q.F. Stout, ``Random graph algorithms for the mesh with row and column subbuses'', Proc. 2nd Work. on Reconfigurable Architectures (1995), pp. 1-13.
Keywords: ultrafast algorithms, reconfigurable mesh, rmesh, MasPar, edge cover, Hamiltonian cycle, spanning trees, randomized algorithm.
R. Miller, V.K. Prasanna Kumar, D. Reisis and Q.F. Stout, Parallel computations on reconfigurable meshes, IEEE Trans. on Computers 42 (1993), pp. 678-692.
Keywords: reconfigurable mesh, image algorithms, graph algorithms, parallel algorithms, VLSI, mesh, PRAM, mesh-of-trees, pyramid computer, component labeling, global or, prefix calculation, parity, xor. abstract paper.pdf
P.D. MacKenzie and Q.F. Stout, Optimal parallel construction of Hamiltonian cycles and spanning trees in random graphs, Proc. 5th ACM Symp. Parallel Algorithms and Architectures (SPAA) (1993), pp. 224-229.
Keywords: ultrafast algorithms, CRCW PRAM, edge cover, lower bounds, parallel target shooting, randomized algorithm. abstract paper.ps paper.pdf
R. Machlin and Q.F. Stout, The complex behavior of simple machines, in Emergent Computation, S. Forrest, ed., MIT Press, 1991, pp. 85-98. Reprint of paper first appearing in Physica D 42 (1990), pp. 85-98.
Keywords: Turing machines, emergent systems, halting problem, Busy Beaver problem, halting probability, complexity. abstract paper.pdf
R. Miller and Q.F. Stout, Efficient parallel convex hull algorithms, IEEE Trans. Computers C-37 (1988), pp. 1605-1618.
Keywords: AKS network, computational geometry, convex hull, EREW PRAM, hypercube, mesh, mesh-of-trees, reconfigurable mesh, pyramid, parallel algorithms, divide-and-conquer. abstract paper.pdf
Q.F. Stout, Meshes with multiple buses, Proc. 27th IEEE Symp. on Foundations of Computer Science (FOCS) (1986), pp. 264-273.
Keywords: broadcasting, mesh computer, cooperative problem solving, cooperative speedup, optimal stepwise simulation, or, minimum, component labeling, spanning forest, tree, pyramid, mesh-of-trees, layouts. abstract
Q.F. Stout, Pyramid computer solutions of the closest pair problem, J. of Algorithms 6 (1985), pp. 200-212.
Keywords: pyramid cellular automata, pyramid computers, closest pair, computational geometry, nearest neighbors, parallel algorithms, finite automaton. abstract paper.pdf
Q.F. Stout, Topological matching, Proc. 15th ACM Symp. on Theory of Computing (STOC) (1983), pp. 24-31.
Keywords: image processing, deformation, cellular automata (array), clerks, mesh computer, tree isomorphism. abstract paper.pdf
Q.F. Stout, Mesh-connected computers with broadcasting, IEEE Trans. on Computers C-32 (1983), pp. 826-830.
Keywords: bus, broadcasting, mesh computer, median, selection, semigroup computation, sorting, communication lower bounds. abstract paper.pdf
Q.F. Stout, Drawing straight lines with a pyramid cellular automaton, Information Processing Letters 15 (1982), pp. 233-237.
Keywords: self-organizing finite state automata, pyramid computer, digital line, clerks, parallel algorithms. abstract paper.pdf
Q.F. Stout, Using clerks in parallel processing, Proc. 23rd IEEE Symp. on Foundations of Computer Science (FOCS) (1982), pp. 272-279.
Keywords: self-organizing cellular array, pyramid cellular automata, finite automata, mesh computer, pyramid computer, connected components, image processing, digital circle, clerks, emulate, parallel algorithm. abstract paper.pdf
Q.F. Stout, Broadcasting in mesh-connected computers, Proc. 1982 Conf. Information Sciences and Systems, pp. 85-90.
Keywords: image algorithms, geometry, 2-dimensional, semigroup operations. abstract paper.pdf

Serial Algorithms and Data Structures

Most of the publications listed in the Adaptive Design section contain serial algorithms, and most of the publications listed in the Parallel Computing section contain parallel algorithms. The papers on adaptive blocks all concern a parallel data structure for dynamic Cartesian or spherical grids.

Q.F. Stout, Unimodal regression via prefix isotonic regression, submitted.
Keywords: nonparametric, shape-constrained, isotonic or monotonic regression, scan, parallel prefix, umbrella ordering, least squares, pool adjacent violators (PAV), median regression, minimax, persistent data structure. abstract paper.ps paper.pdf
A.A. Poe and Q.F. Stout, Load balancing 2-phased geometrically based problems, Proc. 9th SIAM Conf. Parallel Processing for Scientific Computing (1999).
Keywords: multi-weight load balancing, graph partitioning, ham sandwich theorem, geometric decomposition, impact analysis, crash simulation, domain decomposition, discrete computational geometry, multiple constraints. abstract paper.ps paper.pdf
J. Landrum, J. Hardwick, and Q.F. Stout, Predicting algorithm performance, Computing Science and Statistics 30 (1998), pp. 309-314.
Keywords: computer performance prediction, adaptive sampling, change-point, experimental algorithms, regression, extrapolation, design of experiments, benchmarking. abstract paper.ps paper.pdf
D.M. Pennock and Q.F. Stout, Exploiting a theory of phase transitions in three-satisfiability problems, Proceedings American Association of Artificial Intelligence, 1996, pp. 253-258.
Keywords: satisfiability, 3-SAT, phase transition, constraint satisfaction, pruning, heuristic search, NP-complete, NP-hard, classification. abstract paper.ps paper.pdf
M.L. Livingston and Q.F. Stout, Constant time computation of minimum dominating sets, Congresses Numerantium 105 (1994), pp. 116-128.
Keywords: codes, covering, domination, packing, matching, perfect domination, grid graph, product graph, mesh, torus, dynamic programming, finite state space, resource allocation, regular architecture, algorithms. abstract paper.ps paper.pdf Here are some related open questions and conjectures.
C.A. Shaffer and Q.F. Stout, Linear-time distance transforms for quadtrees, Computer Vision, Graphics, and Image Processing: Image Understanding 54 (1991), pp. 215-223.
Keywords: quadtrees, hierarchical data structures, chessboard distance, medial axis, QMAT, top-down traversal, neighbored traversal. abstract paper.pdf
Q.F. Stout and B.L. Warren, Tree rebalancing in optimal time and space, Commun. of the ACM 29 (1986), pp. 902-908.
Keywords: binary search trees, vines, perfect balance, optimal search, sorting, data structures. abstract paper.pdf
Q.F. Stout and B.L. Warren, Tree algorithms for unbiased coin tossing with a biased coin, Annals of Probability 12 (1984), pp. 212-222.
Keywords: bias, finite distributions, coin, lattice algorithm, tree algorithm, random number generation, multinomial termination. abstract paper.pdf

Overview of Research in Algorithms and Data Structures.

Discrete Mathematics: Graph Theory, Geometry, Combinatorics, Codings, Probability

J. Lipman and Q.F. Stout, ``A performance analysis of local synchronization'', Symp. Parallelism in Algorithms and Architectures (SPAA) 2006.
Keywords: synchronization delay, overhead, performance analysis, barrier, performance analysis, geometric distribution, heavy-tailed distribution, stochastic task times, idle time abstract paper.pdf
D.M. Pennock and Q.F. Stout, ``Exploiting a theory of phase transitions in three-satisfiability problems'', Proceedings American Association of Artificial Intelligence, 1996, pp. 253-258.
Keywords: satisfiability, 3-SAT, phase transition, constraint satisfaction, pruning, heuristic search, NP-complete, NP-hard, classification. abstract paper.ps paper.pdf
J.D. Masters, Q.F. Stout, and D.M. Van Wieren, ``Unique Domination in Cross-Product Graphs'', Congresses Numerantium 118 (1996), pp. 49-71.
Keywords: coverings, product graph, cross-product, dominating set, unique domination, grid graph, perfect dominating set, torus, cube-connected cycles. abstract paper.ps paper.pdf
M.L. Livingston and Q.F. Stout, ``Constant time computation of minimum dominating sets'', Congresses Numerantium 105 (1994), pp. 116-128.
Keywords: codes, covering, domination, packing, matching, perfect domination, grid graph, product graph, mesh, torus, dynamic programming, finite state space, resource allocation, regular architecture, algorithms. abstract paper.ps paper.pdf
Here are some related open questions and conjectures.
N. Graham, F. Harary, M.L. Livingston and Q.F. Stout, ``Subcube fault-tolerance in hypercubes'', Information and Computation 102 (1993), pp. 280-314.
Keywords: hypercube computer, n-cube, fault-tolerance, k-independent sets, partitions, resource allocation. abstract paper.ps paper.pdf
D. Van Wieren, M.L. Livingston and Q.F. Stout, ``Perfect dominating sets on cube-connected cycles'', Congresses Numerantium 97 (1993), pp. 51-70.
Keywords: perfect dominating set, cube-connected cycles, parallel computer, perfect code, vertex-vertex domination, graph theory, interconnection network, resource allocation, regular architecture. abstract paper.ps paper.pdf
M.L. Livingston and Q.F. Stout, ``Perfect dominating sets'', Congressus Numerantium 79 (1990), pp. 187-203.
Keywords: perfect codes, domination, packings, mesh, torus, hypercube, cube-connected cycles, de Bruijn graph, tree, dag, dynamic programming. abstract paper.ps paper.pdf
M.L. Livingston and Q.F. Stout, ``Embeddings in hypercubes'', Mathematical and Computational Modeling 11 (1988), pp. 222-227.
Keywords: hypercube computer, n-cube, embedding, dilation, expansion, cubical, packing, random graphs, critical graphs, parallel computing. abstract paper.ps paper.pdf
M.L. Livingston and Q.F. Stout, ``Distributing resources in hypercube computers'', Proc. 3rd Conf. on Hypercube Concurrent Computers and Applications (1988), ACM, pp. 222-231.
Keywords: hypercube, subcube fault-tolerance, codes, buddy allocation, disk placement, parallel computing. abstract paper.ps paper.pdf
Q.F. Stout and B.L. Warren, ``Tree algorithms for unbiased coin tossing with a biased coin'', Annals of Probability 12 (1984), pp. 212-222.
Keywords: bias, finite distributions, coin, lattice algorithm, tree algorithm, random number generation, multinomial termination. abstract paper.pdf
Q.F. Stout, ``Searching and encoding for infinite ordered sets'', Int'l. J. Computer and Information Sciences 11 (1982), pp. 55-72.
Keywords: unbounded search, binary encodings, prefix codes, search codes, linear order, infinite sets. abstract
Q.F. Stout, ``Improved prefix encodings of the natural numbers'', IEEE Trans. on Information Theory IT-26 (1980), pp. 607-609.
Keywords: unbounded search, binary encoding, prefix codes, septenary code, integers, natural numbers, long strings. abstract paper.pdf
M. Livingston and Q.F. Stout, ``Shift-product networks'', Mathematical and Computational Modeling, 1998, to appear.
Keywords: interconnection networks, scalable networks, shuffle-exchange networks, Cayley graphs, product graphs, de Bruijn network, parallel computer, commodity components. abstract paper.ps paper.pdf
Q.F. Stout, Order types of words over a countable alphabet, in preparation.
Keywords: lexical (lexicographic) ordering, dictionaries, finite words, countable alphabet, order types, total orders, search.
Q.F. Stout, Packings in hypercubes, in preparation.
Keywords: hypercube, graph embedding, packing, cubical, tree, cycle, biconnected components.
Q.F. Stout, Embedding criterion for e-cube routing, in preparation.
Keywords: hypercube computer, graph embedding, e-cube routing, dimension order, link contention.

Operator Theory, Analysis

Q.F. Stout, On Levi's duality between permutations and convergent series, J. London Mathematical Society 34 (1986), pp. 67-80.
Keywords: convergent series, alternating series, absolutely convergent series, permutations, duality, semigroup abstract paper.pdf
Q.F. Stout, The numerical range of a weighted shift, Proc. American Mathematical Society 88 (1983), pp. 495-502.
Keywords: weighted unilateral or bilateral shift, Hilbert space, numerical radius, numerical range, tri-diagonal matrix, circular shift, circularly symmetric functions. abstract paper.pdf
Q.F. Stout, Schur products of operators and the essential numerical range, Trans. American Mathematical Society 264 (1981), pp. 39-47.
Keywords: Schur multiplication, Hadamard multiplication, essential numerical range, matrix representations, Schatten classes, Hilbert space. abstract paper.pdf
Q.F. Stout, Schur multiplication on B(l_p,l_q), J. Operator Theory 5 (1981), pp. 231-243.
Keywords: Schur multiplication, Banach algebra, maximal ideal space, Stone-Cech compactification, operator theory, l_p spaces.

Overview of Research in Operator Theory, Analysis.

Other Research

Q.F. Stout, Behind the scenes of HPCC, in Suggesting Computer Science Agendas for High Performance Computing, U. Vishkin, ed., Assoc. Computing Machinery, 1994, pp. 156-158.
Keywords: HPCC, funding, planning, instrumentation, parallel computing, supercomputing, graphics, professional training and degrees.
Q.F. Stout and P. Woodworth, Relational databases, American Mathematical Monthly 90 (1983), pp. 101-118.
Keywords: relational databases, normal forms, selection, projection, lossless decomposition.

Overview of Other Research.

Teaching-Related Publications

Q.F. Stout and C. Jablonowski, ``Parallel Computing 101'', tutorial notes that are continuously being updated. Here is more information about the tutorial.
G. Bachelis, D.A. James, B.R. Maxim and Q.F. Stout, Bringing algorithms to life: cooperative computing activities using students as processors, School Science and Mathematics 94 (1994), pp. 176-186.
Keywords: parallel algorithms, cooperation, sorting, addition, multiplication, sieving for primes, sorting, efficiency, systolic, pipelining.

Overview of Teaching Precollege Students.