Ordered Eigenvalue Decomposition Implementation on Systolic Arrays via Virtual Rewiring
Chengqian Tang, Yaxuan Lu, Bowen Liang, Yunhe Cao, Mengmeng Han · Electronics · 2026
Eigenvalue Decomposition (EVD) is a fundamental operation in real-time signal processing, yet obtaining sorted outputs from systolic arrays remains a persistent engineering challenge. The conventional Brent–Luk architecture relies on external sorting networks to reorder eigenvalues. Attempts to achieve in-place sorting via angle adjustment fail due to “topological mismatch,” a conflict between implicit data permutation from large-angle Givens rotations and fixed hardware routing. To address this, we propose a virtual rewiring mechanism. By exploiting the inherent half-cycle reversal pattern of Round-Robin scheduling, we derive a correction algorithm requiring only sign-bit operations. This achieves automatic descending-order arrangement without modifying physical interconnects. Field-Programmable Gate Array (FPGA) experiments demonstrate that the proposed scheme requires negligible additional resources (0.8% Look-Up Tables (LUTs)) while reducing sorting-related logic by 91%. Furthermore, sorting is achieved entirely within the existing computational pipeline, resulting in zero additional hardware latency per sweep.