An algorithm is proposed for locating and computing in parallel and with certainty all the simple roots of any twice continuously differentiable function in any specific interval. To compute with certainty all the roo...
详细信息
An algorithm is proposed for locating and computing in parallel and with certainty all the simple roots of any twice continuously differentiable function in any specific interval. To compute with certainty all the roots, the proposed method is heavily based on the knowledge of the total number of roots within the given interval. To obtain this information we use results from topological degree theory and, in particular, the Kronecker-Picard approach. This theory gives a formula for the computation of the total number of roots of a system of equations within a given region, which can be computed in parallel, With this tool in hand, we construct a parallel procedure for the localization and isolation of all the roots by dividing the given region successively and applying the above formula to these subregions until the final domains contain at the most one root. The subregions with no roots are discarded, while for the rest a modification of the well-known bisection method is employed for the computation of the contained root. The new aspect of the present contribution is that the computation of the total number of zeros using the Kronecker-Picard integral as well as the localization and computation of all the roots is performed in parallel using the parallel virtual machine (PVM). PVM is an integrated set of software tools and libraries that emulates a general-purpose, flexible, heterogeneous concurrent computing framework on interconnected computers of varied architectures. The proposed algorithm has large granularity and low synchronization, and is robust. It has been implemented and tested and our experience is that it can massively compute with certainty all the roots in a certain interval. Performance information from massive computations related to a recently proposed conjecture due to Elbert (this issue, J. Comput. Appl. Math. 133 (2001) 65-83) is reported. (C) 2001 Elsevier Science B.V. All rights reserved.
Retrograde analysis is an efficient exhaustive search method. It is a powerful tool that can be used in solving problems where end states have known values but starting states do not. It has been widely used to solve ...
详细信息
ISBN:
(纸本)0769512968
Retrograde analysis is an efficient exhaustive search method. It is a powerful tool that can be used in solving problems where end states have known values but starting states do not. It has been widely used to solve mathematically-precise games such as chess endgames, and is potentially usable in energy-minimization problems. With increasing computing power, both in speed and storage capacity, retrograde analysis will become more and more useful. This paper looks at successful applications to games, the challenges ahead, and the modifications that are required to utilize distributed hardware. The power and the usefulness of retrograde analysis are still limited by the computing resources one has access to. Today, the best sequential retrograde algorithms are capable of solving problems with about 109 states in a few hours on a standard personal computer Bigger problems need more powerful computers, or take much longer to solve, or are simply out of reach of today's technologies, Introducing parallelism to retrograde analysis is a natural way to attack the bigger problems. There are today three main architectures available for doing parallel retrograde analysis: namely Symmetric Multiprocessor systems, High-speed network based distributed systems, and Internet based distributed systems. In this paper, we discuss some of the key issues in doing parallel retrograde analysis on these different architectures. Technical challenges are addressed in detail, as well as some examples and proposals. These examples and proposals are drawn from various board games, but the ideas can be applied to other problem domains.
A parallel single level store system (PSLS) integrates a shared virtual memory and a parallel file system. Managing the data globally it provides programmers of scientific applications with the attractive shared memor...
详细信息
Wavelet transforms have proven to be useful tools for several applications, including signal analysis, signal coding, and image compression. In this paper, faster parallel algorithms for computing the continuous wavel...
详细信息
In contrast to the common belief that OpenMP requires data-parallel extensions to scale well on architectures with non-uniform memory access latency, recent work has shown that it is possible to develop OpenMP program...
详细信息
A parallel architecture for decoding low density parity check (LDPC) codes is proposed that achieves high coding gain together with extremely low power dissipation, and high throughput. The feasibility of this archite...
详细信息
ISBN:
(纸本)0780366859
A parallel architecture for decoding low density parity check (LDPC) codes is proposed that achieves high coding gain together with extremely low power dissipation, and high throughput. The feasibility of this architecture is demonstrated through the design and implementation of a 1024 bit, rate-1/2, soft decision parallel LDPC decoder.
We discuss parallel algorithms for wavelet-based image and video coding. After reviewing fundamentals of the parallel discrete wavelet transform, we cover the parallelization of two state-of-the-art compression scheme...
详细信息
ISBN:
(纸本)9539676940
We discuss parallel algorithms for wavelet-based image and video coding. After reviewing fundamentals of the parallel discrete wavelet transform, we cover the parallelization of two state-of-the-art compression schemes: a C++ 3D SPIHT video codec and a Java JPEG-2000 implementation.
暂无评论