Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Remote Access
Green Open Access
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(online) ISSN 0025-5718(print)

 

Bimonotone enumeration


Author: Michael Eisermann
Journal: Math. Comp. 78 (2009), 591-613
MSC (2000): Primary 68P10; Secondary 11Y50, 68W10, 11Y16, 11D45
Published electronically: June 16, 2008
MathSciNet review: 2448723
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 \colon \mathbb{N} \times \mathbb{N}\to \mathbb{Z}$ that are bimonotone in the sense that $ f(a,b) \le f(a',b')$ whenever $ a \le a'$ and $ b \le 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 $ \sqrt{2n}+1$. In terms of bit-complexity this ensures that the algorithm takes time $ O( n \log^2 n )$ and requires memory $ O( \sqrt{n} \log n )$, which considerably improves on the memory bound $ \Theta( n \log n )$ provided by a naïve approach, and extends the semimonotone enumeration algorithm previously considered by R.L.Ekl and D.J.Bernstein.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 68P10, 11Y50, 68W10, 11Y16, 11D45

Retrieve articles in all journals with MSC (2000): 68P10, 11Y50, 68W10, 11Y16, 11D45


Additional Information

Michael Eisermann
Affiliation: Institut Fourier, Université Grenoble I, France
Email: Michael.Eisermann@ujf-grenoble.fr

DOI: http://dx.doi.org/10.1090/S0025-5718-08-02162-5
PII: S 0025-5718(08)02162-5
Keywords: Sorting and searching, diophantine equation, bimonotone function, sorted enumeration, semimonotone enumeration, bimonotone enumeration
Received by editor(s): July 27, 2005
Received by editor(s) in revised form: June 22, 2007
Published electronically: June 16, 2008
Article copyright: © Copyright 2008 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.



Comments: Email Webmaster

© Copyright , American Mathematical Society
Contact Us · Sitemap · Privacy Statement

Connect with us Facebook Twitter Google+ LinkedIn Instagram RSS feeds Blogs YouTube Podcasts Wikipedia