Matrix Factorizations for Parallel Integer Transformation

Integer mapping is critical for lossless source coding and has been used for multicomponent image compression in the new international image compression standard JPEG 2000. In this paper, starting from block factorizations for any nonsingular transform matrix, we introduce two types of parallel elementary reversible matrix (PERM) factorizations which are helpful for the parallelization of perfectly reversible integer transforms. With improved degree of parallelism and parallel performance, the cost of multiplications and additions can be, respectively, reduced to O(logN) and O(log²N) for an N by N transform matrix. These make PERM factorizations an effective means of developing parallel integer transforms for large matrices. We also present a scheme to block the matrix and allocate the load of processors for efficient transformation