You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@systemds.apache.org by mb...@apache.org on 2026/09/29 10:34:01 UTC

(systemds) branch main updated: [SYSTEMDS-3547] Extended tensor transposition for sparse inputs

This is an automated email from the ASF dual-hosted git repository.

mboehm7 pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/systemds.git


The following commit(s) were added to refs/heads/main by this push:
     new 91af40100b [SYSTEMDS-3547] Extended tensor transposition for sparse inputs
91af40100b is described below

commit 91af40100b00ef0393701952ca9da9dc19ff16a8
Author: BeceHQ <ch...@gmail.com>
AuthorDate: Tue Sep 29 12:26:52 2026 +0200

    [SYSTEMDS-3547] Extended tensor transposition for sparse inputs
    
    Closes #2547.
---
 .../sysds/runtime/matrix/data/LibMatrixReorg.java  | 482 ++++++------
 .../matrix/libMatrixReorg/PermuteTest.java         | 869 ++++++++++++++++-----
 2 files changed, 901 insertions(+), 450 deletions(-)

diff --git a/src/main/java/org/apache/sysds/runtime/matrix/data/LibMatrixReorg.java b/src/main/java/org/apache/sysds/runtime/matrix/data/LibMatrixReorg.java
index 5f47897910..2b5cddd573 100644
--- a/src/main/java/org/apache/sysds/runtime/matrix/data/LibMatrixReorg.java
+++ b/src/main/java/org/apache/sysds/runtime/matrix/data/LibMatrixReorg.java
@@ -5004,8 +5004,8 @@ public class LibMatrixReorg {
 
 	/**
 	 * Restores SystemDS matrix/tensor metadata after an in-place tensor permutation.
-	 * @param in           matrix/tensor block whose metadata is restored
-	 * @param finalShape   final tensor shape after permutation
+	 * @param in         matrix/tensor block whose metadata is restored
+	 * @param finalShape final tensor shape after permutation
 	 */
 	private static void restoreMetadata(MatrixBlock in, int[] finalShape) {
 		in.setNumRows(finalShape[0]);
@@ -5016,7 +5016,7 @@ public class LibMatrixReorg {
 		if (in.getDenseBlock() != null)
 			in.getDenseBlock().setDims(finalShape);
 	}
-		
+
 	private static long[] getStridesForPermutation(int[] dims) {
 		long[] strides = new long[dims.length];
 		long stride = 1;
@@ -5027,23 +5027,33 @@ public class LibMatrixReorg {
 		return strides;
 	}
 
-	public static MatrixBlock permute(MatrixBlock in, int[] inDims, int[] perm) {
-		return permute(in, inDims, perm, 1);
+	public static MatrixBlock permute(MatrixBlock inData, int[] inDims, int[] perm) {
+		return permute(inData, inDims, perm, 1);
 	}
 
-	public static MatrixBlock permute(MatrixBlock in, int[] inDims, int[] perm, int k) {
+	public static MatrixBlock permute(MatrixBlock inData, int[] inDims, int[] perm, int k) {
+		//TODO Enable Pointers on first dim 
 		int rank = inDims.length;
 		
-		boolean isIdentity = true;
-		for( int i = 0; i < rank; i++ ) {
-			if( perm[i] != i ) {
-				isIdentity = false;
-				break;
+		if( perm.length != rank ) {
+			throw new DMLRuntimeException("Permutation array must have the same length as inDims.");
+		}
+
+		boolean[] seen = new boolean[rank];
+		for( int p : perm ) {
+			if( p < 0 || p >= rank || seen[p] ) {
+				throw new IllegalArgumentException("Invalid permutation. Indices might be out of bounds or duplicate dimensions were given.");
 			}
+			seen[p] = true;
 		}
 
-		if( isIdentity ) {
-			return new MatrixBlock(in);
+		long expectedLength = 1;
+		for( int d : inDims ) {
+			expectedLength *= d;
+		}
+		long actualLength = (long) inData.getNumRows() * inData.getNumColumns();
+		if( expectedLength != actualLength ) {
+			throw new DMLRuntimeException("Dimensions (inDims) do not match the actual number of elements in the matrix.");
 		}
 
 		int[] outDims = new int[rank];
@@ -5056,299 +5066,253 @@ public class LibMatrixReorg {
 			length *= d;
 		}
 
-		MatrixBlock out = new MatrixBlock(1, (int)length, false);
-		out.allocateDenseBlock();
+		boolean isSparse = inData.isInSparseFormat();
+		MatrixBlock outData = new MatrixBlock(1, (int) length, isSparse);
+		
+		if( isSparse ) {
+			int nnz = (int) inData.getNonZeros();
+			SparseBlockCSR csr = new SparseBlockCSR(1, nnz, nnz);
 
-		DenseBlock inDB = in.getDenseBlock();
-		DenseBlock outDB = out.getDenseBlock();
+			int[] rptr = csr.rowPointers();
+			rptr[0] = 0;
+			rptr[1] = nnz;
+			
+			outData.setSparseBlock(csr);
+		} else {
+			outData.allocateDenseBlock();
+		}
 
 		long[] inStrides = getStridesForPermutation(inDims);
 		long[] outStrides = getStridesForPermutation(outDims);
-		
-		long[] permutedStrides = new long[rank];
+
+		int[] inversePermute = new int[rank];
 		for( int i = 0; i < rank; i++ ) {
-			permutedStrides[i] = outStrides[perm[i]];
+			inversePermute[perm[i]] = i;
 		}
 
-		boolean useParallel = (k > 1 || k == -1) && length >= PAR_NUMCELL_THRESHOLD;
-		int numThreads = k == -1 ? Runtime.getRuntime().availableProcessors() : k;
-
-		if( inDB.numBlocks() == 1 && outDB.numBlocks() == 1 ) {
-			double[] inData = inDB.valuesAt(0);
-			double[] outData = outDB.valuesAt(0);
-			
-			if( useParallel && rank > 0 ) {
-				permuteSingleBlockParallel(inData, outData, inDims, inStrides, 
-					permutedStrides, numThreads, length);
-			} else {
-				permuteSingleBlock(inData, outData, inDims, inStrides, 
-					permutedStrides, 0, 0, 0);
-			}
-		} else {
-			if( useParallel && rank > 0 ) {
-				permuteMultiBlockParallel(inDB, outDB, inDims, inStrides, 
-					permutedStrides, numThreads, length);
-			} else {
-				permuteMultiBlock(inDB, outDB, inDims, inStrides, 
-					permutedStrides, 0, 0L, 0L);
-			}
+		long[] permutedOutStrides = new long[rank];
+		for( int i = 0; i < rank; i++ ) {
+			permutedOutStrides[i] = outStrides[inversePermute[i]];
 		}
-		return out;
-	}
 
-	private static void permuteSingleBlock(
-		double[] inData, double[] outData,
-		int[] inDims, long[] inStrides, long[] permutedStrides,
-		int dim, int inOffset, int outOffset) 
-	{
-		if( dim == inDims.length - 1 ) {
-			int len = inDims[dim];
-			int outStride = (int) permutedStrides[dim];
+		int rlen = inData.getNumRows();
+		int numThreads = k == -1 ? InfrastructureAnalyzer.getLocalParallelism() : k;
+		boolean useParallel = (numThreads > 1) && (length >= PAR_NUMCELL_THRESHOLD);
+
+		int[] cnt = null;
+		int[] outIndexes = null;
+		double[] outValues = null;
 
-			if( outStride == 1 ) {
-				System.arraycopy(inData, inOffset, outData, outOffset, len);
+		if( isSparse ) {
+			SparseBlockCSR csr = (SparseBlockCSR) outData.getSparseBlock();
+			outIndexes = csr.indexes();
+			outValues = csr.values();
+		}
+
+		if( !useParallel ) {
+			if( isSparse ) {
+				cnt = new int[]{0};
+				permuteSparseKernel(inData, inStrides, permutedOutStrides, 0, rlen, cnt, outIndexes, outValues, 0);
 			} else {
-				transposeRow(inData, outData, inOffset, outOffset, outStride, len);
+				permuteDenseKernel(inData, outData, inStrides, permutedOutStrides, 0, rlen);
 			}
-			return;
+		} else {
+			permuteMultiThreaded(inData, outData, inStrides, permutedOutStrides, rlen, numThreads, outIndexes, outValues);
 		}
 
-		int dimSize = inDims[dim];
-		long inStep = inStrides[dim];
-		long outStep = permutedStrides[dim];
-
-		final int BLOCK_SIZE = 128;
-		for( int bi = 0; bi < dimSize; bi += BLOCK_SIZE ) {
-			int bimin = Math.min(bi + BLOCK_SIZE, dimSize);
-			for( int i = bi; i < bimin; i++ ) {
-				permuteSingleBlock(
-						inData, outData, inDims, inStrides, permutedStrides,
-						dim + 1,
-						inOffset + (int)(i * inStep),
-						outOffset + (int)(i * outStep)
-				);
-			}
+		outData.recomputeNonZeros(); 
+		if( isSparse ) {
+			outData.sortSparseRows();
 		}
+		return outData;		
 	}
 
-	private static void permuteSingleBlockParallel(
-			double[] inData, double[] outData,
-			int[] inDims, long[] inStrides, long[] permutedStrides,
-			int k, long totalElements) {
-		
-		final long elementsPerThread = Math.max(1024, (totalElements + k - 1) / k);
-		final int actualThreads = (int) Math.min(k, (totalElements + elementsPerThread - 1) / elementsPerThread);
-		
-		final ExecutorService pool = CommonThreadPool.get(actualThreads);
+	private static void permuteMultiThreaded(MatrixBlock inData, MatrixBlock outData,
+			long[] inStrides, long[] permutedOutStrides, int rlen, int k,
+			int[] outIndexes, double[] outValues) 
+	{
+		ExecutorService pool = CommonThreadPool.get(k);
 		try {
-			final ArrayList<PermuteSingleBlockTask> tasks = new ArrayList<>();
+			ArrayList<PermuteTask> tasks = new ArrayList<>();
+			int blklen = (int) Math.ceil((double) rlen / k);
 			
-			for( int t = 0; t < actualThreads; t++ ) {
-				final long start = t * elementsPerThread;
-				final long end = Math.min(start + elementsPerThread, totalElements);
-				
-				if( start >= totalElements ) {
-					break;
+			int[] cnt = null;
+			SparseBlock inSB = null;
+			int currentOffset = 0;
+
+			if( inData.isInSparseFormat() ) {
+				cnt = new int[k];
+				inSB = inData.getSparseBlock();
+			}
+
+			for( int i = 0; i < k && i * blklen < rlen; i++ ) {
+				int rl = i * blklen;
+				int ru = Math.min((i + 1) * blklen, rlen);
+
+				if( cnt != null && inSB != null ) {
+					cnt[i] = currentOffset;
+					for( int r = rl; r < ru; r++ ) {
+						if( !inSB.isEmpty(r) ) {
+							currentOffset += inSB.size(r);
+						}
+					}
 				}
-				
-				tasks.add(new PermuteSingleBlockTask(inData, outData, inDims, 
-					inStrides, permutedStrides, start, end));
+				tasks.add(new PermuteTask(inData, outData, inStrides, permutedOutStrides, rl, ru, 
+										  cnt, outIndexes, outValues, i));
 			}
 
 			for( Future<Object> task : pool.invokeAll(tasks) ) {
 				task.get();
 			}
-		} catch (Exception ex) {
+
+		} 
+		catch( Exception ex ) {
 			throw new DMLRuntimeException(ex);
-		} finally {
+		} 
+		finally {
 			pool.shutdown();
 		}
 	}
 
-	private static void permuteMultiBlock(
-		DenseBlock inDB, DenseBlock outDB,
-		int[] inDims, long[] inStrides, long[] permutedStrides,
-		int dim, long inOffset, long outOffset) {
-
-		if( dim == inDims.length - 1 ) {
-			int len = inDims[dim];
-			long outStride = permutedStrides[dim];
-			
-			int inBlockSize = inDB.blockSize();
-			int outBlockSize = outDB.blockSize();
-
-			for( int i = 0; i < len; i++ ) {
-				long currentInAbs = inOffset + i * inStrides[dim];
-				long currentOutAbs = outOffset + i * outStride;
-				
-				int inBlockIdx = (int) (currentInAbs / inBlockSize);
-				int inRelIdx = (int) (currentInAbs % inBlockSize);
-				
-				int outBlockIdx = (int) (currentOutAbs / outBlockSize);
-				int outRelIdx = (int) (currentOutAbs % outBlockSize);
-				
-				double[] inArr = inDB.valuesAt(inBlockIdx);
-				double[] outArr = outDB.valuesAt(outBlockIdx);
-				
-				if( inArr != null && outArr != null && 
-					inRelIdx < inArr.length && outRelIdx < outArr.length ) {
-					outArr[outRelIdx] = inArr[inRelIdx];
-				}
-			}
-			return;
+	private static class PermuteTask implements Callable<Object> {
+		private final MatrixBlock _inData;
+		private final MatrixBlock _outData;
+		private final long[] _inStrides;
+		private final long[] _permutedOutStrides; 
+		private final int _rl;
+		private final int _ru; 
+		private final int[] _cnt;
+		private final int[] _outIndexes;
+		private final double[] _outValues;
+		private final int _taskID;
+
+		protected PermuteTask(MatrixBlock inData, MatrixBlock outData, long[] inStrides, 
+				long[] permutedOutStrides, int rl, int ru,
+				int[] cnt, int[] outIndexes, double[] outValues, int taskID) {
+			_inData = inData;
+			_outData = outData;
+			_inStrides = inStrides;
+			_permutedOutStrides = permutedOutStrides;
+			_rl = rl;
+			_ru = ru;
+			_cnt = cnt;
+			_outIndexes = outIndexes;
+			_outValues = outValues;
+			_taskID = taskID;
 		}
 
-		int dimSize = inDims[dim];
-		long inStep = inStrides[dim];
-		long outStep = permutedStrides[dim];
-
-		final int BLOCK_SIZE = 128;
-		for( int bi = 0; bi < dimSize; bi += BLOCK_SIZE ) {
-			int bimin = Math.min(bi + BLOCK_SIZE, dimSize);
-			for( int i = bi; i < bimin; i++ ) {
-				permuteMultiBlock(
-					inDB, outDB, inDims, inStrides, permutedStrides,
-					dim + 1,
-					inOffset + i * inStep,
-					outOffset + i * outStep
-				);
+		@Override
+		public Object call() {
+			if( _inData.isInSparseFormat() ) {
+				permuteSparseKernel(_inData, _inStrides, _permutedOutStrides, _rl, _ru, 
+									_cnt, _outIndexes, _outValues, _taskID);
+			} else {
+				permuteDenseKernel(_inData, _outData, _inStrides, _permutedOutStrides, _rl, _ru);
 			}
+			return null;
 		}
 	}
 
-	private static void permuteMultiBlockParallel(
-			DenseBlock inDB, DenseBlock outDB,
-			int[] inDims, long[] inStrides, long[] permutedStrides,
-			int k, long totalElements) {
-		
-		final long elementsPerThread = Math.max(1024, (totalElements + k - 1) / k);
-		final int actualThreads = (int) Math.min(k, (totalElements + elementsPerThread - 1) / elementsPerThread);
+	private static void permuteDenseKernel(MatrixBlock inData, MatrixBlock outData,
+			long[] inStrides, long[] permutedOutStrides, int rl, int ru) {
 
-		final ExecutorService pool = CommonThreadPool.get(actualThreads);
-		try {
-			final ArrayList<PermuteMultiBlockTask> tasks = new ArrayList<>();
-			
-			for( int t = 0; t < actualThreads; t++ ) {
-				final long start = t * elementsPerThread;
-				final long end = Math.min(start + elementsPerThread, totalElements);
-				
-				if( start >= totalElements ) {
-					break;
-				}
-				
-				tasks.add(new PermuteMultiBlockTask(inDB, outDB, inDims, 
-					inStrides, permutedStrides, start, end));
-			}
+		final int rank = inStrides.length;
+		final int clen = inData.getNumColumns();
 
-			for( Future<Object> task : pool.invokeAll(tasks) ) {
-				task.get();
-			}
+		DenseBlock inDB = inData.getDenseBlock();
+		DenseBlock outDB = outData.getDenseBlock();
 
-		} catch (Exception ex) {
-			throw new DMLRuntimeException(ex);
-		} finally {
-			pool.shutdown();
-		}
-	}
+		// blocking according to typical L2 cache sizes
+		final int blocksizeI = 128;
+		final int blocksizeJ = 128;
 
-	private static class PermuteSingleBlockTask implements Callable<Object> {
-		//TODO call single-threaded kernel for block
-		
-		private final double[] inData;
-		private final double[] outData;
-		private final int[] inDims;
-		private final long[] inStrides;
-		private final long[] permutedStrides;
-		private final long start;
-		private final long end;
-		
-		protected PermuteSingleBlockTask(double[] inData, double[] outData,
-				int[] inDims, long[] inStrides, long[] permutedStrides,
-				long start, long end) {
-			this.inData = inData;
-			this.outData = outData;
-			this.inDims = inDims;
-			this.inStrides = inStrides;
-			this.permutedStrides = permutedStrides;
-			this.start = start;
-			this.end = end;
-		}
-		
-		@Override
-		public Object call() {
-			for( long idx = start; idx < end; idx++ ) {
-				long inIdx = 0;
-				long outIdx = 0;
-				long remaining = idx;
-				
-				for( int d = 0; d < inDims.length; d++ ) {
-					long coord = remaining / inStrides[d];
-					remaining = remaining % inStrides[d];
-					inIdx += coord * inStrides[d];
-					outIdx += coord * permutedStrides[d];
+		for( int bi = rl; bi < ru; bi += blocksizeI ) {
+			int bimin = Math.min(bi + blocksizeI, ru);
+			for( int bj = 0; bj < clen; bj += blocksizeJ ) {
+				int bjmin = Math.min(bj + blocksizeJ, clen);
+
+				// core block permute operation
+				for( int i = bi; i < bimin; i++ ) {
+					double[] avals = inDB.values(i);
+					int apos = inDB.pos(i);
+
+					for( int j = bj; j < bjmin; j++ ) {
+						double val = avals[apos + j];
+						if( val == 0 )
+							continue;
+
+						long linearInIdx = (long) i * clen + j;
+						long remaining = linearInIdx;
+						long targetOutIdx = 0;
+
+						for( int d = 0; d < rank; d++ ) {
+							long coord = remaining / inStrides[d];
+							remaining %= inStrides[d];
+							targetOutIdx += coord * permutedOutStrides[d];
+						}
+
+						outDB.set(0, (int) targetOutIdx, val);
+					}
 				}
-				
-				outData[(int)outIdx] = inData[(int)inIdx];
 			}
-			return null;
 		}
 	}
 
-	private static class PermuteMultiBlockTask implements Callable<Object> {
-		//TODO call single-threaded kernel for block
-		
-		private final DenseBlock inDB;
-		private final DenseBlock outDB;
-		private final int[] inDims;
-		private final long[] inStrides;
-		private final long[] permutedStrides;
-		private final long start;
-		private final long end;
-		
-		protected PermuteMultiBlockTask(DenseBlock inDB, DenseBlock outDB,
-				int[] inDims, long[] inStrides, long[] permutedStrides,
-				long start, long end) {
-			this.inDB = inDB;
-			this.outDB = outDB;
-			this.inDims = inDims;
-			this.inStrides = inStrides;
-			this.permutedStrides = permutedStrides;
-			this.start = start;
-			this.end = end;
-		}
-		
-		@Override
-		public Object call() {
-			int inBlockSize = inDB.blockSize();
-			int outBlockSize = outDB.blockSize();
-			
-			for( long idx = start; idx < end; idx++ ) {
-				long inIdx = 0;
-				long outIdx = 0;
-				long remaining = idx;
-				
-				for( int d = 0; d < inDims.length; d++ ) {
-					long coord = remaining / inStrides[d];
-					remaining = remaining % inStrides[d];
-					inIdx += coord * inStrides[d];
-					outIdx += coord * permutedStrides[d];
-				}
-				
-				int inBlockIdx = (int) (inIdx / inBlockSize);
-				int inRelIdx = (int) (inIdx % inBlockSize);
-				
-				int outBlockIdx = (int) (outIdx / outBlockSize);
-				int outRelIdx = (int) (outIdx % outBlockSize);
-				
-				double[] inArr = inDB.valuesAt(inBlockIdx);
-				double[] outArr = outDB.valuesAt(outBlockIdx);
-				
-				if( inArr != null && outArr != null && 
-					inRelIdx < inArr.length && outRelIdx < outArr.length ) {
-					outArr[outRelIdx] = inArr[inRelIdx];
+	private static void permuteSparseKernel(MatrixBlock inData,
+			long[] inStrides, long[] permutedOutStrides, int rl, int ru,
+			int[] cnt, int[] outIndexes, double[] outValues, int taskID) {
+
+		SparseBlock inSB = inData.getSparseBlock();
+		if( inSB == null ) return;
+
+		final int rank = inStrides.length;
+		final int clen = inData.getNumColumns();
+
+		// blocking according to typical L2 cache sizes with awareness of sparsity
+		final long nnz = inData.getNonZeros();
+		final long xsp = (nnz == 0) ? 1L : ((long) inData.getNumRows() * clen) / nnz;
+		final int blocksizeI = Math.min(Math.max(128, (int) (8 * xsp)), 512);
+
+		// temporary array for block boundaries (for preventing binary search)
+		final int[] ix = new int[Math.min(blocksizeI, ru - rl)];
+
+		// blocked execution
+		for( int bi = rl; bi < ru; bi += blocksizeI ) {
+			Arrays.fill(ix, 0);
+			// find column starting positions
+			int bimin = Math.min(bi + blocksizeI, ru);
+
+			for( int bj = 0; bj < clen; bj += blocksizeI ) {
+				final int bjmin = Math.min(bj + blocksizeI, clen);
+				// core block permute operation
+				for( int i = bi; i < bimin; i++ ) {
+					if( inSB.isEmpty(i) ) continue;
+
+					final int apos = inSB.pos(i);
+					final int alen = inSB.size(i);
+					final int[] aix = inSB.indexes(i);
+					final double[] avals = inSB.values(i);
+					int j = ix[i - bi] + apos; // last block boundary
+					for( ; j < apos + alen && aix[j] < bjmin; j++ ) {
+						long linearInIdx = (long) i * clen + aix[j];
+						long remaining = linearInIdx;
+						long targetOutIdx = 0;
+
+						for( int d = 0; d < rank; d++ ) {
+							long coord = remaining / inStrides[d];
+							remaining %= inStrides[d];
+							targetOutIdx += coord * permutedOutStrides[d];
+						}
+
+						int pointer = cnt[taskID];
+						cnt[taskID]++;
+						outIndexes[pointer] = (int) targetOutIdx;
+						outValues[pointer] = avals[j];
+					}
+					ix[i - bi] = j - apos; // keep block boundary
 				}
 			}
-			return null;
 		}
 	}
 }
+
diff --git a/src/test/java/org/apache/sysds/test/component/matrix/libMatrixReorg/PermuteTest.java b/src/test/java/org/apache/sysds/test/component/matrix/libMatrixReorg/PermuteTest.java
index 60810b9228..f6d309426b 100644
--- a/src/test/java/org/apache/sysds/test/component/matrix/libMatrixReorg/PermuteTest.java
+++ b/src/test/java/org/apache/sysds/test/component/matrix/libMatrixReorg/PermuteTest.java
@@ -31,10 +31,10 @@ import java.util.Arrays;
 public class PermuteTest {
 
 	@Test
-	public void testBasicPermute() {
+	public void testBasicPermuteDense() {
 		int[] shape = {2, 3, 4};
-		MatrixBlock tensor = generateMatrixBlock(shape);
-		
+		MatrixBlock tensor = generateDenseMatrixBlock(shape);
+
 		Assert.assertEquals(24, tensor.getNumRows() * tensor.getNumColumns());
 		
 		double[] data = tensor.getDenseBlockValues();
@@ -51,66 +51,66 @@ public class PermuteTest {
 	}
 
 	@Test
-	public void testPermute2DTranspose() {
+	public void testPermute2DTransposeDense() {
 		int[] shape = {10, 5};
 		int[] perm = {1, 0};
-		
-		MatrixBlock in = generateMatrixBlock(shape);
+
+		MatrixBlock in = generateDenseMatrixBlock(shape);
 		MatrixBlock out = LibMatrixReorg.permute(in, shape, perm);
-		
+
 		verifyPermutation(in, out, shape, perm);
 	}
 
 	@Test
-	public void testPermute3DSimple() {
+	public void testPermute3DSimpleDense() {
 		int[] shape = {2, 3, 4};
 		int[] perm = {1, 0, 2};
 
-		MatrixBlock in = generateMatrixBlock(shape);
+		MatrixBlock in = generateDenseMatrixBlock(shape);
 		MatrixBlock out = LibMatrixReorg.permute(in, shape, perm);
 
 		verifyPermutation(in, out, shape, perm);
 	}
 
 	@Test
-	public void testPermute3DIdentity() {
+	public void testPermute3DIdentityDense() {
 		int[] shape = {5, 5, 5};
 		int[] perm = {0, 1, 2};
 
-		MatrixBlock in = generateMatrixBlock(shape);
+		MatrixBlock in = generateDenseMatrixBlock(shape);
 		MatrixBlock out = LibMatrixReorg.permute(in, shape, perm);
 
 		verifyPermutation(in, out, shape, perm);
 	}
 
 	@Test
-	public void testPermute4DReverse() {
+	public void testPermute4DReverseDense() {
 		int[] shape = {2, 3, 4, 5};
 		int[] perm = {3, 2, 1, 0};
 
-		MatrixBlock in = generateMatrixBlock(shape);
+		MatrixBlock in = generateDenseMatrixBlock(shape);
 		MatrixBlock out = LibMatrixReorg.permute(in, shape, perm);
 
 		verifyPermutation(in, out, shape, perm);
 	}
 
 	@Test
-	public void testPermuteHighRank() {
+	public void testPermuteHighRankDense() {
 		int[] shape = {2, 2, 2, 2, 2, 2};
 		int[] perm = {5, 0, 4, 1, 3, 2};
 
-		MatrixBlock in = generateMatrixBlock(shape);
+		MatrixBlock in = generateDenseMatrixBlock(shape);
 		MatrixBlock out = LibMatrixReorg.permute(in, shape, perm);
 
 		verifyPermutation(in, out, shape, perm);
 	}
 
 	@Test
-	public void testLargeBlockLogicMocked() {
+	public void testLargeBlockLogicMockedDense() {
 		int[] shape = {10, 10, 10};
 		int[] perm = {2, 0, 1};
 
-		MatrixBlock in = generateMatrixBlock(shape);
+		MatrixBlock in = generateDenseMatrixBlock(shape);
 		DenseBlock originalDB = in.getDenseBlock();
 		DenseBlock spyDB = Mockito.spy(originalDB);
 		Mockito.when(spyDB.numBlocks()).thenReturn(2);
@@ -118,245 +118,688 @@ public class PermuteTest {
 
 		MatrixBlock out = LibMatrixReorg.permute(in, shape, perm);
 
-		MatrixBlock originalIn = generateMatrixBlock(shape);
-		verifyPermutation(originalIn, out, shape, perm);
+		MatrixBlock reference = generateDenseMatrixBlock(shape);
+		verifyPermutation(reference, out, shape, perm);
 	}
 
 	@Test
-	public void testLargeBlockLogicMockedInputAndOutput() {
+	public void testLargeBlockLogicMockedInputAndOutputDense() {
 		int[] shape = {4, 4, 4};
 		int[] perm = {2, 1, 0};
-		
-		MatrixBlock in = generateMatrixBlock(shape);
+
+		MatrixBlock in = generateDenseMatrixBlock(shape);
 		DenseBlock spyIn = Mockito.spy(in.getDenseBlock());
 		Mockito.when(spyIn.numBlocks()).thenReturn(5);
 		in.setDenseBlock(spyIn);
-		
+
 		MatrixBlock out = LibMatrixReorg.permute(in, shape, perm);
-		
-		MatrixBlock originalIn = generateMatrixBlock(shape);
-		verifyPermutation(originalIn, out, shape, perm);
+
+		MatrixBlock reference = generateDenseMatrixBlock(shape);
+		verifyPermutation(reference, out, shape, perm);
 	}
 
 	@Test
-	public void testPermute3DParallel() {
+	public void testPermute3DParallelDense() {
 		int[] shape = {100, 100, 100};
 		int[] perm = {2, 0, 1};
-		
-		MatrixBlock in = generateMatrixBlock(shape);
+
+		MatrixBlock in = generateDenseMatrixBlock(shape);
 		MatrixBlock out = LibMatrixReorg.permute(in, shape, perm, -1);
-		
+
 		verifyPermutation(in, out, shape, perm);
 	}
 
 	@Test
-	@Ignore
-	public void testPerformanceSingleVsMultiThreaded() {
-		int size = 100; 
-		int[] shape = {size, size, size};
+	public void testEdgeCaseSingleElementDense() {
+		int[] shape = {1, 1, 1};
+		int[] perm = {2, 1, 0};
+
+		MatrixBlock in = generateDenseMatrixBlock(shape);
+		MatrixBlock out = LibMatrixReorg.permute(in, shape, perm);
+
+		verifyPermutation(in, out, shape, perm);
+	}
+
+	@Test
+	public void testEdgeCaseOneDimensionOneDense() {
+		int[] shape = {5, 1, 10};
 		int[] perm = {2, 0, 1};
-		
-		MatrixBlock in = generateMatrixBlock(shape);
-		
-		long startSingle = System.nanoTime();
-		MatrixBlock outSingle = LibMatrixReorg.permute(in, shape, perm, 1);
-		long timeSingle = System.nanoTime() - startSingle;
-		
-		long startMulti = System.nanoTime();
-		MatrixBlock outMulti = LibMatrixReorg.permute(in, shape, perm, -1);
-		long timeMulti = System.nanoTime() - startMulti;
-		
-		verifyPermutation(in, outSingle, shape, perm);
-		verifyPermutation(in, outMulti, shape, perm);
-		
-		System.out.println("Large Matrix (" + size + "x" + size + "x" + size + "):");
-		System.out.println("Single-threaded: " + timeSingle / 1_000_000 + " ms");
-		System.out.println("Multi-threaded: " + timeMulti / 1_000_000 + " ms");
-		System.out.println("Speedup: " + String.format("%.2fx", (double)timeSingle / timeMulti));
 
-		Assert.assertTrue("Multi-threaded should be faster for large matrices", timeMulti < timeSingle);
+		MatrixBlock in = generateDenseMatrixBlock(shape);
+		MatrixBlock out = LibMatrixReorg.permute(in, shape, perm);
+
+		verifyPermutation(in, out, shape, perm);
 	}
 
-	@SuppressWarnings("unused")
 	@Test
-	@Ignore
-	public void testPerformanceLargeMatrixSingleVsMulti() {
-		int[] shape = {1, 10000, 10000};
-		int[] perm = {0, 2, 1};
-		
-		MatrixBlock in = generateMatrixBlock(shape);
-		
-		long startSingle = System.nanoTime();
-		MatrixBlock outSingle = LibMatrixReorg.permute(in, shape, perm, 1);
-		long timeSingle = System.nanoTime() - startSingle;
-		
-		long startMulti = System.nanoTime();
-		MatrixBlock outMulti = LibMatrixReorg.permute(in, shape, perm, -1);
-		long timeMulti = System.nanoTime() - startMulti;
-		
-		System.out.println("Large Matrix (" + 1 + "x" + 10000 + "x" + 100000 + "):");
-		System.out.println("Single-threaded: " + timeSingle / 1_000_000 + " ms");
-		System.out.println("Multi-threaded: " + timeMulti / 1_000_000 + " ms");
-		System.out.println("Speedup: " + String.format("%.2fx", (double)timeSingle / timeMulti));
-		
-		Assert.assertTrue("Multi-threaded should be faster for large matrices", timeMulti < timeSingle);
+	public void testEdgeCaseTwoDimensionsOneDense() {
+		int[] shape = {1, 1, 100};
+		int[] perm = {2, 1, 0};
+
+		MatrixBlock in = generateDenseMatrixBlock(shape);
+		MatrixBlock out = LibMatrixReorg.permute(in, shape, perm);
+
+		verifyPermutation(in, out, shape, perm);
 	}
 
-	@SuppressWarnings("unused")
 	@Test
-	@Ignore
-	public void testPerformancePermuteVsNativeTranspose() {
-		int size = 1000;
-		MatrixBlock in = new MatrixBlock(size, size, false);
+	public void testConsecutivePermutationsDense() {
+		int[] shape = {3, 4, 5};
+		int[] perm1 = {1, 0, 2};
+		int[] perm2 = {2, 0, 1};
+
+		MatrixBlock in = generateDenseMatrixBlock(shape);
+		MatrixBlock temp = LibMatrixReorg.permute(in, shape, perm1);
+
+		int[] tempShape = {shape[perm1[0]], shape[perm1[1]], shape[perm1[2]]};
+		MatrixBlock out = LibMatrixReorg.permute(temp, tempShape, perm2);
+
+		verifyPermutation(temp, out, tempShape, perm2);
+	}
+
+	@Test
+	public void testDifferentThreadCountsDense() {
+		int[] shape = {50, 50, 50};
+		int[] perm = {2, 0, 1};
+
+		MatrixBlock in = generateDenseMatrixBlock(shape);
+
+		MatrixBlock out1 = LibMatrixReorg.permute(in, shape, perm, 1);
+		MatrixBlock out2 = LibMatrixReorg.permute(in, shape, perm, 2);
+		MatrixBlock out4 = LibMatrixReorg.permute(in, shape, perm, 4);
+		MatrixBlock out8 = LibMatrixReorg.permute(in, shape, perm, 8);
+
+		double[] data1 = out1.getDenseBlockValues();
+		double[] data2 = out2.getDenseBlockValues();
+		double[] data4 = out4.getDenseBlockValues();
+		double[] data8 = out8.getDenseBlockValues();
+
+		for (int i = 0; i < data1.length; i++) {
+			Assert.assertEquals(data1[i], data2[i], 0.0001);
+			Assert.assertEquals(data1[i], data4[i], 0.0001);
+			Assert.assertEquals(data1[i], data8[i], 0.0001);
+		}
+	}
+
+	@Test
+	public void testThreadCountExceedsElementCountDense() {
+		int[] shape = {2, 2};
+		int[] perm = {1, 0};
+		MatrixBlock in = generateDenseMatrixBlock(shape);
+
+		MatrixBlock out1 = LibMatrixReorg.permute(in, shape, perm, 1);
+		MatrixBlock out16 = LibMatrixReorg.permute(in, shape, perm, 16);
+
+		verifyPermutation(in, out16, shape, perm);
+		double[] data1 = out1.getDenseBlockValues();
+		double[] data16 = out16.getDenseBlockValues();
+		for (int i = 0; i < data1.length; i++)
+			Assert.assertEquals(data1[i], data16[i], 0.0001);
+	}
+
+	@Test
+	public void testPermuteAllDimensionsCyclicDense() {
+		int[] shape = {3, 4, 5, 2};
+		int[] perm = {1, 2, 3, 0};
+
+		MatrixBlock in = generateDenseMatrixBlock(shape);
+		MatrixBlock out = LibMatrixReorg.permute(in, shape, perm);
+
+		verifyPermutation(in, out, shape, perm);
+	}
+
+	@Test
+	public void testPermuteNonContiguousStridesDense() {
+		int[] shape = {7, 11, 13};
+		int[] perm = {2, 0, 1};
+
+		MatrixBlock in = generateDenseMatrixBlock(shape);
+		MatrixBlock out = LibMatrixReorg.permute(in, shape, perm);
+
+		verifyPermutation(in, out, shape, perm);
+	}
+
+	@Test
+	public void testPermuteLargePrimeStridesDense() {
+		int[] shape = {17, 19};
+		int[] perm = {1, 0};
+
+		MatrixBlock in = generateDenseMatrixBlock(shape);
+		MatrixBlock out = LibMatrixReorg.permute(in, shape, perm);
+
+		verifyPermutation(in, out, shape, perm);
+	}
+
+	@Test
+	public void testSpecialFloatingPointValuesDense() {
+		int[] shape = {2, 2};
+		int[] perm = {1, 0};
+
+		MatrixBlock in = new MatrixBlock(1, 4, false);
 		in.allocateDenseBlock();
 		double[] data = in.getDenseBlockValues();
-		for (int i = 0; i < size; i++) {
-			for (int j = 0; j < size; j++) {
-				data[i * size + j] = i * size + j;
-			}
+		data[0] = Double.NaN;
+		data[1] = Double.POSITIVE_INFINITY;
+		data[2] = Double.NEGATIVE_INFINITY;
+		data[3] = 0.0;
+
+		MatrixBlock out = LibMatrixReorg.permute(in, shape, perm);
+		double[] outData = out.getDenseBlockValues();
+
+		int nanCount = 0, posInfCount = 0, negInfCount = 0;
+		for (double v : outData) {
+			if (Double.isNaN(v)) nanCount++;
+			else if (v == Double.POSITIVE_INFINITY) posInfCount++;
+			else if (v == Double.NEGATIVE_INFINITY) negInfCount++;
 		}
-		
-		int[] shape = {size, size};
+		Assert.assertEquals(1, nanCount);
+		Assert.assertEquals(1, posInfCount);
+		Assert.assertEquals(1, negInfCount);
+	}
+
+	@Test
+	public void testInputImmutableAfterPermuteDense() {
+		int[] shape = {4, 5, 6};
+		int[] perm = {2, 0, 1};
+
+		MatrixBlock in = generateDenseMatrixBlock(shape);
+		double[] before = in.getDenseBlockValues().clone();
+
+		LibMatrixReorg.permute(in, shape, perm);
+
+		double[] after = in.getDenseBlockValues();
+		Assert.assertArrayEquals(before, after, 0.0001);
+	}
+
+	@Test
+	public void testBasicPermuteSparse() {
+		int[] shape = {2, 3, 4};
+		int[] perm = {1, 0, 2};
+
+		MatrixBlock in = generateSparseMatrixBlock(shape, 0.2);
+		MatrixBlock out = LibMatrixReorg.permute(in, shape, perm);
+
+		verifyPermutation(in, out, shape, perm);
+	}
+
+	@Test
+	public void testPermute2DTransposeSparse() {
+		int[] shape = {10, 5};
 		int[] perm = {1, 0};
-		
-		long startPermute = System.nanoTime();
-		MatrixBlock outPermute = LibMatrixReorg.permute(in, shape, perm, -1);
-		long timePermute = System.nanoTime() - startPermute;
-		
-		long startTranspose = System.nanoTime();
-		MatrixBlock outTranspose = LibMatrixReorg.transpose(in);
-		long timeTranspose = System.nanoTime() - startTranspose;
-		
-		System.out.println("Transpose Performance (" + size + "x" + size + "):");
-		System.out.println("Permute function: " + timePermute / 1_000_000 + " ms");
-		System.out.println("Native transpose: " + timeTranspose / 1_000_000 + " ms");
-		System.out.println("Ratio: " + String.format("%.2fx", (double)timePermute / timeTranspose));
-		
-		double[] permuteData = outPermute.getDenseBlockValues();
-		
-		for (int i = 0; i < size; i++) {
-			for (int j = 0; j < size; j++) {
-				double expected = in.get(j, i);
-				double actual = permuteData[i * size + j];
-				Assert.assertEquals("Mismatch at (" + i + "," + j + ")", expected, actual, 0.0001);
-			}
-		}
+
+		MatrixBlock in = generateSparseMatrixBlock(shape, 0.2);
+		MatrixBlock out = LibMatrixReorg.permute(in, shape, perm);
+
+		verifyPermutation(in, out, shape, perm);
+	}
+
+	@Test
+	public void testPermute3DSimpleSparse() {
+		int[] shape = {2, 3, 4};
+		int[] perm = {1, 0, 2};
+
+		MatrixBlock in = generateSparseMatrixBlock(shape, 0.2);
+		MatrixBlock out = LibMatrixReorg.permute(in, shape, perm);
+
+		verifyPermutation(in, out, shape, perm);
+	}
+
+	@Test
+	public void testPermute3DIdentitySparse() {
+		int[] shape = {5, 5, 5};
+		int[] perm = {0, 1, 2};
+
+		MatrixBlock in = generateSparseMatrixBlock(shape, 0.2);
+		MatrixBlock out = LibMatrixReorg.permute(in, shape, perm);
+
+		verifyPermutation(in, out, shape, perm);
+	}
+
+	@Test
+	public void testPermute4DReverseSparse() {
+		int[] shape = {2, 3, 4, 5};
+		int[] perm = {3, 2, 1, 0};
+
+		MatrixBlock in = generateSparseMatrixBlock(shape, 0.2);
+		MatrixBlock out = LibMatrixReorg.permute(in, shape, perm);
+
+		verifyPermutation(in, out, shape, perm);
+	}
+
+	@Test
+	public void testPermuteHighRankSparse() {
+		int[] shape = {2, 2, 2, 2, 2, 2};
+		int[] perm = {5, 0, 4, 1, 3, 2};
+
+		MatrixBlock in = generateSparseMatrixBlock(shape, 0.2);
+		MatrixBlock out = LibMatrixReorg.permute(in, shape, perm);
+
+		verifyPermutation(in, out, shape, perm);
 	}
 
 	@Test
-	public void testEdgeCaseSingleElement() {
+	public void testPermute3DParallelSparse() {
+		int[] shape = {100, 100, 100};
+		int[] perm = {2, 0, 1};
+
+		MatrixBlock in = generateSparseMatrixBlock(shape, 0.1);
+		MatrixBlock out = LibMatrixReorg.permute(in, shape, perm, -1);
+
+		verifyPermutation(in, out, shape, perm);
+	}
+
+	@Test
+	public void testEdgeCaseEmptySparse() {
+		int[] shape = {5, 5, 5};
+		int[] perm = {1, 0, 2};
+
+		MatrixBlock in = new MatrixBlock(1, 125, true);
+		MatrixBlock out = LibMatrixReorg.permute(in, shape, perm);
+
+		Assert.assertTrue(out.isEmpty());
+		Assert.assertEquals(125, out.getNumColumns());
+	}
+
+	@Test
+	public void testEdgeCaseSingleElementSparse() {
 		int[] shape = {1, 1, 1};
 		int[] perm = {2, 1, 0};
-		
-		MatrixBlock in = generateMatrixBlock(shape);
+
+		MatrixBlock in = new MatrixBlock(1, 1, true);
+		in.allocateSparseRowsBlock();
+		in.appendValue(0, 0, 42.0);
+		in.recomputeNonZeros();
 		MatrixBlock out = LibMatrixReorg.permute(in, shape, perm);
-		
+
 		verifyPermutation(in, out, shape, perm);
 	}
 
 	@Test
-	public void testEdgeCaseOneDimensionOne() {
+	public void testEdgeCaseOneDimensionOneSparse() {
 		int[] shape = {5, 1, 10};
 		int[] perm = {2, 0, 1};
-		
-		MatrixBlock in = generateMatrixBlock(shape);
+
+		MatrixBlock in = generateSparseMatrixBlock(shape, 0.2);
 		MatrixBlock out = LibMatrixReorg.permute(in, shape, perm);
-		
+
 		verifyPermutation(in, out, shape, perm);
 	}
 
 	@Test
-	public void testEdgeCaseTwoDimensionsOne() {
+	public void testEdgeCaseTwoDimensionsOneSparse() {
 		int[] shape = {1, 1, 100};
 		int[] perm = {2, 1, 0};
-		
-		MatrixBlock in = generateMatrixBlock(shape);
+
+		MatrixBlock in = generateSparseMatrixBlock(shape, 0.2);
 		MatrixBlock out = LibMatrixReorg.permute(in, shape, perm);
-		
+
 		verifyPermutation(in, out, shape, perm);
 	}
 
-	@SuppressWarnings("unused")
 	@Test
-	public void testConsecutivePermutations() {
+	public void testConsecutivePermutationsSparse() {
 		int[] shape = {3, 4, 5};
 		int[] perm1 = {1, 0, 2};
 		int[] perm2 = {2, 0, 1};
-		
-		MatrixBlock in = generateMatrixBlock(shape);
+
+		MatrixBlock in = generateSparseMatrixBlock(shape, 0.2);
 		MatrixBlock temp = LibMatrixReorg.permute(in, shape, perm1);
-		
+
 		int[] tempShape = {shape[perm1[0]], shape[perm1[1]], shape[perm1[2]]};
 		MatrixBlock out = LibMatrixReorg.permute(temp, tempShape, perm2);
-		
-		int[] finalShape = {tempShape[perm2[0]], tempShape[perm2[1]], tempShape[perm2[2]]};
-		
+
 		verifyPermutation(temp, out, tempShape, perm2);
 	}
 
 	@Test
-	public void testDifferentThreadCounts() {
+	public void testDifferentThreadCountsSparse() {
 		int[] shape = {50, 50, 50};
 		int[] perm = {2, 0, 1};
-		
-		MatrixBlock in = generateMatrixBlock(shape);
-		
+
+		MatrixBlock in = generateSparseMatrixBlock(shape, 0.1);
+
 		MatrixBlock out1 = LibMatrixReorg.permute(in, shape, perm, 1);
 		MatrixBlock out2 = LibMatrixReorg.permute(in, shape, perm, 2);
 		MatrixBlock out4 = LibMatrixReorg.permute(in, shape, perm, 4);
 		MatrixBlock out8 = LibMatrixReorg.permute(in, shape, perm, 8);
-		
-		double[] data1 = out1.getDenseBlockValues();
-		double[] data2 = out2.getDenseBlockValues();
-		double[] data4 = out4.getDenseBlockValues();
-		double[] data8 = out8.getDenseBlockValues();
-		
-		for (int i = 0; i < data1.length; i++) {
-			Assert.assertEquals(data1[i], data2[i], 0.0001);
-			Assert.assertEquals(data1[i], data4[i], 0.0001);
-			Assert.assertEquals(data1[i], data8[i], 0.0001);
+
+		long len = totalLength(shape);
+		for (int i = 0; i < len; i++) {
+			double v1 = out1.get(0, i);
+			Assert.assertEquals(v1, out2.get(0, i), 0.0001);
+			Assert.assertEquals(v1, out4.get(0, i), 0.0001);
+			Assert.assertEquals(v1, out8.get(0, i), 0.0001);
 		}
 	}
 
 	@Test
-	public void testPermuteAllDimensionsCyclic() {
+	public void testThreadCountExceedsElementCountSparse() {
+		int[] shape = {2, 2};
+		int[] perm = {1, 0};
+		MatrixBlock in = generateSparseMatrixBlock(shape, 0.5);
+
+		MatrixBlock out1 = LibMatrixReorg.permute(in, shape, perm, 1);
+		MatrixBlock out16 = LibMatrixReorg.permute(in, shape, perm, 16);
+
+		verifyPermutation(in, out16, shape, perm);
+		long len = totalLength(shape);
+		for (int i = 0; i < len; i++)
+			Assert.assertEquals(out1.get(0, i), out16.get(0, i), 0.0001);
+	}
+
+	@Test
+	public void testPermuteAllDimensionsCyclicSparse() {
 		int[] shape = {3, 4, 5, 2};
 		int[] perm = {1, 2, 3, 0};
-		
-		MatrixBlock in = generateMatrixBlock(shape);
+
+		MatrixBlock in = generateSparseMatrixBlock(shape, 0.2);
 		MatrixBlock out = LibMatrixReorg.permute(in, shape, perm);
-		
+
 		verifyPermutation(in, out, shape, perm);
 	}
 
 	@Test
-	public void testPermuteNonContiguousStrides() {
+	public void testPermuteNonContiguousStridesSparse() {
 		int[] shape = {7, 11, 13};
 		int[] perm = {2, 0, 1};
-		
-		MatrixBlock in = generateMatrixBlock(shape);
+
+		MatrixBlock in = generateSparseMatrixBlock(shape, 0.2);
 		MatrixBlock out = LibMatrixReorg.permute(in, shape, perm);
-		
+
 		verifyPermutation(in, out, shape, perm);
 	}
 
 	@Test
-	public void testPermuteLargePrimeStrides() {
+	public void testPermuteLargePrimeStridesSparse() {
 		int[] shape = {17, 19};
 		int[] perm = {1, 0};
-		
-		MatrixBlock in = generateMatrixBlock(shape);
+
+		MatrixBlock in = generateSparseMatrixBlock(shape, 0.2);
 		MatrixBlock out = LibMatrixReorg.permute(in, shape, perm);
-		
+
 		verifyPermutation(in, out, shape, perm);
 	}
 
-	private MatrixBlock generateMatrixBlock(int[] shape) {
+	@Test
+	public void testSpecialFloatingPointValuesSparse() {
+		int[] shape = {2, 2};
+		int[] perm = {1, 0};
+
+		MatrixBlock in = new MatrixBlock(1, 4, true);
+		in.allocateSparseRowsBlock();
+		in.appendValue(0, 0, Double.NaN);
+		in.appendValue(0, 1, Double.POSITIVE_INFINITY);
+		in.appendValue(0, 2, Double.NEGATIVE_INFINITY);
+		in.recomputeNonZeros();
+
+		MatrixBlock out = LibMatrixReorg.permute(in, shape, perm);
+
+		int nanCount = 0, posInfCount = 0, negInfCount = 0;
+		for (int i = 0; i < 4; i++) {
+			double v = out.get(0, i);
+			if (Double.isNaN(v)) nanCount++;
+			else if (v == Double.POSITIVE_INFINITY) posInfCount++;
+			else if (v == Double.NEGATIVE_INFINITY) negInfCount++;
+		}
+		Assert.assertEquals(1, nanCount);
+		Assert.assertEquals(1, posInfCount);
+		Assert.assertEquals(1, negInfCount);
+	}
+
+	@Test
+	public void testInputImmutableAfterPermuteSparse() {
+		int[] shape = {4, 5, 6};
+		int[] perm = {2, 0, 1};
+
+		MatrixBlock in = generateSparseMatrixBlock(shape, 0.2);
+		long len = totalLength(shape);
+		double[] before = new double[(int) len];
+		for (int i = 0; i < len; i++)
+			before[i] = in.get(0, i);
+
+		LibMatrixReorg.permute(in, shape, perm);
+
+		for (int i = 0; i < len; i++)
+			Assert.assertEquals(before[i], in.get(0, i), 0.0001);
+	}
+
+	@Test
+	public void testLargeSparseManyRowsConsistency() {
+		int[] shape = {10, 10, 10};
+		int[] perm = {2, 0, 1};
+		MatrixBlock in = generateSparseMatrixBlock(shape, 0.3);
+
+		MatrixBlock outSingle = LibMatrixReorg.permute(in, shape, perm, 1);
+		MatrixBlock outMulti = LibMatrixReorg.permute(in, shape, perm, -1);
+
+		verifyPermutation(in, outSingle, shape, perm);
+		long len = totalLength(shape);
+		for (int i = 0; i < len; i++)
+			Assert.assertEquals(outSingle.get(0, i), outMulti.get(0, i), 0.0001);
+	}
+
+	@Test
+	public void testNonZeroCountPreservedAfterPermuteSparse() {
+		int[] shape = {6, 7, 8};
+		int[] perm = {2, 0, 1};
+		MatrixBlock in = generateSparseMatrixBlock(shape, 0.25);
+		long nnzBefore = in.getNonZeros();
+
+		MatrixBlock out = LibMatrixReorg.permute(in, shape, perm);
+		out.recomputeNonZeros();
+
+		Assert.assertEquals(nnzBefore, out.getNonZeros());
+		Assert.assertEquals(nnzBefore == 0, out.isEmpty());
+	}
+
+	@Test
+	public void testDenseSparseParitySmall() {
+		int[] shape = {4, 3, 5};
+		int[] perm = {2, 0, 1};
+
+		MatrixBlock dense = generateDenseMatrixBlock(shape);
+		MatrixBlock sparse = denseToSparse(dense);
+
+		MatrixBlock outDense = LibMatrixReorg.permute(dense, shape, perm);
+		MatrixBlock outSparse = LibMatrixReorg.permute(sparse, shape, perm);
+
+		long len = totalLength(shape);
+		for (int i = 0; i < len; i++) {
+			Assert.assertEquals(outDense.get(0, i), outSparse.get(0, i), 0.0001);
+		}
+	}
+
+	@Test
+	public void testDenseSparseParityHighRank() {
+		int[] shape = {2, 3, 4, 5};
+		int[] perm = {3, 1, 0, 2};
+
+		MatrixBlock dense = generateDenseMatrixBlock(shape);
+		MatrixBlock sparse = denseToSparse(dense);
+
+		MatrixBlock outDense = LibMatrixReorg.permute(dense, shape, perm);
+		MatrixBlock outSparse = LibMatrixReorg.permute(sparse, shape, perm);
+
+		long len = totalLength(shape);
+		for (int i = 0; i < len; i++) {
+			Assert.assertEquals(outDense.get(0, i), outSparse.get(0, i), 0.0001);
+		}
+	}
+
+	@Test
+	public void testInvalidPermutationDuplicateIndicesDense() {
+		int[] shape = {2, 3, 4};
+		int[] perm = {0, 0, 2};
+
+		MatrixBlock in = generateDenseMatrixBlock(shape);
+		try {
+			LibMatrixReorg.permute(in, shape, perm);
+			Assert.fail("Expected an exception for duplicate indices");
+		} catch (Exception expected) {
+		}
+	}
+
+	@Test
+	public void testInvalidPermutationOutOfRangeIndexDense() {
+		int[] shape = {2, 3, 4};
+		int[] perm = {0, 1, 5};
+		MatrixBlock in = generateDenseMatrixBlock(shape);
+		try {
+			LibMatrixReorg.permute(in, shape, perm);
+			Assert.fail("Expected an exception for an out-of-range permutation index");
+		} catch (Exception expected) {
+		}
+	}
+
+	@Test
+	public void testInvalidPermutationWrongLengthDense() {
+		int[] shape = {2, 3, 4};
+		int[] perm = {1, 0};
+		MatrixBlock in = generateDenseMatrixBlock(shape);
+		try {
+			LibMatrixReorg.permute(in, shape, perm);
+			Assert.fail("Expected an exception for a permutation array of the wrong length");
+		} catch (Exception expected) {
+		}
+	}
+
+	@Test
+	public void testInvalidShapeDataLengthMismatchDense() {
+		int[] shape = {3, 3, 3};
+		int[] perm = {1, 0, 2};
+		MatrixBlock in = generateDenseMatrixBlock(new int[]{2, 2, 2});
+		try {
+			LibMatrixReorg.permute(in, shape, perm);
+			Assert.fail("Expected an exception when shape does not match input data length");
+		} catch (Exception expected) {
+		}
+	}
+
+	@Test
+	public void testInvalidPermutationDuplicateIndicesSparse() {
+		int[] shape = {2, 3, 4};
+		int[] perm = {0, 0, 2};
+		MatrixBlock in = generateSparseMatrixBlock(shape, 0.2);
+		try {
+			LibMatrixReorg.permute(in, shape, perm);
+			Assert.fail("Expected an exception for duplicate indices");
+		} catch (Exception expected) {
+		}
+	}
+
+	@Test
+	public void testSparseFormatPreservedAfterPermute() {
+		int[] shape = {6, 7, 8};
+		int[] perm = {2, 0, 1};
+
+		MatrixBlock in = generateSparseMatrixBlock(shape, 0.05);
+		MatrixBlock out = LibMatrixReorg.permute(in, shape, perm);
+
+		Assert.assertTrue("Sparse input must produce a sparse output", out.isInSparseFormat());
+	}
+
+	@Test
+	public void testDenseFormatPreservedAfterPermute() {
+		int[] shape = {6, 7, 8};
+		int[] perm = {2, 0, 1};
+
+		MatrixBlock in = generateDenseMatrixBlock(shape);
+		MatrixBlock out = LibMatrixReorg.permute(in, shape, perm);
+
+		Assert.assertFalse("Dense input must produce a dense output", out.isInSparseFormat());
+	}
+
+	/*
+	This Test takes relatively long. 
+	The smaller sparse tests are relatively unstable, sometimes showing some speedup, sometimes not. 
+	The larg test however, always shows some speedup but in the range between 1.01 and 10.4. 
+	*/
+	@Test 
+	@Ignore
+	public void testPerformanceBenchmarkDenseAndSparse() {
+		int size = 100;
+		int[] shape = {size, size, size};
+		int[] perm = {2, 0, 1};
+
+		System.out.println("--- Benchmark Results (Size " + size + "^3) ---");
+
+		MatrixBlock denseIn = generateDenseMatrixBlock(shape);
+		double dSingle = benchmarkPermute(denseIn, shape, perm, 1);
+		double dMulti = benchmarkPermute(denseIn, shape, perm, -1);
+		printBenchmarkResult("Dense", dSingle, dMulti);
+
+		MatrixBlock sparseIn10 = generateSparseMatrixBlock(shape, 0.1);
+		double s10Single = benchmarkPermute(sparseIn10, shape, perm, 1);
+		double s10Multi = benchmarkPermute(sparseIn10, shape, perm, -1);
+		printBenchmarkResult("Sparse (0.1)", s10Single, s10Multi);
+
+		MatrixBlock sparseIn50 = generateSparseMatrixBlock(shape, 0.5);
+		double s50Single = benchmarkPermute(sparseIn50, shape, perm, 1);
+		double s50Multi = benchmarkPermute(sparseIn50, shape, perm, -1);
+		printBenchmarkResult("Sparse (0.5)", s50Single, s50Multi);
+
+		MatrixBlock sparseLarge = generateSparseMatrixBlock(new int[]{100, 1000, 1000}, 0.5);
+		double sLargeSingle = benchmarkPermute(sparseLarge, new int[]{100, 1000, 1000}, new int[]{2, 0, 1}, 1);
+		double sLargeMulti = benchmarkPermute(sparseLarge, new int[]{100, 1000, 1000}, new int[]{2, 0, 1}, -1);
+		printBenchmarkResult("Sparse Large (0.5)", sLargeSingle, sLargeMulti);
+
+		Assert.assertTrue(dMulti < dSingle * 2.0);
+	}
+
+	@Test
+	@Ignore // Unstable on my device 
+	public void testPerformanceSingleVsMultiThreadedDense() {
+		int size = 100;
+		int[] shape = {size, size, size};
+		int[] perm = {2, 0, 1};
+
+		MatrixBlock in = generateDenseMatrixBlock(shape);
+
+		MatrixBlock outSingle = LibMatrixReorg.permute(in, shape, perm, 1);
+		MatrixBlock outMulti = LibMatrixReorg.permute(in, shape, perm, -1);
+		verifyPermutation(in, outSingle, shape, perm);
+		verifyPermutation(in, outMulti, shape, perm);
+
+		double timeSingle = benchmarkPermute(in, shape, perm, 1);
+		double timeMulti = benchmarkPermute(in, shape, perm, -1);
+
+		System.out.println("Large Matrix (" + size + "x" + size + "x" + size + "):");
+		System.out.printf("Single-threaded (avg): %.2f ms%n", timeSingle);
+		System.out.printf("Multi-threaded (avg): %.2f ms%n", timeMulti);
+		System.out.printf("Speedup: %.2fx%n", timeSingle / timeMulti);
+
+		Assert.assertTrue("Multi-threaded should be faster for large matrices", timeMulti < timeSingle);
+	}
+
+	@Test // Shows a stable speedup of ~2,20 
+	@Ignore
+	public void testPerformanceLargeMatrixSingleVsMultiDense() {
+		int[] shape = {10, 1000, 1000};
+		int[] perm = {0, 2, 1};
+
+		MatrixBlock in = generateDenseMatrixBlock(shape);
+
+		double timeSingle = benchmarkPermute(in, shape, perm, 1);
+		double timeMulti = benchmarkPermute(in, shape, perm, -1);
+
+		System.out.println("Large Matrix (10x1000x1000):");
+		System.out.printf("Single-threaded (avg): %.2f ms%n", timeSingle);
+		System.out.printf("Multi-threaded (avg): %.2f ms%n", timeMulti);
+		System.out.printf("Speedup: %.2fx%n", timeSingle / timeMulti);
+
+		Assert.assertTrue("Multi-threaded should be faster for large matrices", timeMulti < timeSingle);
+	}
+
+	private MatrixBlock generateDenseMatrixBlock(int[] shape) {
 		long len = 1;
 		for (int d : shape) len *= d;
-		
-		MatrixBlock mb = new MatrixBlock(1, (int)len, false);
+
+		int rows = shape[0];
+		int cols = (int) (len / rows);
+
+		MatrixBlock mb = new MatrixBlock(rows, cols, false);
 		mb.allocateDenseBlock();
+		
 		double[] data = mb.getDenseBlockValues();
 		for (int i = 0; i < data.length; i++) {
 			data[i] = (double) i;
@@ -364,65 +807,83 @@ public class PermuteTest {
 		return mb;
 	}
 
-	private void verifyPermutation(MatrixBlock in, MatrixBlock out, int[] inShape, int[] perm) {
-		double[] inData = new double[(int)(in.getNumRows() * in.getNumColumns())];
-		double[] outData = new double[(int)(out.getNumRows() * out.getNumColumns())];
-		
-		DenseBlock inDB = in.getDenseBlock();
-		DenseBlock outDB = out.getDenseBlock();
+	private MatrixBlock generateSparseMatrixBlock(int[] shape, double sparsity) {
+		long len = 1;
+		for (int d : shape) len *= d;
+
+		int rows = shape[0];
+		int cols = (int) (len / rows);
+
+		MatrixBlock mb = new MatrixBlock(rows, cols, true);
+		mb.allocateSparseRowsBlock();
 		
-		if (inDB != null) {
-			int inBlockSize = inDB.blockSize();
-			for (int i = 0; i < inDB.numBlocks(); i++) {
-				double[] block = inDB.valuesAt(i);
-				int offset = i * inBlockSize;
-				int len = Math.min(inBlockSize, inData.length - offset);
-				System.arraycopy(block, 0, inData, offset, len);
+		for (long i = 0; i < len; i++) {
+			if ((i * 0.12345) % 1.0 < sparsity) {
+				int r = (int) (i / cols);
+				int c = (int) (i % cols);
+				mb.appendValue(r, c, (double) i);
 			}
 		}
+		mb.recomputeNonZeros();
+		return mb;
+	}
+
+	private MatrixBlock denseToSparse(MatrixBlock dense) { 
+		int rows = dense.getNumRows();
+		int cols = dense.getNumColumns();
+
+		MatrixBlock sparse = new MatrixBlock(rows, cols, true);
+		sparse.allocateSparseRowsBlock();
 		
-		if (outDB != null) {
-			int outBlockSize = outDB.blockSize();
-			for (int i = 0; i < outDB.numBlocks(); i++) {
-				double[] block = outDB.valuesAt(i);
-				int offset = i * outBlockSize;
-				int len = Math.min(outBlockSize, outData.length - offset);
-				System.arraycopy(block, 0, outData, offset, len);
+		for (int r = 0; r < rows; r++) {
+			for (int c = 0; c < cols; c++) {
+				double val = dense.get(r, c);
+				if (val != 0) {
+					sparse.appendValue(r, c, val);
+				}
 			}
 		}
-		
+		sparse.recomputeNonZeros();
+		return sparse;
+	}
+
+	private void verifyPermutation(MatrixBlock in, MatrixBlock out, int[] inShape, int[] perm) {
 		int rank = inShape.length;
 		int[] outShape = new int[rank];
-		for (int i = 0; i < rank; i++) 
+		for (int i = 0; i < rank; i++)
 			outShape[i] = inShape[perm[i]];
 
 		long[] outStrides = getStrides(outShape);
 		long[] inStrides = getStrides(inShape);
-
+		
 		long len = 1;
 		for (int d : outShape) len *= d;
 
 		for (long i = 0; i < len; i++) {
 			int[] outCoords = new int[rank];
-			long temp = i;
+			long remaining = i;
 			for (int d = 0; d < rank; d++) {
-				outCoords[d] = (int)(temp / outStrides[d]);
-				temp = temp % outStrides[d];
+				outCoords[d] = (int) (remaining / outStrides[d]);
+				remaining %= outStrides[d];
 			}
 
 			int[] inCoords = new int[rank];
-			for (int d = 0; d < rank; d++) {
+			for (int d = 0; d < rank; d++){
 				inCoords[perm[d]] = outCoords[d];
 			}
-			
+
 			long inIndex = 0;
-			for (int d = 0; d < rank; d++) {
+			for (int d = 0; d < rank; d++){
 				inIndex += inCoords[d] * inStrides[d];
 			}
+
+			int inCols = in.getNumColumns();
+			int r = (int) (inIndex / inCols);
+			int c = (int) (inIndex % inCols);
 			
-			double expectedValue = inData[(int)inIndex];
-			double actualValue = outData[(int)i];
-			
+			double expectedValue = in.get(r, c);
+			double actualValue = out.get(0, (int)i);
+
 			if (Math.abs(expectedValue - actualValue) > 0.0001) {
 				Assert.fail("Mismatch at linear output index " + i + 
 							". Output coords " + Arrays.toString(outCoords) + 
@@ -441,4 +902,30 @@ public class PermuteTest {
 		}
 		return strides;
 	}
-}
\ No newline at end of file
+
+	private long totalLength(int[] shape) {
+		long len = 1;
+		for (int d : shape) len *= d;
+		return len;
+	}
+
+	private double benchmarkPermute(MatrixBlock in, int[] shape, int[] perm, int k) {
+		double checksum = 0;
+		for (int i = 0; i < 5; i++)
+			checksum += LibMatrixReorg.permute(in, shape, perm, k).get(0, 0);
+
+		long start = System.nanoTime();
+		for (int i = 0; i < 10; i++)
+			checksum += LibMatrixReorg.permute(in, shape, perm, k).get(0, 0);
+		long elapsed = System.nanoTime() - start;
+
+		if (checksum == Double.NaN)
+			System.out.println("unreachable");
+		return (double) elapsed / 1_000_000.0 / 10.0;
+	}
+
+	private void printBenchmarkResult(String label, double single, double multi) {
+		System.out.printf("%-20s Single: %6.2fms  Multi: %6.2fms  Speedup: %.2fx%n",
+			label, single, multi, single / multi);
+	}
+}