New weighing matrices of weight 25

The existence of a weighing matrix of order 33 and weight 25 has been open so far. We actually construct such a circulant matrix, thereby obtaining circulant matrices of order 33t with weight 25, for each positive integer t. Consequently a missing entry in Craigen's table of weighing matrices can now be filled with a positive response. © 1999 John Wiley & Sons, Inc. J Combin Designs 7: 11–15, 1999     

Circulant weighing matrices of weight 22t

A weighing matrix of weight k is a square matrix M with entries 0, ± 1 such that MM ^T = kI _n . We study the case that M is a circulant and k = 2^2t for some positive integer t. New structural results are obtained. Based on these results, we make a complete computer search for all circulant weighing matrices of order 16.      

Finiteness of circulant weighing matrices of fixed weight

Let n be a fixed positive integer. Every circulant weighing matrix of weight n arises from what we call an irreducible orthogonal family of weight n. We show that the number of irreducible orthogonal families of weight n is finite and thus obtain a finite algorithm for classifying all circulant weighing matrices of weight n. We also show that, for every odd prime power q, there are at most finitely many proper circulant weighing matrices of weight q.     

Proper circulant weighing matrices of weight p^2

A circulant weighing matrix \(CW(v,n)\) is a circulant matrix \(M\) of order \(v\) with \(0,\pm 1\) entries such that \(MM^T=nI_v\) . In this paper, we study proper circulant matrices with \(n=p^2\) where \(p\) is an odd prime divisor of \(v\) . For \(p\ge 5\) , it turns out that to search for such circulant matrices leads us to two group ring equations and by studying these two equations, we manage to prove that no proper \(CW(pw,p^2)\) exists when \(p\equiv 3\pmod {4}\) or \(p=5\) .     

An efficient algorithm for maximum entropy extension of block-circulant covariance matrices

This paper deals with maximum entropy completion of partially specified block-circulant matrices. Since positive definite symmetric circulants happen to be covariance matrices of stationary periodic processes, in particular of stationary reciprocal processes, this problem has applications in signal processing, in particular to image modeling. In fact it is strictly related to maximum likelihood estimation of bilateral AR-type representations of acausal signals subject to certain conditional independence constraints. The maximum entropy completion problem for block-circulant matrices has recently been solved by the authors, although leaving open the problem of an efficient computation of the solution. In this paper, we provide an efficient algorithm for computing its solution which compares very favorably with existing algorithms designed for positive definite matrix extension problems. The proposed algorithm benefits from the analysis of the relationship between our problem and the band-extension problem for block-Toeplitz matrices also developed in this paper.     

Study of proper circulant weighing matrices with weight 9

We provide the first theoretical proof of the spectrum of orders n for which circulant weighing matrices with weight 9 exist. This spectrum consists of those positive integers n, which are multiples of 13 or 24. We actually characterize the “minimal” examples which exist for orders 13, 26, or 24.     

An efficient and accurate parallel algorithm for the singular value problem of bidiagonal matrices

Summary. In this paper we propose an algorithm based on Laguerre's iteration, rank two divide-and-conquer technique and a hybrid strategy for computing singular values of bidiagonal matrices. The algorithm is fully parallel in nature and evaluates singular values to tiny relative error if necessary. It is competitive with QR algorithm in serial mode in speed and advantageous in computing partial singular values. Error analysis and numerical results are presented. Received March 15, 1993 / Revised version received June 7, 1994     

An eigenvalue algorithm for skew-symmetric matrices

A Jacobi-like algorithm is presented for the skew-symmetric eigenvalue problem. The process constructs iteratively, with elementary orthogonal transformations, a sequence of matrices which converges to the so-called Murnaghan form of the intial matrix.     

An algorithm for determining copositive matrices

In this paper, we present an algorithm of simple exponential growth called COPOMATRIX for determining the copositivity of a real symmetric matrix. The core of this algorithm is a decomposition theorem, which is used to deal with simplicial subdivision of on the standard simplex Δ_m, where each component of the vector β is −1, 0 or 1.     

An efficient algorithm for linear programming

A simple but efficient algorithm is presented for linear programming. The algorithm computes the projection matrix exactly once throughout the computation unlike that of Karmarkar’s algorithm where in the projection matrix is computed at each and every iteration. The algorithm is best suitable to be implemented on a parallel architecture. Complexity of the algorithm is being studied.     

An efficient algorithm for voting sequences

The chaos theorems show that given almost any alternatives x and y, there exists voting sequence from x to y. However, proofs of such results have been purely existential; that is, there is no algorithm by which such a voting path can be constructed. In this paper, we present such an algorithm for one standard example. Furthermore, it is shown that the algorithm has the property that the voting sequence involves the fewest possible number of steps.     

An efficient algorithm for solving inequalities

An efficient algorithm for solving a finite system of inequalities in a finite number of iterations is described and analyzed.This work was supported by the UK Science and Engineering Research Council     

An approximation algorithm for sorting by reversals and transpositions

Genome rearrangement algorithms are powerful tools to analyze gene orders in molecular evolution. Analysis of genomes evolving by reversals and transpositions leads to a combinatorial problem of sorting by reversals and transpositions, the problem of finding a shortest sequence of reversals and transpositions that sorts one genome into the other. In this paper we present a 2k-approximation algorithm for sorting by reversals and transpositions for unsigned permutations where k is the approximation ratio of the algorithm used for cycle decomposition. For the best known value of k our approximation ratio becomes 2.8386+δ for any δ>0. We also derive a lower bound on reversal and transposition distance of an unsigned permutation.     

An efficient algorithm for enumeration of triangulations

We consider the problem of enumerating triangulations of n points in the plane in general position. We introduce a tree of triangulations and present an algorithm for enumerating triangulations in O(loglogn) time per triangulation. It improves the previous bound by almost linear factor.     

An implicit QR algorithm for symmetric semiseparable matrices

The QR algorithm is one of the classical methods to compute the eigendecomposition of a matrix. If it is applied on a dense n × n matrix, this algorithm requires O(n³) operations per iteration step. To reduce this complexity for a symmetric matrix to O(n), the original matrix is first reduced to tridiagonal form using orthogonal similarity transformations. In the report (Report TW360, May 2003) a reduction from a symmetric matrix into a similar semiseparable one is described. In this paper a QR algorithm to compute the eigenvalues of semiseparable matrices is designed where each iteration step requires O(n) operations. Hence, combined with the reduction to semiseparable form, the eigenvalues of symmetric matrices can be computed via intermediate semiseparable matrices, instead of tridiagonal ones. The eigenvectors of the intermediate semiseparable matrix will be computed by applying inverse iteration to this matrix. This will be achieved by using an O(n) system solver, for semiseparable matrices. A combination of the previous steps leads to an algorithm for computing the eigenvalue decompositions of semiseparable matrices. Combined with the reduction of a symmetric matrix towards semiseparable form, this algorithm can also be used to calculate the eigenvalue decomposition of symmetric matrices. The presented algorithm has the same order of complexity as the tridiagonal approach, but has larger lower order terms. Numerical experiments illustrate the complexity and the numerical accuracy of the proposed method. Copyright © 2005 John Wiley & Sons, Ltd.     

An efficient method for computing the inverse of arrowhead matrices

In this paper we propose a simple and effective method to find the inverse of arrowhead matrices which often appear in wide areas of applied science and engineering such as wireless communications systems, molecular physics, oscillators vibrationally coupled with Fermi liquid, and eigenvalue problems. A modified Sherman–Morrison inverse matrix method is proposed for computing the inverse of an arrowhead matrix. The effectiveness of the proposed method is illustrated and numerical results are presented along with comparative results.     

An efficient heuristic algorithm for minimum matching

We give a new heuristic algorithm for minimum matching problems and apply it to the Euclidean problem with random vertices in 2 dimensions. The algorithm is based on simulated annealing and performs in practice faster than previous heuristic algorithms yielding suboptimal solutions of the same good quality. From configurations with up toN=20.000 vertices in the unit square we estimate that the length of a minimum matching scales asymptotically asLN with (=0.3123±0.0016.

---

Zusammenfassung Wir stellen einen neuen heuristischen Algorithmus für minimale Matching-Probleme vor und wenden diesen auf das euklidische Problem mit zufÄlliger Punkteverteilung in 2 Dimensionen an. Auf Simulated Annealing basierend lÄuft der Algorithmus schneller als frühere heuristische Algorithmen und erreicht dabei suboptimale Lösungen gleich guter QualitÄt. Aus Konfigurationen mit bis zuN=20.000 Punkten im Einheitsquadrat schÄtzen wir, da\ für die LÄnge des minimalen Matchings asymptotischLN mit=0.3123±0.0016 gilt.