An L-shaped partitioning-based algebraic factorization algorithm

Algebraic factorization is an extremely important part of any logic synthesis system but it is computationally expensive. Hence it is important to speed it up. The paper presents an algorithm to speedup the factorization by partitioning the circuit and performing factorizations on the sub-circuits. The approach clusters the entries of the co-kernel cube matrix into dense blocks using a novel L-shaped partitioning and searches these blocks for kernels. The L-shaped approach runs up to five times faster than the kernel extraction routine in SIS