The SFT Algorithm


Browse this site: Home | Java Usage | Matlab Usage

Learning and Coding Theory Workshop

The Java SFT Library

Summary

The Java SFT library allows users to use the public SFT methods for calculating a list of elements with significant Fourier coefficients, and an approximation of these coefficients. The library includes two public packages:
  • SFT: main package, includes the SFT implementation.
  • Function: a package with data structures to describe general user-defined functions, as part of the SFT methods input, for the function-query (see the paper for details).
The SFT main package allows the user to call the SFT calculation in 6 variations:
  • Function domain: input function is either Cartesian product of finite groups (ZN1 x ... x ZNk) described by a list of Nj's or an Abelian group described by a list of Nj's and the corresponding generators gj's.
  • Random subsets calculation method: as detailed in the paper, the approximation is based on a set of elements in G, Q, which is defined as {x-y | x in A, y in Btl, t=1,...,k, l=1,...,log(Nt)}, where A and Btl are randomly generated sets of elements in G. Set A is of defined to be of size mA and sets Btl are defined to be of maximum size of mB.
    The user is given two options to determine mA and mB: either give these variables directly or the more precise way by giving the algorithm all parameters needed to calculate mA and mB as described in the paper (p. 57):
    mA = Θ((||f||∞/η)2 * ln(1/δ)), mB = Θ((||f||∞/η)2 * ln(||f||∞/δγ))
    where δ = δ'/Θ(1/τ * (||f||22/τ)1.5 * log|G|), η = Θ(min{γ, √γ, γ/||f||∞})

    The second option usage requires: δ', ||f||2, ||f||∞, the constant for the tight-bound in δ calculation, the constants for the tight-bounds in mA and mB calculation and the constant for the tight-bound in η calculation.
  • Number of iterations: the simpler method, the one using a given mA and mB, has an optional numOfIterations parameter. This parameter is for a suggested improvement for the percision of the SFT output. If the given number of iterations is bigger than 1, each iteration i reruns the SFT significant elements calculation over the same generated Q, over the difference function ƒ-ƒi-1: the difference between the given function and the output function of the previous iteration.
    The more complex method must accept this parameter (not an option).
The Function package allows the user to define a function object to be sent as the query access in the SFT implementation. Hierarchy:
  • Abstract class Function:
    The basic function object, has two abstract extensions corresponding to the different optional function domain: Cartesian product of finite groups or Abelian group. There are three main procedures for this object: getValue, calcInfinityNorm and calcEuclideanNorm.
    • Abstract class DirectProdFunction: an abstract extension to class Function, for describing functions over ZN1 x ... x ZNk → C. It provides a naive implementation of the calcInfinityNorm and calcEuclideanNorm that are not recommended for use (very long calculation that iterates over all the elements in G).
      The Function package also includes two implementations for the DirectProdFunction:
      • Class FourierPolynomial: extends class DirectProdFunction and describes a Fourier polynomial by a list of terms and their coefficients, i.e. for a Fourier polynomial:
        p(x) = ∑cα•Χα(x) it holds the mapping of α to its coefficient cα.
      • Class XMLFourierPolynomial: extends class DirectProdFunction and describes a Fourier polynomial as class FourierPolynomial, allowing the user to construct it from a XML description of the function. In addition this implementation can receive multiple functions in one XML, and let the user choose which of the functions to use or randomly choose a function from the given list at each calculation.
    • Abstract class FiniteAbelianFunction: an abstract extension to class Function, for describing functions over a finite Abelian group G → C.

Usage

In order to use the SFT library in your Java project, follow these steps:
  • Download: download the SFT jar file (link below under Tools and Downloads).
  • Import: import the library into your Java project.
  • Use: import SFT.* and Function.* in your Java code and start using it! use the Function documentation to understand how to describe your function as a SFT-suitable input.

Example:
This example demonstrates how to use the SFT in java, using a XMLFourierPolynomial input function generated from: sample.xml. The code will use this XML function as over G = (Z1000)4.
Remark: The SFT algorithm works best with consentrated functions, where usually τ is in (0,1).
Download Java code example

import SFT.*;
import Function.*;
import java.io.*;
import java.util.*;

public class Test{
  public static void main(String[] args) throws Exception{
    long[] G = new long[]{1000, 1000, 1000, 1000};
    int numOfIterations = 1;
    double tau = 50000;
    long ma = 10;
    long mb = 10;
    String filename = "sample.xml";

    // create function from XML file
    DirectProdFunction p = new XMLFourierPolynomial(new File(filename), G);

    // RUN THE SFT ALGORITHM TO APPROXIMATE THE FUNCTION
    Map<long[],Complex> res =
        SFT.getSignificantElements(G,tau,p,ma,mb,numOfIterations);

    System.out.println("The result of the SFT is:");
    for(long[] elem: res.keySet()){
      System.out.println("\tElement: "+SFTUtils.vectorToString(elem)+"\tCoefficient: "+res.get(elem));
    }
  }
}

The output of the above is:

The result of the SFT is:
    Element: (142,80,500,792) Coefficient: -0.5852568512436241-0.4017816116061057i
    Element: (230,100,20,19) Coefficient: -0.6360323065565167-1.4501748131307315i
    Element: (142,80,500,791) Coefficient: 19.712055953206114+122.17770292054499i
    Element: (230,100,20,21) Coefficient: 0.36075652442768963-3.075836040923196i
    Element: (230,100,20,20) Coefficient: 101.81471066738774+131.48304965709386i

As it can be seen, the output is very close to the real elements and their coefficients: (142,80,500,791) with coefficient 19+120i, and (230,100,20,20) with coefficient 101+130i. Although additional elements passed the threshold, the coefficients generated for them are insignificant.

Tools and Downloads:

Browse this site: Home | Java Usage | Matlab Usage
Created by Elizabeth Firman & Ariel Stolerman, CS Workshop, TAU Spring 2010