HW5 Bit Battle Leaderboard

Performance Results

Last updated: 2026-04-09 23:01:20 EDT

Rank	Team Name	Error	Execution Time (seconds)
1	ctrl-alt-elite-repo	2e-16	17.0678
2	committhenpray	2e-15	6.8955
3	git-rich-soon-1	3e-15	1.8459
4	epiagent	5e-15	2.2047
5	standard-deviants	1e-14	4.4226
6	the-executors	5e-14	9.8845
7	404-brain-not-found	1e-13	0.7045
8	ele_aaa	9e-9	0.0498
9	git-er-done	2e-7	0.1400

Solutions

Both problems are from the SIAM 100-Digit Challenge. You can find all problems and solutions in Bornemann, Folkmar; Laurie, Dirk; Wagon, Stan; Waldvogel, Jörg (2004). The SIAM 100-digit challenge: A study in high-accuracy numerical computing.

The beauty of the two homework problems is that they can be solved both by straightforward linear algebra methods and can be accelerated by using some advanced mathematical tools like complex analysis. We strongly recommend you to read the solutions in the problem1_answer.pdf and problem2_answer.pdf files and we can promise you that you will learn a lot from them.

Problem 1

You can find the multiple solutions to this problem in the problem1_answer.pdf file.

In problem1.py, we implemented the power method combined with the Strebel’s summation formula to accelerate the convergence (See Section 3.5 in problem1_answer.pdf). It achieves the accuracy of 2e-16 within 0.074 seconds only for a 513 by 513 matrix.

Since we are implementing the power method, it involves the matrix-vector multiplication like

$$ (M x)_{j} = \sum_{k=1}^{\infty} M_{jk} x_k $$

Euler-Maclaurin formula aims to convert the infinite sum into a finite sum. Let us first consider the integral. We aim to find a one-to-one mapping $\phi: [1,n] \to [1,\infty)$ such that by change of the variable:

$$ \int_1^\infty f(x) dx = \int_1^n \phi'(x) f(\phi(x)) dx. $$

Our idea is to convert the infinite sum into a finite sum:

$$ \sum_{k=1}^\infty f(k) = \sum_{k=1}^{n-1} \phi_n'(k) f(\phi_n(k)) $$

So why using the right-hand side is better than computing the left-hand side truncated at $n$? We need to find a function $\phi_n$ such that the finite sum is closer to the integral on the right-hand side.

By the Euler-Maclaurin formula, we have

$$ \sum_{k=0}^{n} f(k) = \int_0^{n} f(x)dx + \frac{f(0) + f(n)}{2} + \sum_{j=1}^p \frac{B_{2j}}{(2j)!}[f^{(2j-1)}(n) - f^{(2j-1)}(0)] + R_{2p} $$

where $B_{2j}$ are the Bernoulli numbers and $R_{2p}$ is the remainder term such that

$$ |R_{2p}| \leq \frac{B_{2p}}{(2p)!} \int_0^n |f^{(2p)}(x)| dx. $$

Our goal is to find a function $\phi_n$ such that it has the smallest error in the Euler-Maclaurin formula.

Lemma (R. Strebel). Let $n$ be a positive integer and $f_n(x) = (x + n)^{-\alpha}$, $\alpha > 1$. The function

$$ \phi_n(\xi) = \frac{n^{1+\beta} (n - \xi)^{-\beta}}{\beta} - \frac{n}{\beta} - \frac{(1 + \beta) \xi^2}{2n}, \quad \beta = \frac{6}{\alpha - 1}, $$

is strictly increasing and maps $[0,n)$ onto $[0,\infty)$. Then

$$ \sum_{k=0}^{\infty} f_n(k) = \sum_{k=0}^{n-1} \phi_n'(k) \cdot f_n(\phi_n(k)) + O(n^{-3-\alpha}). $$

For problem 1, we roughly have $\alpha = 4$.

Choosing the following

$$ \phi_{\exp}(\xi) = \exp\left(\frac{2}{(1-u)^2} -\frac{1}{2u^2}\right) $$

will make even faster convergence, though it is hard to prove.

There are even faster approximation methods using the contour integral on the complex plane. See Section 3.6 in problem1_answer.pdf for more details.

Problem 2

You can find the multiple solutions to this problem in the problem2_answer.pdf file.

A key trick is that you can construct the matrix A by Kronecker product. See problem2.py for the implementation.