Mathematics of Computation Preprint version available at

Description

Mathematics of Computation 78 (2009), 591-613 Preprint version available at BIMONOTONE ENUMERATION MICHAEL EISERMANN ABSTRACT. Solutions of a diophantine equation f (a,b) = g(c,d), with a,b,c,d in some finite range, can be efficiently enumerated by sorting the values of f and g in ascending order and searching for collisions. This article considers functions f : N?N? Z that are bimonotone in the sense that f (a,b) ≤ f (a?,b?) whenever a ≤ a? and b ≤ b?. A two- variable polynomial with non-negative coefficients is a typical example. The problem is to efficiently enumerate all pairs (a,b) such that the values f (a,b) appear in increasing order. We present an algorithm that is memory-efficient and highly parallelizable. In order to enumerate the first n values of f , the algorithm only builds up a priority queue of length at most √ 2n + 1. In terms of bit-complexity this ensures that the algorithm takes time O(n log2 n) and requires memory O(√n logn), which considerably improves on the memory bound ?(n log n) provided by a naıve approach, and extends the semimonotone enumeration algorithm previously considered by R.L. Ekl and D.

• algorithm has


• algorithm


• memory requirements


• efficiently enumerate all


• since most


• optimiza- tion can


• general setting


• partial order


• elements need

Sujets

• Algorithm
• Partially ordered set

Informations

• Publié par: pefav
• Nombre de lectures: 12
• Langue: English

Extrait

Mathematics of Computation 78 (2009), 591-613 Preprint version available at http://www-fourier.ujf-grenoble.fr/˜eiserm

BIMONOTONE ENUMERATION

MICHAEL EISERMANN

A BS TRACT . Solutions of a diophantine equationf(ab) =g(cd), withabcdin some nite range, can be efciently enumerated by sorting the vaules offandgin ascending order and searching for collisions. This article considers functionsf:N×N→Zthat are bimonotone in the sense thatf(ab)≤f(a ′ b ′ )whenevera≤a ′ andb≤b ′ . A two- variable polynomial with non-negative coefcients is a typical example. The problem is to efciently enumerate all pairs(ab)such that the valuesf(ab)appear in increasing order. We present an algorithm that is memory-efcient and highly parallelizable. In order to enumerate the rstnvalues off, the algorithm only builds up a priority queue of length at most 2n+1. Inbit-complexity this ensures that the algorithm takes terms of timeO(nlog 2 n)and requires memoryO(nlogn), which considerably improves on the memory boundQ(nlogn)etonominoemesthdsenxtdean,hcaorppaev¨anarpvodideyb enumeration algorithm previously considered by R.L. Ekl and D.J. Bernstein.

1. I NTRODUCTION AND STATEMENT OF RESULTS 1.1.Motivation.Given polynomial functionsfg:N×N→Z, how can we efciently enumerate solutions of the equationf(ab) =g(cd)? One standard way to do this is to sort the setsF={(f(ab)ab)|1≤ab≤N}andG={(g(cd)cd)|1≤cd≤N}into ascending order with respect to the rst coordinate and to look for collisions. As stated, this requires storing all elements before sorting, which consumes memoryQ(nlogn), where n=N 2 the number of values to enumerate, and time betweenis W(nlogn)andO(nlog 2 n). The present article develops a less memory consuming algorithm under the hypothesis thatfandgarebimonotone, that is, monotone in each variable. This is sufciently of- ten the case to be of interest, for example, whenfandgare given by polynomials with non-negative coefcients. Given a bimonotone functionf, Algorithm 4, discussed below, produces a streamx 1 x 2 x 3    enumerating all parametersx i = (a i b i )in the domain of fsuch thatf(x 1 )6f(x 2 )6f(x 3 )6   at hand such sorted enumerations for. Having fandg, one can easily enumerate solutions of the equationf(x) =g(y): start withi=1 andj=1; wheneverf(x i )<g(y j ), incrementi; wheneverf(x i )>g(y j ), incrementj. If eventuallyf(x i ) =g(y j ), then output the solution(x i y j )and continue searching. 1.2.Main result. [1] with BernsteinThe idea of sorted enumeration was applied by D.J. great success to equations of the special formp(a) +q(b) =r(c) +s(d). We generalize his approach to arbitrary bimonotone functions. The main result can be stated as follows:

Date: rst version June 2005; this version compiled March 16, 2009. 2000Mathematics Subject Classication.68P10; 11Y50, 68W10, 11Y16, 11D45. Key words and phrases.sorting and searching, diophantine equation, bimonotone function, sorted enumera- tion, semimonotone enumeration, bimonotone enumeration. 1

2

MICHAEL EISERMANN

Theorem 1.Suppose that f:N×N→Zis bimonotone and proper in the sense that for every z∈Zonly nitely many pairs(ab)satisfy f(ab)≤z. Then Algorithm 4 stated below produces a stream enumerating all pairs(ab)∈N×Nsuch that the values f(ab) appear in increasing order. While enumerating the rst n values, the algorithm only builds up a priority queue of length m≤2n+1 a polynomial, this ensures that the. If f is algorithm takes time O(nlog 2 n)and requires memory O(nlogn). The precise boundm≤2n+1 is free of hidden constants and thus uniformly valid for all bimonotone functionsf. The less explicit bounds of timeO(nlog 2 n)and memory O(nlogn)concern the bit-complexity and the hidden constants necessarily depend onf. We shall assume throughout thatfbehaves polynomially, see§2.3. To place this result into perspective, notice that the time requirementO(nlog 2 n)is nearly optimal: enumeratingnelements obviously needsniterations, and one lognfactor is due to their increasing size. On the other hand, the standard approach would require memoryQ(nlogn)to storeall Here the stream approachvalues before outputting them. can achieve considerable savings and reduce memory toO(nlogn). Example 2.Considerf(ab) =p(a) +q(b)wherepandqare non-decreasing polyno- mial functions of degreea=degpandb=degq Assuming, respectively. 1≤a≤b, Algorithm 4 builds up a priority queue of lengthm∈Q(n Α )withΑ= a+b ∈[0 2 ]. This illustrates that in the uniform boundm∈O(n 12 ), stated in the theorem for all bimonotone functions, the exponent 2 cannot be improved. Notwithstanding, the algorithm performs better on certain subclasses of bimonotone functions, whereΑ< 2 . Remark 3.The predecessor of our algorithm is semimonotone enumeration, recalled in §3. It was devised in [2, 1] for polynomials of the formf(ab) =p(a) +q(b), where it pro- vides the desired memory boundO(nlogn) the more general setting of bimonotone. In functions, however, we show that it only guarantees the memory boundO(nlogn)and in general the exponent 1 cannot be improved. See§5 for a detailed discussion. As an additional benet, our algorithm turns out to be highlyparallelizable:

Remark 4.Algorithm 4 can be adapted to enumerate only those pairs(ab)∈N×Nfor which the valuesf(ab)lie in a given interval[z 1 z 2 ] and memory requirements. Time are essentially the same as before; only initialization induces some additional cost and can usually be neglected. This means that searching solutionsf(ab) =g(cd)can be split up into disjoint intervals and thus parallelized on independent machines (see§6). 1.3.How this article is organized.Section 2 introduces the necessary notation and re- calls the generic algorithm of sorted enumeration for an arbitrary mapf:X→Z, where Xi.Ekl[2]lyaltien.LoRetdurogladensse,mhtiiscuon3daressestiseasnceitteS. and D.J. Bernstein [1], under the hypothesis thatf:A×B→Zis semimonotone, that is, monotone in the rst variable. Section 4 develops a sorted enumeration algorithm for bimonotone functions, and Section 5 analyses the asymptotic complexity. Section 6 high- lights the intrinsically parallel structure of such a search problem. Section 7 generalizes our algorithms to functionsf:X→Zrestricted to suitable domainsX⊂A×Bthat are of of practical interest. Finally, Section 8 briey indicates applications to diophantine enu- meration problems, such as the taxicab problem.

1.4.Acknowledgement.the anonymous referee for his thorough critique, harshI thank but fair, which substantially contributed to improve the exposition.