* @param omega root of unity, can be 2 or 4
     * @param numThreads number of threads to use; 1 means run on the current thread
     */
    private static void idftParallel(final MutableModFn[] A, final int omega, int numThreads) throws InterruptedException, ExecutionException {
        // arrange the elements of A in a matrix roughly sqrt(A.length) by sqrt(A.length) in size
        final int rows = 1 << ((31-Integer.numberOfLeadingZeros(A.length))/2);   // number of rows
        final int cols = A.length / rows;   // number of columns

        ExecutorService executor = Executors.newFixedThreadPool(numThreads);

        // step 1: perform an IDFT on each row
        Collection<Future<?>> pending = new ArrayList<>();
        for (int i=0; i<rows; i++) {
            final int rowIdx = i;
            Future<?> future = executor.submit(new Runnable() {
                @Override
                public void run() {
                    idftDirect(A, omega, cols, 0, rows, rowIdx*cols, 1);
                }
            });
            pending.add(future);
        }
        for (Future<?> future: pending)
            future.get();

        // step 2: multiply by powers of omega
        applyIdftWeights(A, omega, rows, cols);

        // step 3 is built into step 4 by making the stride length a multiple of the row length
        // step 4: perform an IDFT on each column
        pending = new ArrayList<>();
        for (int i=0; i<cols; i++) {
            final int colIdx = i;
            Future<?> future = executor.submit(new Runnable() {
                @Override
                public void run() {
                    idftDirect(A, omega, rows, rows, cols, colIdx, cols);
                }
            });
            pending.add(future);
        }
        for (Future<?> future: pending)
            future.get();

        executor.shutdown();
    }