Make illustrative plots for BKZ's behaviour

bkz_plot.py

# -*- coding: utf-8 -*-
"""
Illustrate behaviour of BKZ algorithm.

.. modulauthor: Martin Albrecht <martin.albrecht@royalholloway.ac.uk>

To convert to movie, call e.g. `ffmpeg -framerate 8 -pattern_type glob -i "*.png" bkz.mkv`

"""

from fpylll.tools.bkz_stats import dummy_tracer
from fpylll.algorithms.bkz2 import BKZReduction as BKZ2
from fpylll import BKZ

import matplotlib.pyplot as plt
from math import log, pi, e
import matplotlib.patches as patches


class PlotBKZ(BKZ2):
    def __call__(self, params, min_row=0, max_row=-1):
        self.M.update_gso()
        self._plots = [self.M.r()]
        self._toplevel = True
        BKZ2.__call__(self, params, min_row, max_row)
        self.M.update_gso()
        self._plots.append(self.M.r())

    def svp_reduction(self, kappa, block_size, params, tracer=dummy_tracer):
        _toplevel = self._toplevel
        self._toplevel = False
        r = BKZ2.svp_reduction(self, kappa, block_size, params, tracer=dummy_tracer)
        self._toplevel = _toplevel
        if _toplevel:
            self.M.update_gso()
            self._plots[-1].append(self.M.r())
        return r

    def tour(self, params, min_row=0, max_row=-1, tracer=dummy_tracer):
        if self._toplevel:
            self._plots.append([])
        return BKZ2.tour(self, params, min_row, max_row, tracer)


def log_line(l):
    return [log(l[i], 2) for i in range(len(l))]


def gso_plot(tours, block_size, basename="foo"):

    d = len(tours[0])
    x = range(d)

    beta = float(block_size)
    delta_0 = (beta/(2.*pi*e) * (pi*beta)**(1./beta))**(1./(2.*beta-1.))
    alpha = delta_0**(-2.*d/(d-1.))
    logvol = sum(log_line(tours[0]))  # already squared
    gsa = [log(alpha, 2)*(2*i) + log(delta_0, 2)*(2*d) + logvol*(1./d) for i in range(d)]

    print gsa[0]

    fig, ax = plt.subplots()
    ax.plot(x, log_line(tours[0]))

    ax.set_ylabel("$\\log_2 \\mathbf{b}_i^*$")
    ax.set_xlabel("$i$")
    ylim = ax.get_ylim()

    fig.savefig("%s-aaa.png"%basename, dpi=300)
    plt.close()

    for i, tour in enumerate(tours[1:-1]):
        for kappa, norms in enumerate(tour):
            fig, ax = plt.subplots()

            rect = patches.Rectangle((kappa, ylim[0]), min(block_size, d-kappa-1), ylim[1]-ylim[0],
                                     fill=True, color="lightgray")
            ax.add_patch(rect)
            ax.plot(x, log_line(norms), label="$\\mathbf{b}_i^*$")
            ax.plot(x, gsa, color="black", label="GSA")
            ax.set_ylabel("$\\log_2(\\cdot)$")
            ax.set_xlabel("$i$")
            ax.set_ylim(*ylim)
            ax.legend(loc='upper right')
            ax.set_title("BKZ tour: %2d, $\\kappa$: %3d"%(i, kappa))
            fig.savefig("%s-t%03d-k%04d.png"%(basename, i, kappa), dpi=300)
            plt.close()

    fig, ax = plt.subplots()
    ax.plot(x, log_line(tours[-1]))

    ax.set_ylabel("$\\log_2 \\mathbf{b}_i^*$")
    ax.set_xlabel("$i$")
    ylim = ax.get_ylim()

    fig.savefig("%s-zzz.png"%basename, dpi=300)
    plt.close()


def run(d=150, block_size=60):
    from fpylll import IntegerMatrix
    A = IntegerMatrix.random(d, "qary", bits=30, k=d//2)
    bkz = PlotBKZ(A)
    bkz(BKZ.EasyParam(block_size, flags=BKZ.VERBOSE, max_loops=8))
    gso_plot(bkz._plots, block_size)