In this paper we propose an algorithm for enumerating diagonal Latin squares of small order. It relies on specific properties of diagonal Latin squares to employ symmetry breaking techniques, and on several heuristic optimizations and bit arithmetic techniques to make use of computational power of state-of-the-art CPUs. Using this approach we enumerated diagonal Latin squares of order at most 9, and vertically symmetric diagonal Latin squares of order at most 10.
Authors are not aware of algorithms developed specifically for enumeration of diagonal Latin squares. Papers @cite_8 @cite_12 @cite_6 describe the approaches that led to enumeration of Latin squares of orders 9, 10 and 11. The corresponding algorithms heavily rely on the ability to permute rows and columns to construct equivalence classes and evaluate their properties. To the best of our knowledge the results of these papers are not applicable to diagonal Latin squares because the vast majority of row-column permutations break diagonal property. Also, diagonal Latin squares form relatively small equivalence classes.
@cite_6 @cite_12 @cite_8
2069392999 1729440882
We (1) determine the number of Latin rectangles with 11 columns and each possible number of rows, including the Latin squares of order 11, (2) answer some questions of Alter by showing that the number of reduced Latin squares of order n is divisible by f! where f is a particular integer close to ( 1 2 n, ) (3) provide a formula for the number of Latin squares in terms of permanents of (+1, −1)-matrices, (4) find the extremal values for the number of 1-factorisations of k-regular bipartite graphs on 2n vertices whenever 1 ≤ k ≤ n ≤ 11, (5) show that the proportion of Latin squares with a non-trivial symmetry group tends quickly to zero as the order increases. We show the existence of a large family of representations supported by the orbit closure of the determinant. However, the validity of our result is based on the validity of the celebrated ‘Latin square conjecture’ due to Alon and Tarsi or, more precisely, on the validity of an equivalent ‘column Latin square conjecture’ due to Huang and Rota. While there has been significant progress on algorithmic aspects of the Lovasz Local Lemma (LLL) in recent years, a noteworthy exception is when the LLL is used in the context of random permutations: the "lopsided" version of the LLL is usually at play here, and we do not yet have subexponential-time algorithms. We resolve this by developing a randomized polynomial-time algorithm for such applications. A noteworthy application is for Latin Transversals: the best-known general result here (, improving on Erdos and Spencer), states that any n x n matrix in which each entry appears at most (27 256)n times, has a Latin transversal. We present the first polynomial-time algorithm to construct such a transversal. Our approach also yields RNC algorithms: for Latin transversals, as well as the first efficient ones for the strong chromatic number and (special cases of) acyclic edge-coloring. Comon's (1994) well-known scheme for independent component analysis (ICA) is based on the maximal diagonalization, in a least-squares sense, of a higher-order cumulant tensor. In a previous paper, we proved that for fourth-order cumulants, the computation of an elementary Jacobi rotation is equivalent to the computation of the best rank-1 approximation of a fourth-order tensor. In this paper, we show that for third-order tensors, the computation of an elementary Jacobi rotation is again equivalent to a best rank-1 approximation; however, here, it is a matrix that has to be approximated. This favorable computational load makes it attractive to do "something third-order-like" for fourth-order cumulant tensors as well. We show that simultaneous optimal diagonalization of "third-order tensor slices" of the fourth-order cumulant is a suitable strategy. This "simultaneous third-order tensor diagonalization" approach (STOTD) is similar in spirit to the efficient JADE-algorithm. In P. Corbett et a. (2004), the authors present a row-diagonal parity scheme with two parity columns for a (p - 1) times (p + 1) array, p a prime, that recovers any two erased columns. The code minimizes the number of XORs at the encoding. It was left as an open problem generalizing this scheme to multiple parities. In this paper, we present such a generalization. In particular, when we have three parity columns, the new code recovers any three erased columns. Efficient encoding and decoding algorithms are presented Abstract In this paper we construct and theoretically analyze a class of direct projection algorithms for the numerical solution of linear least squares problems. These algorithms are obtained by adding supplementary directions for projection, constructed as linear combinations of the initial system rows and columns, in Kaczmarz and Extended Kaczmarz iterative methods. The above ideas are extended to the block row and column versions of the previously mentioned methods. The developed algorithms are then compared with other direct projection-based methods by the application to problems arising in multibody elasticity. Given an n × m nonnegative matrix A = (a ij ) and positive integral vectors r e ℜ n and c e Âm having a common one-norm h, the (r,c)-scaling problem is to obtain positive diagonal matrices X and Y, if they exist, such that XAY has row and column sums equal to r and c, respectively. The entropy minimization problem corresponding to A is to find an n × m matrix z = (z ij ) having the same zero pattern as A, the sum of whose entries is a given number h, its row and column sums are within given integral vectors of lower and upper bounds, and such that the entropy function consisting of the sum of the terms z ij ln (z ij a ij ) is minimized. When the lower and upper bounds coincide, matrix scaling and entropy minimization are closely related. In this paper we present several complexity bounds for the e-approximate (r,c)-scaling problem, polynomial in n,m,h, 1 e, and ln V v, where V and v are the largest and the smallest positive entries of A, respectively. These bounds, although not polynomial in ln(1 1 e), not only provide alternative complexities for the polynomial time algorithms, but could result in better overall complexities. In particular, our theoretical analysis supports the practicality of the well-known RAS algorithm. In our analysis we obtain bounds on the norm of scaling vectors which will be used in deriving not only some of the above complexities, but also a complexity for square nonnegative matrices having positive permanent. In particular, our results extend, nontrivially, many bounds for the doubly stochastic scaling of square nonnegative matrices previously given by Kalantari and Khachiyan to the case of general (r,c)-scaling. Finally, we study a more general entropy minimization problem where row and column sums are constrained to lie in prescribed intervals, and the sum of all entries is also prescribed. Balinski and Demange described an RAS type algorithm for its continuous version, but did not analyze its complexity. We show that this algorithm produces an 1 e-approximate solution within complexity polynomial in n, m, h, V v and 1 1 e. Many fields rely on some stochastic sampling of a given complex space. Low-discrepancy sequences are methods aiming at producing samples with better space-filling properties than uniformly distributed random numbers, hence allowing a more efficient sampling of that space. State-of-the-art methods like nearly orthogonal Latin hypercubes and scrambled Halton sequences are configured by permutations of internal parameters, where permutations are commonly done randomly. This paper proposes the use of evolutionary algorithms to evolve these permutations, in order to optimize a discrepancy measure. Results show that an evolutionary method is able to generate low-discrepancy sequences of significantly better space-filling properties compared to sequences configured with purely random permutations. The functional source coding problem in which the receiver side information (Has-set) and demands (Want-set) include functions of source messages is studied using row-Latin rectangle. The source transmits encoded messages, called the functional source code, in order to satisfy the receiver's demands. We obtain a minimum length using the row-Latin rectangle. Next, we consider the case of transmission errors and provide a necessary and sufficient condition that a functional source code must satisfy so that the receiver can correctly decode the values of the functions in its Want-set. This article presents a fast solver for the dense "frontal" matrices that arise from the multifrontal sparse elimination process of 3D elliptic PDEs. The solver relies on the fact that these matrices can be efficiently represented as a hierarchically off-diagonal low-rank (HODLR) matrix. To construct the low-rank approximation of the off-diagonal blocks, we propose a new pseudo-skeleton scheme, the boundary distance low-rank approximation, that picks rows and columns based on the location of their corresponding vertices in the sparse matrix graph. We compare this new low-rank approximation method to the adaptive cross approximation (ACA) algorithm and show that it achieves better speedup specially for unstructured meshes. Using the HODLR direct solver as a preconditioner (with a low tolerance) to the GMRES iterative scheme, we can reach machine accuracy much faster than a conventional LU solver. Numerical benchmarks are provided for frontal matrices arising from 3D finite element problems corresponding to a wide range of applications. In a typical communications problem, Toeplitz matrices Φ arise when modeling the task of determining an unknown impulse response a from a given probe signal φ. When a is sparse, then whenever Φ formed from the probe signal φ satisfy the Restricted Isometry Property (RIP), a can be robustly recovered from its measurements via l1-minimization. In this paper, we derived the RIP for compressive Toeplitz matrices whose number of rows of the matrices J is much smaller than the number of columns N . We show that J should scale like J ∼ S log(N), where S is the sparsity of the impulse response. While this is marginally worse than the state-of-the-art scaling currently achieved in the literature, the novelty of this work comes from making the relation between the Toeplitz matrix of interest to a block diagonal matrix. The proof of the RIP then follows from using recent results on the concentration of measure inequalities of block diagonal matrices, together with a standard covering-and-counting argument. A numerically stable and fairly fast scheme is described to compute the unitary matrices U and V which transform a given matrix A into a diagonal form @math , thus exhibiting A’s singular values on @math ’s diagonal. The scheme first transforms A to a bidiagonal matrix J, then diagonalizes J. The scheme described here is complicated but does not suffer from the computational difficulties which occasionally afflict some previously known methods. Some applications are mentioned, in particular the use of the pseudo-inverse @math to solve least squares problems in a way which dampens spurious oscillation and cancellation. In this paper we present an algorithm which, for a given (sparse) matrix, constructs a partition of its set of row-indices, such that each subset of this partition (except the last one obtained) contains indices which correspond to mutually orthogonal rows. We then use such decompositions in some classes of block-projections methods, previously extended by the author to general inconsistent linear least-squares problems. Numerical experiments on an inconsistent and rank-deficient least-squares model problem are described in the last section of the paper. We provide a tight-binding model of insulator, for which we derive an exact analytic form of the one-body density matrix and its large-distance asymptotics in dimensions @math . The system is built out of a band of single-particle orbitals in a periodic potential. Breaking of the translational symmetry of the system results in two bands, separated by a direct gap whose width is proportional to the unique energy parameter of the model. The form of the decay is a power law times an exponential. We determine the power in the power law and the correlation length in the exponential, versus the lattice direction, the direct-gap width, and the lattice dimension. In particular, the obtained exact formulae imply that in the diagonal direction of the square lattice the inverse correlation length vanishes linearly with the vanishing gap, while in non-diagonal directions, the linear scaling is replaced by the square root one. Independently of direction, for sufficiently large gaps the inverse correlation length grows logarithmically with the gap width. A discrete uncoupling process for finite spaces is introduced, called the Markov Cluster Process or the MCL process. The process is the engine for the graph clustering algorithm called the MCL algorithm. The MCL process takes a stochastic matrix as input, and then alternates expansion and inflation, each step defining a stochastic matrix in terms of the previous one. Expansion corresponds with taking the @math th power of a stochastic matrix, where @math . Inflation corresponds with a parametrized operator @math , @math , that maps the set of (column) stochastic matrices onto itself. The image @math is obtained by raising each entry in @math to the @math th power and rescaling each column to have sum 1 again. In practice the process converges very fast towards a limit that is invariant under both matrix multiplication and inflation, with quadratic convergence around the limit points. The heuristic behind the process is its expected behavior for (Markov) graphs possessing cluster structure. The process is typically applied to the matrix of random walks on a given graph @math , and the connected components of (the graph associated with) the process limit generically allow a clustering interpretation of @math . The limit is in general extremely sparse and iterands are sparse in a weighted sense, implying that the MCL algorithm is very fast and highly scalable. Several mathematical properties of the MCL process are established. Most notably, the process (and algorithm) iterands posses structural properties generalizing the mapping from process limits onto clusterings. The inflation operator @math maps the class of matrices that are diagonally similar to a symmetric matrix onto itself. The phrase diagonally positive semi-definite (dpsd) is used for matrices that are diagonally similar to a positive semi-definite matrix. For @math and for @math a stochastic dpsd matrix, the image @math is again dpsd. Determinantal inequalities satisfied by a dpsd matrix @math imply a natural ordering among the diagonal elements of @math , generalizing the mapping of process limits onto clusterings. The spectrum of @math is of the form @math , where @math is the number of endclasses of the ordering associated with @math , and @math is the dimension of @math . This attests to the uncoupling effect of the inflation operator. Matrix computations are expensive, and GPUs have the potential to deliver results at reduced cost by exploiting parallel computation. We focus on dense matrices of the form AD 2 A T , where A is an m◊n matrix (m n) and D is an n ◊ n diagonal matrix. Many important numerical problems require solving linear systems of equations involving matrices of this form. These problems include normal equations approaches to solving linear least squares and weighted linear least squares problems, and interior point algorithms for linear and nonlinear programming problems. We develop in this work ecient Several blind source separation algorithms obtain a separating matrix by computing the congruence transformation that "best" diagonalizes a collection of covariance matrices. Recent methods avoid a pre-whitening phase and directly attempt to compute a non-orthogonal diagonalizing congruence. However, since the magnitude of the sources is unknown, there is a fundamental indeterminacy on the norm of the rows of the separating matrix. We show how this indeterminacy can be taken into account by restricting the separating matrix to the oblique manifold. The geometry of this manifold is developed and a trust-region-based algorithm for non-orthogonal joint diagonalization is proposed. A key feature of constraint programming is the ability to design specific search strategies to solve problems. On the contrary, integer programming solvers have used efficient general-purpose strategies since their earliest implementations. We present a new general purpose search strategy for constraint programming inspired from integer programming techniques and based on the concept of the impact of a variable. The impact measures the importance of a variable for the reduction of the search space. Impacts are learned from the observation of domain reduction during search and we show how restarting search can dramatically improve performance. Using impacts for solving multiknapsack, magic square, and Latin square completion problems shows that this new criteria for choosing variables and values can outperform classical general-purpose strategies. A binary superimposed code consists of a set of code words whose digit-by-digit Boolean sums (1 + 1 = 1) enjoy a prescribed level of distinguishability. These codes find their main application in the representation of document attributes within an information retrieval system, but might also be used as a basis for channel assignments to relieve congestion in crowded communications bands. In this paper some basic properties of nonrandom codes of this family are presented, and formulas and bounds relating the principal code parameters are derived. Finally, there are described several such code families based upon (1) q -nary conventional error-correcting codes, (2) combinatorial arrangements, such as block designs and Latin squares, (3) a graphical construction, and (4) the parity-check matrices of standard binary error-correcting codes. Vast amounts of information is available in structured forms like spreadsheets, database relations, and tables found in documents and on the Web. We describe an approach that uses linked data to interpret such tables and associate their components with nodes in a reference linked data collection. Our proposed framework assigns a class (i.e. type) to table columns, links table cells to entities, and inferred relations between columns to properties. The resulting interpretation can be used to annotate tables, confirm existing facts in the linked data collection, and propose new facts to be added. Our implemented prototype uses DBpedia as the linked data collection and Wikitology for background knowledge. We evaluated its performance using a collection of tables from Google Squared, Wikipedia and the Web.