Physical Sciences and Mathematics Commons^™

Parallel H-V Drawings Of Binary Trees, Panagiotis T. Metaxas, Grammati E. Pantziou, Antonis Symvonis

Computer Science Technical Reports

In this paper we present a method to obtain optimal h-v and inclusion drawings in parallel. Based on parallel tree contraction, our method computes optimal (with respect to a class of cost functions of the enclosing rectangle) drawings in $O(\log^2 n)$ parallel time by using a polynomial number of EREW processors. The number of processors reduces substantially when we study minimum area drawings. The method can be extended to compute optimal inclusion layouts in the case where each leaf $l$ of the tree is represented by rectangle $l_x \times l_y$ (the dimensions of which are part of the input). For …

Microphysical Approach To Nonequilibrium Dynamics Of Quantum Fields, Marcelo Gleiser, Rudnei O. Ramos

Dartmouth Scholarship

We examine the nonequilibrium dynamics of a self-interacting λφ4 scalar field theory. Using a real time formulation of finite temperature field theory we derive, up to two loops and O(λ2), the effective equation of motion describing the approach to equilibrium. We present a detailed analysis of the approxi- mations used in order to obtain a Langevin-like equation of motion, in which the noise and dissipation terms associated with quantum fluctuations obey a fluctuation-dissipation relation. We show that, in general, the noise is colored (time-dependent) and multiplicative (couples nonlinearly to the field), even though it is still Gaussian distributed. The noise …

On-Line And Dynamic Shortest Paths Through Graph Decompositions, Hristo N. Djidjev, Grammati E. Pantziou, Christos D. Zaroliagis

Computer Science Technical Reports

We describe algorithms for finding shortest paths and distances in a planar digraph which exploit the particular topology of the input graph. An important feature of our algorithms is that they can work in a dynamic environment, where the cost of any edge can be changed or the edge can be deleted. For outerplanar digraphs, for instance, the data structures can be updated after any such change in only $O(\log n)$ time, where $n$ is the number of vertices of the digraph. We also describe the first parallel algorithms for solving the dynamic version of the shortest path problem. Our …

Parallel Max Cut Approximations, Grammati E. Pantziou, Paul G. Spirakis, Christos D. Zaroliagis

Computer Science Technical Reports

Given a graph with positive integer edge weights one may ask whether there exists an edge cut whose weight is bigger than a given number. This problem is NP-complete. We present here an approximation algorithm in NC which provides tight upper bounds to the proportion of edge cuts whose size is bigger than a given number. Our technique is based on the methods to convert randomized parallel algorithms into deterministic ones introduced by Karp and Wigderson. The basic idea of those methods is to replace an exponentially large sample space by one of polynomial size. In this work, we prove …

Wavelet Localization Of The Radon Transform, Tim Olson, Joe Destefano

Computer Science Technical Reports

In this paper we develop an algorithm which significantly reduces radiation exposure in x-ray tomography, when a local region of the body is to be imaged. The algorithm uses the properties of wavelets to essentially localize the Radon transform. The algorithm differs from previous algorithms for doing local tomography because it recovers an approximation to the original image, not the image modulo the nullspace of the local tomography operator, or the Lambda transform of the image. This is possible because we do not truly invert the interior Radon transform, but rather sample the Radon transform sparsely away from the local …

Pseudostable Bubbles, Marcelo Gleiser

Dartmouth Scholarship

The evolution of spherically symmetric unstable scalar field configura- tions (“bubbles”) is examined for both symmetric (SDWP) and asymmet- ric (ADWP) double-well potentials. Bubbles with initial static energiesE0 ∼< Ecrit, where Ecrit is some critical value, shrink in a time scale deter- mined by their linear dimension, or “radius”. Bubbles with E0 ∼> Ecrit evolve into time-dependent, localized configurations which are very long-lived com- pared to characteristic time-scales in the models examined. The stability of these configurations is investigated and possible applications are briefly discussed.

The Interplay Of Light And The Circadian Clock. Independent Dual Regulation Of Clock-Controlled Gene Ccg-2(Eas), Guiseppina Arpaia, Jennifer J. Loros, Jay C. Dunlap, Giorgio Morelli, Guiseppe Macino

Dartmouth Scholarship

Ambient light is the major agent mediating entrainment of circadian rhythms and is also a major factor influencing development and morphogenesis. We show that in Neurospora crassa the expression of clock-controlled gene 2 (ccg-2), a gene under the control of the circadian clock and allelic to the developmental gene easy wettable (eas), is regulated by light in wild-type strains. Light elicits a direct and important physiological effect on ccg-2(eas) expression as demonstrated using several mutant Neurospora strains. In white collar mutants (wc-1 and wc-2) that are “blind” to blue light, ccg-2(eas) mRNA shows no variation following illumination with saturating light. …

Brittle Compressive Failure Of Salt-Water Columnar Ice Under Biaxial Loading, T. R. Smith, E. M. Schulson

Dartmouth Scholarship

The brittle failure of saline columnar ice was investigated under biaxial compression at and −10° and −40°C over the range 0 ≤ R A < 1 where R A is the ratio of the intermediate to major principal compressive stress. The major principal stress and the intermediate (confining) stress were orthogonal to the columnar axes (type-A confinement); both stresses and the c-axes of the grains were co-planar. The results confirm earlier work by Hausier (1981) and Timco and Frederking (1983, 1986) on saline ice and follow similar behavior to fresh-water columnar ice found by Smith and Schulson (1993) and Frederking (1977). Failure stress and failure mode are sensitive to the confinement and two regimes of behavior are found: the failure stress first rapidly increases with R A in the range 0 ≤ R A < R T and then tends to decrease for R A > R t. The transition stress ratio, R t changes from ≈0.2 at −10°C to ≈0.1 at −40°C. The failure mode changes from axial splitting to shear faulting in the loading plane for 0 < R A < R t. Above R t failure changes to a combined mode of splitting across the columns and shear faulting out of the loading plane. The failure-stress envelope is of a truncated Coulomb-type. Damage studies show wing cracks and local fragmentation of grains involving the brine pockets. The results are explained in terms of Coulombic sliding and Hertzian crack mechanics.

Off-Line Cursive Handwriting Recognition Using Style Parameters, Berrin A. Yanikoglu, Peter A. Sandon

Computer Science Technical Reports

We present a system for recognizing off-line cursive English text, guided in part by global characteristics of the handwriting. A new method for finding the letter boundaries, based on minimizing a heuristic cost function, is introduced. The function is evaluated at each point along the baseline of the word to find the best possible segmentation points. The algorithm tries to find all the actual letter boundaries and as few additional ones as possible. After size and slant normalizations, the segments are classified by a one hidden layer feedforward neural network. The word recognition algorithm finds the segmentation points that are …

Integrating Theory And Practice In Parallel File Systems, Thomas H. Cormen, David Kotz

Dartmouth Scholarship

Several algorithms for parallel disk systems have appeared in the literature recently, and they are asymptotically optimal in terms of the number of disk accesses. Scalable systems with parallel disks must be able to run these algorithms. We present for the first time a list of capabilities that must be provided by the system to support these optimal algorithms: control over declustering, querying about the configuration, independent I/O, and turning off parity, file caching, and prefetching. We summarize recent theoretical and empirical work that justifies the need for these capabilities. In addition, we sketch an organization for a parallel file …

Photoelectric And Ccd Photometry Of E And S0 Galaxies, M. Colless, D. Burstein, G. Wegner, R. P. Saglia

Dartmouth Scholarship

We present BR photoelectric photometry for 352 E and S0 galaxies that are part of a large survey of the properties and peculiar motions of galaxies in distant clusters. Repeat measurements show our internal errors to be 2 – 3 per cent in B and R and 1 – 2 per cent in B– R. Comparisons of BR and BVR reductions for 10 galaxies also observed in V show small systematic errors due to differences between the spectral energy distributions of stars and galaxies. External comparisons with B– V colours in the literature confirm that these colours are …

Throughput Of Existing Multiprocessor File Systems (An Informal Study), David Kotz

Computer Science Technical Reports

Fast file systems are critical for high-performance scientific computing, since many scientific applications have tremendous I/O requirements. Many parallel supercomputers have only recently obtained fully parallel I/O architectures and file systems, which are necessary for scalable I/O performance. Scalability aside, I show here that many systems lack sufficient absolute performance. I do this by surveying the performance reported in the literature, summarized in an informal table.

Accurate Verification Of Five-Axis Numerically Controlled Machining, Jerome L. Quinn

Dartmouth College Ph.D Dissertations

Current automated machining systems are composed of a number of components to aid in bringing a surface from design to physical completion. Numerically controlled (NC) milling machines are used to cut parts out of stock. Programming these machines to cut a desired surface is still largely a matter of experienced human participation. Therefore, the need exists to verify that tool programs produce the desired part.

We present recent developments in the verification of NC tool programs. Many of these methods rely on approximating the stock material as vectors whose lengths reflect the amount of uncut material at any point. This …

Metastability In Two Dimensions And The Effective Potential, Mark Alford, Marcelo Gleiser

Dartmouth Scholarship

We study analytically and numerically the decay of a metastable phase in (2+1)-dimensional classical scalar field theory coupled to a heat bath, which is equivalent to two-dimensional Euclidean quantum field theory at zero temperature. By a numerical simulation we obtain the nucleation barrier as a function of the parameters of the potential, and compare it to the theoretical prediction from the bounce (critical bubble) calculation. We find the nucleation barrier to be accurately predicted by theory using the bounce configuration obtained from the tree-level (“classical”) effective action. Within the range of parameters probed, we found that using the bounce derived …

Efficient Parallel Algorithms For Some Tree Layout Problems, J Diaz, A Gibbons, Grammati E. Pantziou, M Serna, Paul G. Spirakis, J Toran

Computer Science Technical Reports

The minimum cut and minimum length linear arrangement problems usually occur in solving wiring problems and have a lot in common with job sequencing questions. Both problems are NP-complete for general graphs and in P for trees. We present here two algorithms in NC. The first solves the minimum length linear arrangement problem for unrooted trees in $O(\log^2 n)$ time and $O(n^2 3^{\log n})$ CREW PRAM processors. The second algorithm solves the minimum cut arrangement for unrooted trees of maximum degree $d$ in $O(d \log^2 n)$ time and $O(n^2 /\log n)$ CREW PRAM processors.

Integrating Theory And Practice In Parallel File Systems, Thomas H. Cormen, David Kotz

Computer Science Technical Reports

Several algorithms for parallel disk systems have appeared in the literature recently, and they are asymptotically optimal in terms of the number of disk accesses. Scalable systems with parallel disks must be able to run these algorithms. We present a list of capabilities that must be provided by the system to support these optimal algorithms: control over declustering, querying about the configuration, independent I/O, turning off file caching and prefetching, and bypassing parity. We summarize recent theoretical and empirical work that justifies the need for these capabilities.

Distinguishing A Charged Higgs Signal From A Heavy Wr Signal, David I. Kaiser

Dartmouth Scholarship

It is shown that non-Standard Model bosons should obey an observable asymmetry in their decays to taus. This asymmetry enables a distinction to be made between charged Higgsboson signalsand heavy right-handed Wboson signals,by reconstructing the orientation of the z with respect to the beam axis.

Videoscheme: A Programmable Video Editing System For Automation And Media Recognition, James Matthews, Peter Gloor, Fillia Makedon

Computer Science Technical Reports

The recent development of powerful, inexpensive hardware and software support had made digital video editing possible on personal computers and workstations. To date the video editing application category has been dominated by visual, easy-to-use, direct manipulation interfaces. These systems bring high-bandwidth human-computer interaction to a task formerly characterized by slow, inflexible, indirectly-operated machines. However, the direct manipulation computer interfaces are limited by their manual nature, and can not easily accommodate algorithmically- defined operations. This paper proposes a melding of the common direct manipulation interfaces with a programming language which we have enhanced to manipulate digital audio and video. The result …

Asymptotically Tight Bounds For Performing Bmmc Permutations On Parallel Disk Systems, Thomas H. Cormen, Leonard F. Wisniewski

Computer Science Technical Reports

No abstract provided.

Vector Layout In Virtual-Memory Systems For Data-Parallel Computing, Thomas H. Cormen

Computer Science Technical Reports

In a data-parallel computer with virtual memory, the way in which vectors are laid out on the disk system affects the performance of data-parallel operations. We present a general method of vector layout called banded layout, in which we divide a vector into bands of a number of consecutive vector elements laid out in column-major order, and we analyze the effect of the band size on the major classes of data-parallel operations. We find that although the best band size varies among the operations, choosing fairly small band sizes—at most a track—works well in general.

Decay Of The Relative Error In The Formation Of Acoustic Bullets, Harry E. Moses, Reese T. Prosser

Dartmouth Scholarship

In a previous paper, the authors showed how to construct certain solutions of the acoustic and electromagnetic wave equations in three dimensions, which are constrained asymptotically to a narrow conical sector of an outgoing spherical shell, i.e., which behave like “bullets.” In this paper, it is shownthat, in the acoustic case, the magnitude of the relative error between the true solution and its asymptotic form decays in time according to an inverse square root law.
Read More: https://epubs.siam.org/doi/10.1137/0153025

Multiprocessor File System Interfaces, David Kotz

Dartmouth Scholarship

Increasingly, file systems for multiprocessors are designed with parallel access to multiple disks, to keep I/O from becoming a serious bottleneck for parallel applications. Although file system software can transparently provide high-performance access to parallel disks, a new file system interface is needed to facilitate parallel access to a file from a parallel application. We describe the difficulties faced when using the conventional (Unix-like) interface in parallel applications, and then outline ways to extend the conventional interface to provide convenient access to the file for parallel programs, while retaining the traditional interface for programs that have no need for explicitly …

Practical Prefetching Techniques For Multiprocessor File Systems, David Kotz, Carla Schlatter Ellis

Dartmouth Scholarship

Improvements in the processing speed of multiprocessors are outpacing improvements in the speed of disk hardware. Parallel disk I/O subsystems have been proposed as one way to close the gap between processor and disk speeds. In a previous paper we showed that prefetching and caching have the potential to deliver the performance benefits of parallel file systems to parallel applications. In this paper we describe experiments with practical prefetching policies that base decisions only on on-line reference history, and that can be implemented efficiently. We also test the ability of these policies across a range of architectural parameters.