首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到10条相似文献,搜索用时 93 毫秒
1.
We exhibit two black-box problems, both of which have an efficient quantum algorithm with zero-error, yet whose composition does not have an efficient quantum algorithm with zero-error. This shows that quantum zero-error algorithms cannot be composed. In oracle terms, we give a relativized world where ZQPZQP≠ZQP, while classically we always have ZPPZPP=ZPP.  相似文献   

2.
In Noro (2010) we proposed an algorithm for computing a primary ideal decomposition by using the notion of a separating ideal and showed that it can efficiently decompose several examples which are hard to decompose using existing algorithms. In particular, the number of redundant components produced in the algorithm is zero or very small in many examples, but no theoretical explanation for the efficiency was given.In this paper we define a more sophisticated class of separating ideals: saturated separating ideals. By using this notion we modify the algorithm of Noro (2010) such that it directly outputs a minimal primary decomposition without producing any intermediate redundant component.By modifying the process of extraction of a primary component via the pseudo-primary decomposition proposed in Shimoyama and Yokoyama (1996), we find a method for intermediate decomposition of an ideal and propose a variant of the new primary decomposition algorithm based on this intermediate decomposition. Our experiment shows that this variant efficiently decomposes many examples which are still hard to decompose even if we apply the original version of the new algorithm. Furthermore, in this algorithm we can bypass the computation of primary components and obtain directly the set of all associated primes of an ideal.  相似文献   

3.
In this paper we present a new stable algorithm for the parallel QR-decomposition of “tall and skinny” matrices. The algorithm has been developed for the dense symmetric eigensolver ELPA, where the QR-decomposition of tall and skinny matrices represents an important substep. Our new approach is based on the fast but unstable CholeskyQR algorithm (Stathopoulos and Wu, 2002) [1]. We show the stability of our new algorithm and provide promising results of our MPI-based implementation on a BlueGene/P and a Power6 system.  相似文献   

4.
We present an engineered version of the divide-and-conquer algorithm for finding the closest pair of points,within a given set of points in the XY-plane.For this version of the algorithm we show that only two pairwise comparisons are required in the combine step,for each point that lies in the 2δ-wide vertical slab.The correctness of the algorithm is shown for all Minkowski distances with p 1.We also show empirically that,although the time complexity of the algorithm is still O(n lg n),the reduction in the total number of comparisons leads to a significant reduction in the total execution time,for inputs with size sufficiently large.  相似文献   

5.
Quite often in database search, we only need to extract portion of the information about the satisfying item. We consider this problem in the following form: the database of N items is separated into K blocks of size b = N / K elements each and an algorithm has just to find the block containing the item of interest. The queries are exactly the same as in the standard database search problem. We present a quantum algorithm for this problem of partial search that takes about 0.34 fewer iterations than the quantum search algorithm.  相似文献   

6.
We consider concurrent-write PRAMs with a large number of processors of unlimited computational power and an infinite shared memory. Our adversary chooses a small number of our processors and gives them a 0–1 input sequence (each chosen processor gets a bit, and each bit is given to one processor). The chosen processors are required to compute thePARITY of their input, while the others do not take part in the computation. Ifat most q processors are chosen andq 1/2 log logn, then we show that computing PARITY needsq steps in the worst case. On the other hand, there exists an algorithm which computes PARITY inq steps (for anyq <n) in this model, thus our result is sharp. Surprisingly, if our adversary choosesexactly q of our processors, then they can compute PARITY in [q/2] + 2 steps, and in this case we show that it needs at least [q2] steps. Our result implies that large parallel machines which are efficient when only a small number of their processors are active cannot be constructed. On the other hand, a result of Ajtai and Ben-Or [1] shows that if we haven input bits which contain at most polylogn 1's and polynomially many processors which are all allowed to work, then thePARITY can be solved inconstant time.  相似文献   

7.
In this paper we investigate the parallelization of two modular algorithms. In fact, we consider the modular computation of Gröbner bases (resp. standard bases) and the modular computation of the associated primes of a zero-dimensional ideal and describe their parallel implementation in Singular. Our modular algorithms for solving problems over Q mainly consist of three parts: solving the problem modulo p for several primes p, lifting the result to Q by applying the Chinese remainder algorithm (resp. rational reconstruction), and verification. Arnold proved using the Hilbert function that the verification part in the modular algorithm for computing Gröbner bases can be simplified for homogeneous ideals (cf. Arnold, 2003). The idea of the proof could easily be adapted to the local case, i.e. for local orderings and not necessarily homogeneous ideals, using the Hilbert-Samuel function (cf. Pfister, 2007). In this paper we prove the corresponding theorem for non-homogeneous ideals in the case of a global ordering.  相似文献   

8.
Simulating Boolean Circuits on a DNA Computer   总被引:6,自引:0,他引:6  
M. Ogihara  A. Ray 《Algorithmica》1999,25(2-3):239-250
We demonstrate that DNA computers can simulate Boolean circuits with a small overhead. Boolean circuits embody the notion of massively parallel signal processing and are frequently encountered in many parallel algorithms. Many important problems such as sorting, integer arithmetic, and matrix multiplication are known to be computable by small size Boolean circuits much faster than by ordinary sequential digital computers. This paper shows that DNA chemistry allows one to simulate large semi-unbounded fan-in Boolean circuits with a logarithmic slowdown in computation time. Also, for the class NC 1 , the slowdown can be reduced to a constant. In this algorithm we have encoded the inputs, the Boolean AND gates, and the OR gates to DNA oligonucleotide sequences. We operate on the gates and the inputs by standard molecular techniques of sequence-specific annealing, ligation, separation by size, amplification, sequence-specific cleavage, and detection by size. Additional steps of amplification are not necessary for NC 1 circuits. The feasibility of the DNA algorithm has been successfully tested on a small circuit by actual biochemical experiments. Received May 29, 1997; revised February 15, 1998.  相似文献   

9.
In order to deal with the common trend in size increase of volumetric datasets, in the past few years research in isosurface extraction has focused on related aspects such as surface simplification and load-balanced parallel algorithms.We present a parallel, block-wise extension of the tandem algorithm [Attali D, Cohen-Steiner D, Edelsbrunner H. Extraction and simplification of iso-surfaces in tandem. In: SGP ’05: Proceedings of the third Eurographics symposium on Geometry processing. Aire-la-Ville, Switzerland: Eurographics Association; 2005. p. 139-148], which simplifies on the fly an isosurface being extracted. Our approach minimizes the overall memory consumption using an adequate block splitting and merging strategy along with the introduction of a component dumping mechanism that drastically reduces the amount of memory needed for particular datasets such as those encountered in geophysics. As soon as detected, surface components are migrated to the disk along with a meta-data index (oriented bounding box, volume, etc.) that permits further improved exploration scenarios (small component removal or particularly oriented component selection for instance).For ease of implementation, we carefully describe a master and worker algorithm architecture that clearly separates the four required basic tasks. We show several results of our parallel algorithm applied on a geophysical dataset of size 7000×1600×2000.  相似文献   

10.
This article presents an adaptive approach to improving the infection algorithm that we have used to solve the dense stereo matching problem. The algorithm presented here incorporates two different epidemic automata along a single execution of the infection algorithm. The new algorithm attempts to provide a general behavior of guessing the best correspondence between a pair of images. Our aim is to provide a new strategy inspired by evolutionary computation, which combines the behaviors of both automata into a single correspondence problem. The new algorithm will decide which automata will be used based on the transmission of information and mutation, as well as the attributes, texture, and geometry, of the input images. This article gives details about how the rules used in the infection algorithm are coded. Finally, we show experiments with a real stereo pair, as well as with a standard test bed, to show how the infection algorithm works.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号