Mathematical Complexity Reduction - Otto-von-Guericke-University Magdeburg

 
 
 
 
 
 
 
 

Costas Arrays

We study Costas arrays, which is a highly combinatorial problem with practical applications in radar engineering. A Costas array of size n is an n*n binary matrix such that there is exactly a single 1 per each row and each column (i.e., it is a permutation matrix) and such that the line segments formed by joining pairs of 1s are all distinct. In other words, a Costas array is a permutation matrix that no two of the n choose 2 line segments connecting 1s have the same length and slope.

Until today, the enumeration of Costas arrays has been completed via computational methods for all n leq 29. However, the total run-time of the search for n=29 on a single CPU required the equivalent of 366.55 years, but, the real-time required was approximately 230 days as a result of high parallelization of the tasks. Problems related to Costas arrays are inherently difficult, perhaps the most serious difficulty of finding Costas arrays via exhaustive search is that the size of the search space increases exponentially with n. In our opinion, further research into Costas arrays regarding the role of optimization techniques would be worthwhile. It might be possible to propose a new algorithm by which we could reduce the computational complexity of Costas array problems.

Last Modification: 2020-01-28 - Contact Person: Sebastian Sager - Impressum