Filetype PDF | Posted on 27 Jan 2023 | 3 years ago
Authentication
digital resources
192x Filetype PDF File size 0.30 MB Source: core.ac.uk
View metadata, citation and similar papers at core.ac.uk brought to you by CORE
provided by Elsevier - Publisher Connector
Theoretical ComputerScience407(2008)274–277
Contents lists available at ScienceDirect
Theoretical ComputerScience
journal homepage: www.elsevier.com/locate/tcs
Heuristic algorithms for Hadamard matrices with two circulant cores
M.Chiarandinia,I.S. Kotsireasb,∗, C. Koukouvinosc, L. Paqueted
a Department of Mathematics and Computer Science, University of Southern Denmark, Campusvej 55 DK-5230 Odense M, Denmark
b Wilfrid Laurier University, Department of Physics and Computer Science, 75 University Avenue West, Waterloo, Ontario N2L 3C5, Canada
c Department of Mathematics, National Technical University of Athens, Zografou 15773, Athens, Greece
d CISUC, Department of Informatics Engineering, University of Coimbra, Polo II, 3030-290 Coimbra, Portugal
a r t i c l e i n f o a b s t r a c t
Article history: WedesignheuristicalgorithmstoconstructHadamardmatriceswithtwocirculantcores.
Received3October2007 This hard combinatorial problem can be formulated in terms of objective functions of
Accepted5June2008 several binary variables, so that heuristic methodologies can be used. Our algorithms are
CommunicatedbyV.Pan basedonlocalandtabusearchandtheyuseinformationonthegeometryoftheobjective
Keywords: function landscapes. In addition, we use the supplementary difference sets formalism
Hadamardmatrices to detect when solutions of a special structure exist. Using these algorithms we have
Heuristic algorithms computed at least one Hadamard matrix with two circulant cores of the sixteen orders
56,60,64,68,72,76,80,84,88,92,96,100,104,108,112,116.Inparticular,theHadamard
matrix with two circulant cores of order 116 is constructed here for the first time, indeed
it was accidentally reported as known in an earlier paper.
©2008ElsevierB.V.Allrightsreserved.
1. Introduction
Hadamardmatriceswithtwocirculantcorescanbedefinedintermsoftheperiodicautocorrelationfunctionofthetwo
binarysequencesthatgeneratethetwocirculantcores.Theperiodicautocorrelationfunctionofasequenceisameasureof
howmuchthegivensequencediffersfromitstranslates.
Let ℓ be a positive integer and A be a (finite) sequence of ℓ real numbers {a ,a ,...,a }. The periodic autocorrelation
function P (s) is defined by 0 1 ℓ−1
A
ℓ−1
P (s) = Xaa , s=0,1,...,ℓ−1 (1)
A i=0 i i+s
wherei+sistakenmoduloℓ.
Thefollowingsymmetrypropertywillbehelpfullateron,inreducingthesizeoftheobjectivefunctionsinvolved.Suppose
that ℓ is odd. Then we have that
PA(s) = PA(ℓ − s), s = 1,..., ℓ − 1. (2)
2
Two{−1,+1}sequencesAandBbothoflengthℓsuchthattheircorrespondingPAFterms(exceptthefirstone)sumto
−2
PA(s) + PB(s) = −2, s = 1,...,ℓ−1 (3)
canbeusedasthefirstrowsofcirculantmatricesCA andCB respectively,sothatthematrix
∗ Correspondingauthor.Tel.:+15198840710.
E-mail address: ikotsire@wlu.ca (I.S. Kotsireas).
0304-3975/$–seefrontmatter©2008ElsevierB.V.Allrightsreserved.
doi:10.1016/j.tcs.2008.06.002
M.Chiarandinietal. / Theoretical Computer Science 407 (2008) 274–277 275
− − +··· + + ··· +
− + +··· + − ··· −
+ +
. .
. .
. . C C
H2ℓ+2 = A B (4)
+ +
+ −
. .
. . T T
. . C −C
+ − B A
is a Hadamardmatrixoforder2ℓ+2withtwocirculantcores.ThesuperscriptTdenotesmatrixtransposition.
AHadamardmatrixofordernisann×nmatrixH whichhas±1elementssuchthatHHT = HTH = nIn,whereIn isthe
identity matrix of order n.
Hadamard matrices with two circulant cores (also called generalized Legendre pairs) have been studied in [3] using
discreteFouriertransform,decimationandpowerspectraldensitytechniques,in[7]usingcomputationalalgebratechniques
andin[6]usingsimplegeneticalgorithm.
Sometimes it may happen that the two sequences A and B that have property (3) are equal. A sufficient condition for
whenthiscanhappen,canbeexpressedconvenientlyviasupplementarydifferencesets.See[9]and[10]forthedefinition
andpropertiesofsupplementarydifferencesets.
Thefollowingtheoremistakenfrom[2].
Theorem1. (1) If P, Q are supplementary difference sets 2 − {ℓ; k , k ; λ} and A, B are the corresponding (−1,1) incidence
1 2
matrices, then
T T
AA +BB =4(k +k −λ)I +2(ℓ−2(k +k −λ))J . (5)
1 2 ℓ 1 2 ℓ
(2) Given two ℓ × ℓ circulant matrices A, B satisfying (5), then the corresponding sets P, Q are supplementary difference sets
2−{ℓ; k , k ; λ},wherek ,k isthenumberof−1’sineachrowofA,Brespectively.
1 2 1 2
In[4]itispointedoutthatasufficientconditionfortheexistenceoftwo{−1,+1}sequencesAandBthatsatisfyproperty
(3) is the existence of an SDS 2 − {ℓ; ℓ+1, ℓ+1; ℓ+1}.
2 2 2
If in addition we are looking for such sequences, with the additional constraint that A = B, then the sufficient condition
is the existence of an (ℓ, ℓ+1, ℓ+1) difference set. In particular, this implies that ℓ ≡ 3 (mod 4). See [1] for the definition
2 4
andpropertiesofdifferencesets.
Whenℓ ≡ 3 (mod 4)isaprime,thenthequadratic residues form an (ℓ, ℓ+1, ℓ+1) difference set, so the condition is
necessaryandsufficient. 2 4
2. Objective functions
Theobjectivefunctionsthatweusedinouralgorithmsaregivenby:
OF1 = |2 +PA(1)+PB(1)|+···+|2+PA(ℓ−1)+PB(ℓ−1)|
and
2 2
OF =(2+P (1)+P (1)) +···+(2+P (ℓ−1)+P (ℓ−1)) .
2 A B A B
Note that OF and OF can be described succinctly in terms of the 1-norm and the 2-norm of the PAF vector v =
1 2
[P (1),...,P (ℓ − 1)] as follows:
A A
2
OF =kvk , OF =kvk .
1 1 2 2
Wenote that OF is a smooth and continuous function, but which attains larger values (has a bigger range) than OF , in
2 1
general. We also occasionally supplemented OF and OF with linear equations of the form
1 2
a +···+a =1, b +···+b =1, (6)
0 ℓ−1 0 ℓ−1
withoutlossofgenerality, due to the Diophantine constraint
2 2
(a +···+a ) +(b +···+b ) =2.
0 ℓ−1 0 ℓ−1
See[7], for instance, for a derivation of the Diophantine constraint above.
276 M.Chiarandinietal. / Theoretical Computer Science 407 (2008) 274–277
Notethatthesymmetryproperty(2)ofthePAFvectorcanbeusedtoreducethesizeoftheobjectivefunctionsOF and
ℓ−1 ℓ−1 1
OF byhalf, as we only need to consider its first elements. Specifically, setting m = , we may define the objective
2 2 2
functions by:
m m
X X 2
OF = |2 +P (i) +P (i)| and OF = (2 +P (i) +P (i)) .
1 A B 2 A B
i=1 i=1
Theheuristic algorithms described in this paper attempt to find values of the binary variables a ,b that make the (non-
i i
negative) objective functions OF and OF equal to zero, i.e. minimize them.
1 2
Toillustrate the difficulty of minimizing these objective functions we mention that the size of the discrete search space
{−1,+1}2ℓ(oftencalledthebooleancube)isequalto22ℓ.Aprobabilisticanalysisregardingthesizeofthesubspacedefined
byEq.(6)isgivenin[6]wherethefollowinglemmaisproved.
Lemma1. The size of the subspace of the boolean cube {−1,+1}2ℓ defined by the equations a + ··· + a = 1 and
b +···+b =1isapproximatelyπℓtimessmallerthanthesizeoftheentirebooleancube. 0 ℓ−1
1 ℓ−1 2
3. Heuristic approach
The heuristic algorithms developed for the minimization of the objective functions OF and OF are based on the tabu
1 2
search method, see [5], which has been shown to be very effective for similar hard problems with quadratic objective
functions, see for instance [8] for the Quadratic Assignment Problem. Tabu search is essentially a local search that selects
thebestsolutionfromaneighborhoodopportunelyrestrictedinordertoavoidcycling.
In our implementation, we considered two different neighborhoods. The first (N1) consists of all feasible solutions that
are obtained from another feasible solution by exchanging the sign between a (b ) and a (b ) with a 6= a (b 6= b ) and
i i j j i j i j
0 ≤ i < j ≤ ℓ − 1. The second neighborhood (N ) explores the cases in which A may be equal to B, that is, when ℓ ≡ 3
2
(mod 4)andℓisaprime.Forthisneighborhood,asignexchangebetweena anda impliesasignexchangebetweenb andb.
i j i j
2 4
Both neighborhoods are of size O(ℓ ) and it takes O(ℓ ) time to choose the best neighboring solution. However, a
faster computation of the objective function can be obtained by computing the contribution UA(s) to PA(s) of the terms
that changed. This value can be computed as follows.
aa +a a s = j − i
U (s) = −2· j φ(j+s) φ(i−s) i
A aa +a a s = ℓ −j+i
i φ(j+s) φ(i−s) j
aa +aa +aa +aa otherwise
i φ(i+s) i φ(i−s) j φ(j+s) j φ(j−s)
whereφ(x)isdefinedasamodulusfunctionφ(x) = x−ℓ⌊x⌋.ThecontributionofUB(s)toPB(s)iscomputedsimilarlywith
ℓ 3
thenecessarychanges.Hence,thebestsolutionintheneighborhoodcanbefoundinO(ℓ )time.
Our tabu search chooses at each iteration the best non-tabu or tabu but aspired solution from the neighborhood,
improving over an initial feasible solution that is generated randomly. The tabu restriction works as follows: If a selected
neighborisobtainedbyasignexchangebetweena (b)anda (b),thesameexchangeisforbiddeninA(B)forthenextiter
i i j j
2
iterations. For this reason, the indices i and j need to be maintained in an additional O(ℓ )-space data structure for each
sequence. The tabu status of a neighboring solution is overruled if it improves over the best solution found so far (known
as the aspiration criterion). If more than one neighboring solution yields the same value in the evaluation function, then
one of those neighbors is selected in lexicographic order. We restrict the neighborhood to the sequence A or B, changing
sequenceateachiteration.Somepreliminaryexperimentsindicatedthatthistabusearchmaybelesseffectiveforlargerℓ.
Therefore, if no improvement is obtained over the best solution found for a given number riter of iterations, the sequences
are reinitialized. The parameters iter and riter were set experimentally.
Thelargestobjectivefunctionthatwewereabletosolveinthispaperistheonecorrespondingtoℓ = 57.Thisobjective
114
function contains 114 binary variables, so the size of the entire search space is 2 . The solution was found within a set
of 60 runs per each different tabu length parameter from the set {0.5ℓ,1ℓ,5ℓ,10ℓ,15ℓ,20ℓ}, each run having a different
6
randomseedandconsisting of 10 seconds with internal restart every 10000 non improving iterations. The solution was
foundwithatabulengthparameterequalto0.5.
4. Results
ThetabusearchusingneighborhoodN wasrunforℓ =27,29,31,33,35,37,39,41,43,45,for10000s.Theparameter
1
iter was set equal to ℓ and riter equal to 10000 iterations. The tabu search using neighborhood N was run for ℓ = 31 and
2
43. The values for riter and iter were defined as above. Table 1 shows the number of unique solutions found by the tabu
search using neighborhoods N and N . Recently, we also found solutions for ℓ = 47,49,51,53,55,57. The solution for
1 2
ℓ = 57isgivenhereforthefirsttime.Indeed,itwasaccidentallyreportedasknownin[3].
Animplementationofthetabusearchalgorithmandtheresultsweobtainedareavailableon-lineatthewebpagehttp://
www.cargo.wlu.ca/2cc. These solutions have been used to construct Hadamard matrices with two circulant cores of the
sixteen orders 56, 60, 64, 68, 72, 76, 80, 84, 88, 92, 96, 100, 104, 108, 112, 116.
M.Chiarandinietal. / Theoretical Computer Science 407 (2008) 274–277 277
Table1
NumberofsolutionsfoundbytabusearchusingneighborhoodsN andN
1 2
ℓ 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57
N1 26525 8121 2061 372 190 46 20 1 2 1 1 1 1 1 1 1
N2 – – 1143 – – – – – 147 – – – – – – –
Acknowledgments
All computations in C have been performed remotely at SHARCnet high performance computing clusters.
ThesecondauthorissupportedbyagrantfromtheNaturalSciencesandEngineeringResearchCouncilofCanada.
References
[1] L.D. Baumert, Cyclic Difference Sets, in: Lecture Notes in Mathematics, vol. 182, Springer-Verlag, Berlin, 1971.
[2] Th. Chadjipantelis, S. Kounias, Supplementary difference sets and D-optimal designs for n ≡ 2 mod 4, Discrete Math. 57 (3) (1985) 211–216.
[3] R.J. Fletcher, M. Gysin, J. Seberry, Application of the discrete Fourier transform to the search for generalised Legendre pairs and Hadamard matrices,
Australas. J. Combin. 23 (2001) 75–86.
[4] S. Georgiou,C.Koukouvinos,OngeneralizedLegendrepairsandmultipliersofthecorrespondingsupplementarydifferencesets,Util.Math.61(2002)
47–63.
[5] F. Glover, M. Laguna, Tabu Search, in: Handbook of Combinatorial Optimization, vol. 3, Kluwer Acad. Publ, Boston, MA, 1998, pp. 621–757.
[6] I.S. Kotsireas, C. Koukouvinos, Genetic algorithms for the construction of Hadamard matrices with two circulant cores, J. Discrete Math. Sci. Cryptogr.
8(2)(2005)241–250.
[7] I.S. Kotsireas, C. Koukouvinos, J. Seberry, Hadamard ideals and Hadamard matrices with two circulant cores, European J. Combin. 27 (5) (2006)
658–668.
[8] É.D. Taillard, Comparison of iterative searches for the quadratic assignment problem, Location Sci. 3 (1995) 87–105.
[9] J. Wallis, On supplementary difference sets, Aequationes Math. 8 (1972) 242–257.
[10] J. Wallis, A note on supplementary difference sets, Aequationes Math. 10 (1974) 46–49.
no reviews yet
Please Login to review.
