public class IntTwoPassFNTStrategy extends IntParallelFNTStrategy
The "two-pass" algorithm only needs to do two passes through the data set. In comparison, a basic FFT algorithm of length 2n needs to do n passes through the data set. Although the algorithm is fairly optimal in terms of amount of data transferred between the mass storage and main memory, the mass storage access is not linear but done in small incontinuous pieces, so due to disk seek times the performance can be quite lousy.
When the data to be transformed is considered to be an n1 x n2 matrix of data, instead of a linear array, the two passes go as follows:
When reading the column data to be transformed, the data can be transposed to rows by reading the b-length blocks to proper locations in memory and then transposing the b x b blocks.
In a convolution algorithm the data elements can remain in any order after the transform, as long as the inverse transform can transform it back. The convolution's element-by-element multiplication is not sensitive to the order in which the elements are, of course.
This algorithm is parallelized so that the row transforms are done in parallel
using multiple threads, if the number of processors is greater than one
in ApfloatContext.getNumberOfProcessors()
.
This transform uses the maximum amount of memory available as retrieved from
ApfloatContext.getMaxMemoryBlockSize()
. All access on memory is synchronized on
the shared memory lock retrieved from ApfloatContext.getSharedMemoryLock()
.
All access to this class must be externally synchronized.
DataStorage.getTransposedArray(int,int,int,int)
parallelRunner
Constructor and Description |
---|
IntTwoPassFNTStrategy()
Default constructor.
|
Modifier and Type | Method and Description |
---|---|
void |
inverseTransform(DataStorage dataStorage,
int modulus,
long totalTransformLength)
Perform an inverse transform on the data.
|
void |
transform(DataStorage dataStorage,
int modulus)
Perform a forward transform on the data.
|
multiplyElements, setParallelRunner, transformRows
getTransformLength, inverseTableFNT, tableFNT
createWTable, getForwardNthRoot, getInverseNthRoot, modDivide, modInverse, modPow, negate
getModulus, modAdd, modMultiply, modSubtract, setModulus
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
getTransformLength
public void transform(DataStorage dataStorage, int modulus) throws ApfloatRuntimeException
NTTStrategy
Multiple moduli can be used, if the convolution algorithm uses the Chinese Remainder Theorem to calculate the final result.
transform
in interface NTTStrategy
transform
in class IntTableFNTStrategy
dataStorage
- The data to be transformed.modulus
- Number of modulus to use (in case the transform supports multiple moduli).ApfloatRuntimeException
public void inverseTransform(DataStorage dataStorage, int modulus, long totalTransformLength) throws ApfloatRuntimeException
NTTStrategy
Multiple moduli can be used, if the convolution algorithm uses the Chinese Remainder Theorem to calculate the final result.
inverseTransform
in interface NTTStrategy
inverseTransform
in class IntTableFNTStrategy
dataStorage
- The data to be transformed.modulus
- Number of modulus to use (in case the transform supports multiple moduli).totalTransformLength
- Total transform length; the final result elements are divided by this value.ApfloatRuntimeException
Copyright © 2011. All Rights Reserved.