Skip to main content
placeholder image

Weighing matrices and string sorting

Journal Article


Abstract


  • In this paper we establish a fundamental link between the search for weighing matrices constructed from two circulants and the operation of sorting strings, an operation that has been studied extensively in computer science. In particular, we demonstrate that the search for weighing matrices constructed from two circulants using the power spectral density criterion and exploiting structural patterns for the locations of the zeros in candidate solutions, can be viewed as a string sorting problem together with a linear time algorithm to locate common strings in two sorted arrays. This allows us to bring into bear efficient algorithms from the string sorting literature. We also state and prove some new enhancements to the power spectral density criterion, that allow us to treat successfully the rounding error effect and speed up the algorithm. Finally, we use these ideas to find new weighing matrices of order 2n and weights 2n - 13, 2n - 17 constructed from two circulants.

UOW Authors


  •   Kotsireas, Ilias S. (external author)
  •   Koukouvinos, Christos (external author)
  •   Seberry, Jennifer

Publication Date


  • 2009

Citation


  • Kotsireas, I. S., Koukouvinos, C. & Seberry, J. (2009). Weighing matrices and string sorting. Annals of Combinatorics, 13 (3), 305-313.

Scopus Eid


  • 2-s2.0-70449517269

Ro Metadata Url


  • http://ro.uow.edu.au/infopapers/3243

Has Global Citation Frequency


Number Of Pages


  • 8

Start Page


  • 305

End Page


  • 313

Volume


  • 13

Issue


  • 3

Abstract


  • In this paper we establish a fundamental link between the search for weighing matrices constructed from two circulants and the operation of sorting strings, an operation that has been studied extensively in computer science. In particular, we demonstrate that the search for weighing matrices constructed from two circulants using the power spectral density criterion and exploiting structural patterns for the locations of the zeros in candidate solutions, can be viewed as a string sorting problem together with a linear time algorithm to locate common strings in two sorted arrays. This allows us to bring into bear efficient algorithms from the string sorting literature. We also state and prove some new enhancements to the power spectral density criterion, that allow us to treat successfully the rounding error effect and speed up the algorithm. Finally, we use these ideas to find new weighing matrices of order 2n and weights 2n - 13, 2n - 17 constructed from two circulants.

UOW Authors


  •   Kotsireas, Ilias S. (external author)
  •   Koukouvinos, Christos (external author)
  •   Seberry, Jennifer

Publication Date


  • 2009

Citation


  • Kotsireas, I. S., Koukouvinos, C. & Seberry, J. (2009). Weighing matrices and string sorting. Annals of Combinatorics, 13 (3), 305-313.

Scopus Eid


  • 2-s2.0-70449517269

Ro Metadata Url


  • http://ro.uow.edu.au/infopapers/3243

Has Global Citation Frequency


Number Of Pages


  • 8

Start Page


  • 305

End Page


  • 313

Volume


  • 13

Issue


  • 3