User igor markov - MathOverflow

Recent Fast Multiplication Algorithms for Large Integers

2012-08-04T16:47:07Z

The STOC 2008 paper "Fast Integer Multiplication using Modular Arithmetic" by De et al http://arxiv.org/abs/0801.1416 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.

Pointers to follow-up work and/or attempts at implementing the STOC 2008 algorithm would be appreciated.

Igor

Best algorithm/software for solving a planar transportation problem ?

2012-02-02T05:03:07Z

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.

The distances inside the rectangle are Manhattan/taxicab, although efficient solutions for the Euclidean distance can also be helpful. Total displacement 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 ?)

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").

An MST-like problem with vertex selection

2012-05-15T05:18:58Z

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$).

For example, given the locations of US cities, we would find an MST that connects to one city from every state.

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).

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 ?

Points of interest: a proof of NP-hardness, an approximation algorithm, an effective heuristic

Differences between the Poisson's and elliptic Monge-Ampere equations?

2012-02-06T09:40:33Z

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.

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 ?
Are the best numerical techniques for these equations essentially the same ? The answers may differ if best is interpreted in terms of speed/convergence, robustness, ease of programming, support in Matlab, or availability of open-source solvers.
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 ?
What are good references on these topics ?

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).

Is the maximum tree-path length distributed lognormally (in the limit) ?

2011-12-31T01:34:01Z

Consider a full binary tree with $k>10$ levels. Let the lengths 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.

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 Gumbel and Airy. If lognormal is indeed the limit distribution, we would appreciate references or suggestions on proving this analytically.

Generator sets of a subgroup of $S_n$ with $O(n)$ total support - do they always exist ?

2011-09-05T06:37:23Z

For a permutation of a finite set $X$, define its supporting set as the complement in $X$ of its fixed-point set. The term support describes the size of a supporting set. For example, a $k$-cycle has support $k$.

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 the total support of a generating set.

$H$ can always be generated by at most $n-1$ generators. An elegant proof, anyone?
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$ ?
Same question with at most $n-1$ generators.

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$.

Comment by Igor Markov

2012-08-05T01:33:42Z

Apparently not - the Toom-Cook family of algorithms rules in a large range. This old paper lyle.smu.edu/~seidel/courses/cse8351/papers/… evaluates Schonhage-Strassen and claims that it does not win at least until 37M bits

Comment by Igor Markov

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 "the grains of sand" being transported. Also, the uniqueness of $l_2$-optimal solutions is useful. But we'll definitely take a look at the software you suggested.

Comment by Igor Markov

2012-02-07T22:32:55Z

Makes sense. Thank you.

Comment by Igor Markov

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.

Comment by Igor Markov

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 "much more difficult to solve numerically" ? Thx for your help.

Comment by Igor Markov

2012-02-06T17:16:40Z

Omitting $det$ in the question was a typo (sorry!) - I fixed that.

Comment by Igor Markov

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.

Comment by Igor Markov

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 "transport" millions of points 40-50 times per run)- this is difficult to answer w/o a solver

Comment by Igor Markov

2012-01-01T07:21:49Z

Makes sense - thanks !