User igor markov - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T21:55:59Z http://mathoverflow.net/feeds/user/17596 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/103960/recent-fast-multiplication-algorithms-for-large-integers Recent Fast Multiplication Algorithms for Large Integers Igor Markov 2012-08-04T16:47:07Z 2012-08-05T01:19:42Z <p>The STOC 2008 paper "Fast Integer Multiplication using Modular Arithmetic" by De et al <a href="http://arxiv.org/abs/0801.1416" rel="nofollow">http://arxiv.org/abs/0801.1416</a> shows how to use $p$-adic numbers instead of $\mathbb C$ used in Furer's multiplication algorithm. Given that Furer's algorithm is not practical for less than a few thousand bits (is there a good estimate of its breakeven point vs Toom-Cook and other algorithms?), I wonder if the De et al algorithm has a lower breakeven point, is easier to implement, and is more practical in general. </p> <p>Pointers to follow-up work and/or attempts at implementing the STOC 2008 algorithm would be appreciated.</p> <p>Igor</p> http://mathoverflow.net/questions/87303/best-algorithm-software-for-solving-a-planar-transportation-problem Best algorithm/software for solving a planar transportation problem ? Igor Markov 2012-02-02T05:03:07Z 2012-07-08T20:40:06Z <p>I am looking for software (open-source or otherwise) or an implementable algorithm for solving a continuous transportation problem. The input consists of a pointset in a planar rectangle, and we need to relocate these points within the rectangle to decrease the peak density below a given threshold (feasibility can be assumed), while minimizing total displacement. </p> <p>The distances inside the rectangle are Manhattan/taxicab, although efficient solutions for the Euclidean distance can also be helpful. <em>Total displacement</em> is interpreted in the $L_1$ sense, but efficient solutions for the $L_2$ case can also be helpful. The peak density can be evaluated with respect to a uniform grid (is there another practical way ?)</p> <p>My students implemented a geometric algorithm (without having any background in transportation) that works great in our application, but we don't know how far the results are from optimal. Just in case, our application also imposes rectangular "exclusion zones", where no points can be placed (more generally, we can assume a "bounding probability distribution").</p> http://mathoverflow.net/questions/96967/an-mst-like-problem-with-vertex-selection An MST-like problem with vertex selection Igor Markov 2012-05-15T05:18:58Z 2012-05-15T05:18:58Z <p>Consider a planar pointset in a rectangle, where every point has a color (an integer label). We need to select one point of every color, so as to minimize the cost of a planar MST of selected points (in my application, the distances are Manhattan/$L_1$).</p> <p>For example, given the locations of US cities, we would find an MST that connects to one city from every state.</p> <p>If helpful, we could additionally assume that the local density of the pointset is upper-bounded (the points can't be clustered too closely). Points of the same color will generally come in groups (can even assume that each color corresponds to a connected region).</p> <p>A straightforward heuristic would average locations of points of each color, build an MST for those "centers", and then look for shortcuts. Is there something better ?</p> <p>Points of interest: a proof of NP-hardness, an approximation algorithm, an effective heuristic</p> http://mathoverflow.net/questions/87644/differences-between-the-poissons-and-elliptic-monge-ampere-equations Differences between the Poisson's and elliptic Monge-Ampere equations? Igor Markov 2012-02-06T09:40:33Z 2012-02-06T17:28:02Z <p>I am working with a numerical application where some known techniques solve $\Delta u=\rho$ for $\rho(x,y)\geq0$ defined on a planar rectangle (given as the density of a large pointset). Since the application is related to transportation problems, I suspect that solving Monge-Ampere $\det(D^2 u)=\rho$ (with the same boundary conditions) may work better. Hence, the following questions. </p> <ol> <li><p>What are the most striking differences between the two PDEs ? It would be useful to have examples of $\rho$ leading to very different solutions, and to identify general properties of individual solutions that differ between the two equations. For example, do solutions of Poisson's equation with nonzero $\rho$ minimize some useful functionals ?</p></li> <li><p>Are the <em>best</em> numerical techniques for these equations essentially the same ? The answers may differ if <em>best</em> is interpreted in terms of speed/convergence, robustness, ease of programming, support in Matlab, or availability of open-source solvers.</p></li> <li><p>Should I expect the (nonlinear) Monge-Ampere equation to be more difficult to solve (numerically) than the Poisson's equation with the same $\rho$ and the same boundary conditions ? Is it possible/practical to solve Monge-Ampere by somehow solving/resolving Poisson's equation ?</p></li> <li><p>What are good references on these topics ?</p></li> </ol> <p>Just in case, my $\rho$ can be heavily concentrated in small regions, often vanishes in other regions, and may experience sharp steps-like discontinuities. But this can be papered over by Gaussian smoothing (at some cost).</p> http://mathoverflow.net/questions/84622/is-the-maximum-tree-path-length-distributed-lognormally-in-the-limit Is the maximum tree-path length distributed lognormally (in the limit) ? Igor Markov 2011-12-31T01:34:01Z 2011-12-31T15:35:57Z <p>Consider a full binary tree with $k>10$ levels. Let the <em>lengths</em> of individual edges in this tree be i.i.d. random variables with finite moments. Then total lengths of the $2^{k-1}$ source-to-sink paths in this tree are approximately Gaussian by the CLT, regardless of the edge-length distribution. We are interested in the limit distribution ($k\rightarrow\infty$) of the maximum path length in the tree.</p> <p>Our numerical simulation built 100K independent trees ($k=15$) with $(a)$ uniform and $(b)$ Gaussian edge lengths. The resulting distributions for $(a)$ and $(b)$ did not look qualitatively different and were somewhat skewed to the right. Lognormal distributions provided very close fits --- better than <em>Gumbel</em> and <em>Airy</em>. If lognormal is indeed the limit distribution, we would appreciate references or suggestions on proving this analytically.</p> http://mathoverflow.net/questions/74556/generator-sets-of-a-subgroup-of-s-n-with-on-total-support-do-they-always Generator sets of a subgroup of $S_n$ with $O(n)$ total support - do they always exist ? Igor Markov 2011-09-05T06:37:23Z 2011-09-05T10:10:01Z <p>For a permutation of a finite set $X$, define its <em>supporting set</em> as the complement in $X$ of its <em>fixed-point set</em>. The term <em>support</em> describes the size of a supporting set. For example, a $k$-cycle has support $k$.</p> <p>Consider a subgroup $H$ of $S_n$, such as $H=Aut(G)$ for an $n$-vertex graph $G$. We are interested in small generating sets of $H$. But rather than count the generators, we are going to add up their supports and call the result <em>the total support</em> of a generating set.</p> <ol> <li><p>$H$ can always be generated by at most $n-1$ generators. An elegant proof, anyone?</p></li> <li><p>Is it true that a generating set of $H$ exists with $O(n)$ total support ? If not, an example of the form $Aut(G)$ would be most useful. If yes, can total support be limited by $Cn$ for a known $C>0$ ?</p></li> <li><p>Same question with at most $n-1$ generators.</p></li> </ol> <p>As an illustration, take $S_n$. It can be generated by $n-1$ transpositions whose total support is $2n-2$. Or by one transposition and a full cycle, whose total support is $n+2$. </p> http://mathoverflow.net/questions/103960/recent-fast-multiplication-algorithms-for-large-integers Comment by Igor Markov Igor Markov 2012-08-05T01:33:42Z 2012-08-05T01:33:42Z Apparently not - the Toom-Cook family of algorithms rules in a large range. This old paper <a href="http://lyle.smu.edu/~seidel/courses/cse8351/papers/ZurasMult.pdf" rel="nofollow">lyle.smu.edu/~seidel/courses/cse8351/papers/&hellip;</a> evaluates Schonhage-Strassen and claims that it does not win at least until 37M bits http://mathoverflow.net/questions/87303/best-algorithm-software-for-solving-a-planar-transportation-problem/92632#92632 Comment by Igor Markov Igor Markov 2012-03-30T21:36:38Z 2012-03-30T21:36:38Z Looking into it very closely now. While we are now leaning toward $l_2$-optimal transport because it tends to preserve the relative ordering of &quot;the grains of sand&quot; being transported. Also, the uniqueness of $l_2$-optimal solutions is useful. But we'll definitely take a look at the software you suggested. http://mathoverflow.net/questions/87644/differences-between-the-poissons-and-elliptic-monge-ampere-equations Comment by Igor Markov Igor Markov 2012-02-07T22:32:55Z 2012-02-07T22:32:55Z Makes sense. Thank you. http://mathoverflow.net/questions/87644/differences-between-the-poissons-and-elliptic-monge-ampere-equations Comment by Igor Markov Igor Markov 2012-02-06T23:22:12Z 2012-02-06T23:22:12Z Hmm... I am not sure how to exploit such invariance in my case, since the domain is bounded and $\rho$ seems unlikely to be invariant. http://mathoverflow.net/questions/87644/differences-between-the-poissons-and-elliptic-monge-ampere-equations/87679#87679 Comment by Igor Markov Igor Markov 2012-02-06T17:32:47Z 2012-02-06T17:32:47Z @Andrew, @Deane - I am looking at A gradient descent solution to the Monge-Kantorovich problem,'' Chartrand et al (Applied Math Sci 2009, 3(22)) math.lanl.gov/Research/Publications/Docs/…. This should explain my interest in $\det(D^2u)=ρ$ (but not the use of $Δu=ρ$ by others). Sections 3 and 4 apparently imply a straightforward numerical solution technique for Monge-Ampere --- consider $f_2=const$ in Formulas 14 and 24. How do I reconcile this with &quot;much more difficult to solve numerically&quot; ? Thx for your help. http://mathoverflow.net/questions/87644/differences-between-the-poissons-and-elliptic-monge-ampere-equations/87679#87679 Comment by Igor Markov Igor Markov 2012-02-06T17:16:40Z 2012-02-06T17:16:40Z Omitting $det$ in the question was a typo (sorry!) - I fixed that. http://mathoverflow.net/questions/87644/differences-between-the-poissons-and-elliptic-monge-ampere-equations Comment by Igor Markov Igor Markov 2012-02-06T09:56:17Z 2012-02-06T09:56:17Z Thinking aloud: for #1, we may want to consider two cases (1) $\rho$ with well-articulated saddle points and (2) $\rho$ without saddle points. http://mathoverflow.net/questions/87303/best-algorithm-software-for-solving-a-planar-transportation-problem Comment by Igor Markov Igor Markov 2012-02-06T08:15:45Z 2012-02-06T08:15:45Z Yes, and it is suboptimal. Recall that 1D transportation has a simple/closed-form solution, implemented for a pointset input by sorting. In 2D, we alternate optimal transportation in X,Y directions, position cutlines at median locations, then recursively divide and conquer. Now consider a pointset distributed normally in 2D. The 1D solution can be applied radially, but our algorithm produces something blocky. A more important question for us is how the suboptimality affects our application (which can &quot;transport&quot; millions of points 40-50 times per run)- this is difficult to answer w/o a solver http://mathoverflow.net/questions/84622/is-the-maximum-tree-path-length-distributed-lognormally-in-the-limit/84642#84642 Comment by Igor Markov Igor Markov 2012-01-01T07:21:49Z 2012-01-01T07:21:49Z Makes sense - thanks !