Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Attempting to compute the kslog numerically (i.e., Kneser's construction)
Well, I was fairly certain the Kneser's solution would be equivalent to the intuitive slog, as there is a uniqueness condition which I've seen explained a couple different ways, but it boils down to the same thing. So I decided to put this to the test, at least within the limits of computational accuracy.

Due to the nature of the singularities in the regular slog at 0 and 1, the kslog becomes rather difficult to compute accurately.

However, after tweaking and experimenting and tweaking some more, I've found a setup that yields decent accuracy, to at least 20-25 bits over most of the unit interval.

In order to prevent my results from being biased by my preference for the intuitive slog, I initially parameterized the unit interval with a second-order polynomial:
(-2*sqrt(6) + 6)*z + R(6*sqrt(6)-15)*z^2 + R(-4*sqrt(6)+10)*z^3

This was done to ensure a continuous second derivative on the boundary of the region that I was trying to map to the unit disk (for the riemann mapping phase). The singularity probably makes this step unnecessary, but I felt it better to be safe than sorry. I did not try to make the initial parameterization any more "accurate" than this, as this might introduce bias into the results (e.g., if I merely used the isexp as the parameterization).

I calculated 2835 equally spaced points along the parameterized boundary, which is 27*105. This allowed me to solve systems with 105, 315, 945, and 2835 points, and monitor the convergence. The 105 allows me to break the point set into groups of 6, 10, or 14 intervals, in order to compute the integrals more accurately (more on that later).

Incidentally, convergence is slow, yielding just under 3 bits of precision for each tripling of system size. This more or less corresponds to 2 bits per doubling, compared with about 6 bits per system doubling for my accelerated islog solution.

On the other hand, the kslog is extremely numerically stable. A 1200x1200 system for the accelerated islog requires about 1600 bits of precision just to "break even", while the kslog requires about 11-15 bits for the same size system.

Anyway, before I start getting into the gritty details (some of which I'll probably not get to until tomorrow), I wanted to post my comparison of the kslog and the islog.

The SAGE plotting library refuses to label the axes on this graph, so I drew light grey lines at intervals of 10^-7, with a darker line at 10^-6. As you can see, the accuracy over most of the unit interval is about 10^-7, about 23 bits' worth, which is about how accurate the computed kslog is (based on convergence analysis). So roughly to within the accuracy of the calculations, the kslog and the islog are probably the same. The error is at most an order of magnitude larger than I expected, based on convergence analysis, so I'm not ready to declare this issue settled just yet. I'm still trying to tune my matrix system, which is temperamental due to the singularities.

This graph is the difference between the 2835 kslog points I computed and the islog at the same points, setting kslog(0.5)=islog(0.5).


Note that due to the way the kslog is calculated, I cannot find a value for kslog(0) or kslog(1), so there's not an obvious way to compare the kslog and islog directly, other than to try to reduce the RMS error for all 2835 points. The derivatives can be compared directly, and I'll be trying that next.
~ Jay Daniel Fox

Messages In This Thread
Attempting to compute the kslog numerically (i.e., Kneser's construction) - by jaydfox - 09/24/2009, 12:03 AM

Possibly Related Threads...
Thread Author Replies Views Last Post
  Kneser-iteration on n-periodic-points (base say \sqrt(2)) Gottfried 11 5,097 05/05/2021, 04:53 AM
Last Post: Gottfried
  fast accurate Kneser sexp algorithm sheldonison 38 117,899 01/14/2016, 05:05 AM
Last Post: sheldonison
  "Kneser"/Riemann mapping method code for *complex* bases mike3 2 10,284 08/15/2011, 03:14 PM
Last Post: Gottfried
  Attempt to make own implementation of "Kneser" algorithm: trouble mike3 9 24,830 06/16/2011, 11:48 AM
Last Post: mike3
  An incremental method to compute (Abel) matrix inverses bo198214 3 13,395 07/20/2010, 12:13 PM
Last Post: Gottfried

Users browsing this thread: 1 Guest(s)