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 userdefined functions, as part of the
SFT methods input, for the functionquery (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 (Z_{N1} x ... x Z_{Nk})
described by a list of N_{j}'s or an Abelian group described by a list of N_{j}'s and the
corresponding generators g_{j}'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 {xy  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 m_{A} and sets Btl are defined to be of maximum size of m_{B}.
The user is given two options to determine m_{A} and m_{B}: either give these variables directly or the more precise
way by giving the algorithm all parameters needed to calculate m_{A} and m_{B} as described in the paper (p. 57):
m_{A} = Θ((f_{∞}/η)^{2} * ln(1/δ)),
m_{B} = Θ((f_{∞}/η)^{2} * ln(f_{∞}/δγ))
where δ = δ'/Θ(1/τ * (f_{2}^{2}/τ)^{1.5} * logG),
η = Θ(min{γ, √γ, γ/f_{∞}})
The second option usage requires: δ', f_{2}, f_{∞}, the constant for the tightbound in δ calculation,
the constants for the tightbounds in m_{A} and m_{B} calculation and the constant for the tightbound in η calculation.

Number of iterations: the simpler method, the one using a given m_{A} and m_{B}, 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 ƒƒ_{i1}:
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 Z_{N1} x ... x Z_{Nk} → 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 SFTsuitable 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 = (Z
_{1000})
^{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.58525685124362410.4017816116061057i
Element: (230,100,20,19) Coefficient: 0.63603230655651671.4501748131307315i
Element: (142,80,500,791) Coefficient: 19.712055953206114+122.17770292054499i
Element: (230,100,20,21) Coefficient: 0.360756524427689633.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