Parallel Algorithms

Tensor-based decomposition methods compress large datasets with less accuracy loss than traditional matrix methods. Under the star-M tensor framework, tensors decompose in a matrix-mimetic way through the star-M SVD, which carries optimality guarantees but has been confined to productivity-oriented language implementations. We present a shared-memory parallel, high-performance implementation built on batched tensor-times-matrix and slice-wise SVD kernels, achieving a 42x strong-scaling speedup from 1 to 64 threads on the ncep-air-6 dataset.

Higher Order Orthogonal Iteration (HOOI) is an iterative algorithm that computes a Tucker decomposition of an input tensor. We present distributed-memory parallel, rank-adaptive variants of HOOI that adaptively determine the core tensor ranks rather than requiring them as fixed inputs, using efficient parallel tensor-times-matrix (TTM) and SVD kernels to scale Tucker decomposition to large tensors.

This work designs, analyzes, and optimizes sequential and shared-memory parallel algorithms for partitioned local depths (PaLD). The algorithms identify pairwise relationships from relative distances and attain sequential speedups up to 29x over a baseline sequential implementation and parallel speedups up to 19.4x over optimized sequential implementations using up to 32 threads on an Intel multicore CPU.