Página 1 dos resultados de 73 itens digitais encontrados em 0.007 segundos

## Modificações na fatoração controlada de Cholesky para acelerar o precondicionamento de sistemas lineares no contexto de pontos interiores; Modifications on controlled Cholesky factorization to improve the preconditioning in interior point method

Fonte: Biblioteca Digital da Unicamp
Publicador: Biblioteca Digital da Unicamp

Tipo: Tese de Doutorado
Formato: application/pdf

Publicado em 02/09/2014
PT

Relevância na Pesquisa

36.13%

#Precondicionadores#Métodos de pontos interiores#Fatoração de Cholesky incompleta#Preconditioners#Incomplete Cholesky factorization#Interior point method

O método de pontos interiores para programação linear resolve em poucas iterações problemas de grande porte. No entanto, requer a cada iteração a resolução de dois sistemas lineares, os quais possuem a mesma matriz de coeficientes. Essa etapa se constitui no passo mais caro do método por aumentar consideravelmente o tempo de processamento e a necessidade de armazenamento de dados. Reduzir o tempo de solução dos sistemas lineares é, portanto, uma forma de melhorar o desempenho do método. De um modo geral, problemas de programação linear de grande porte possuem matrizes esparsas. Uma vez que os sistemas lineares a serem resolvidos são simétricos positivos definidos, métodos iterativos como o método dos gradientes conjugados precondicionado podem ser utilizados na resolução dos mesmos. Além disso, fatores de Cholesky incompletos podem ser utilizados como precondicionadores para o problema. Por outro lado, fatorações incompletas podem sofrer falhas na diagonal durante o processo de fatoração, e quando tais falhas ocorrem uma correção é efetuada somando-se um valor positivo aos elementos da diagonal da matriz do sistema linear e a fatoração da nova matriz é reiniciada, aumentando dessa forma o tempo de precondicionamento...

Link permanente para citações:

## A parallel algorithm for the reduction to tridiagonal form for eigendecomposition

Fonte: Universidade Nacional da Austrália
Publicador: Universidade Nacional da Austrália

Tipo: Working/Technical Paper
Formato: 247019 bytes; 356 bytes; application/pdf; application/octet-stream

EN_AU

Relevância na Pesquisa

35.95%

#orthogonal reduction#tridiagonal form#eigensolver#Symmetric eigenvalue problems#parallel algorithm#eigenvectors

A new algorithm for the orthogonal reduction of a symmetric matrix to tridiagonal form is developed and analysed. It uses a Cholesky factorization of the original matrix and the rotations are applied to the factors. The idea is similar to the one used for the one-sided Jacobi algorithms [B. Zhou and R. Brent, A Parallel Ordering Algorithm for Efficient One-Sided Jacobi SVD Computations, Proc. Sixth IASTED-ISMM International Conference on Parallel and Distributed Computing and Systems, pp. 369{372, 1994.]. The algorithm uses little communication, accesses data with stride one and is to a large extent independent of data distribution. It has been implemented on the Fujitsu VPP 500. The algorithm is designed to be the first step of an eigensolver so the procedure for accumulating transforms for eventual calculation of eigenvectors is given.; no

Link permanente para citações:

## On the stability of the Bareiss and related Toeplitz factorization algorithms

Fonte: Universidade Nacional da Austrália
Publicador: Universidade Nacional da Austrália

Tipo: Working/Technical Paper
Formato: 219556 bytes; 356 bytes; application/pdf; application/octet-stream

EN_AU

Relevância na Pesquisa

36.29%

#numerical stability analysis#factorization algorithms#Cholesky decomposition#symmetric positive definite matrices#Bareiss algorithm#Toeplitz matrix#Levinson algorithm#elementary downdating#symmetric factorization,

This paper contains a numerical stability analysis of factorization algorithms for computing the Cholesky decomposition of symmetric positive definite matrices of displacement rank 2. The algorithms in the class can be expressed as sequences of elementary downdating steps. The stability of the factorization algorithms follows directly from the numerical properties of algorithms for realizing elementary downdating operations. It is shown that the Bareiss algorithm for factorizing a symmetric positive definite Toeplitz matrix is in the class and hence the Bareiss algorithm is stable. Some numerical experiments that compare behavior of the Bareiss algorithm and the Levinson algorithm are presented. These experiments indicate that in general (when the reection coefficients are not all positive) the Levinson algorithm can give much larger residuals than the Bareiss algorithm.; no

Link permanente para citações:

## Efficient VLSI architectures for matrix factorizations

Fonte: Universidade Rice
Publicador: Universidade Rice

ENG

Relevância na Pesquisa

35.95%

The SVD (Singular Value Decomposition) is a critical matrix factorization in many real-time computations from an application domain which includes signal processing and robotics; and complex data matrices are encountered in engineering practice. This thesis advocates the use of CORDIC (Coordinate Rotation Digital Computer) arithmetic for parallel computation of the SVD/eigenvalue decomposition of arbitrary complex/Hermitian matrices using Jacobi-like algorithms on processor arrays.
The algorithms and architectures derive from extending the theory of Jacobi-like matrix factorizations to multi-step and inexact pivot (2 x 2) sub-matrix diagonalizations. Based on the former approach of multi-step diagonalization, and using a two-sided 2 x 2 unitary transformation amenable to CORDIC termed ${cal Q}$ transformation, it is shown that an arbitrary complex 2 x 2 matrix may be diagonalized in at most two ${cal Q}$ transformations while one ${cal Q}$ transformation is sufficient to diagonalize a 2 x 2 Hermitian matrix. Inexact diagonalizations from the use of approximations to the desired transformations have been advocated in the context of Jacobi-like algorithms for reasons of efficiency. Through a unifying parameterization of approximations...

Link permanente para citações:

## Computing matrix symmetrizers. Part 2: new methods using eigendata and linear means; a comparison

Fonte: Elsevier
Publicador: Elsevier

Tipo: info:eu-repo/semantics/acceptedVersion; info:eu-repo/semantics/article

Publicado em 10/07/2015
ENG

Relevância na Pesquisa

76.29%

#Symmetric matrix factorization#symmetrizer#symmetrizer computation#eigenvalue method#linear equation#principal subspace computation#matrix optimization#numerical algorithm#MATLAB code#Matemáticas

Over any field F every square matrix A can be factored into the product of two symmetric matrices as A = S1 . S2 with S_i = S_i^T ∈ F^(n,n) and either factor can be chosen nonsingular, as was discovered by Frobenius in 1910. Frobenius’ symmetric matrix factorization has been lying almost dormant for a century. The first successful method for computing matrix symmetrizers, i.e., symmetric matrices S such that SA is symmetric, was inspired by an iterative linear systems algorithm of Huang and Nong (2010) in 2013 [29, 30]. The resulting iterative algorithm has solved this computational problem over R and C, but at high computational cost. This paper develops and tests another linear equations solver, as well as eigen- and principal vector or Schur Normal Form based algorithms for solving the matrix symmetrizer problem numerically. Four new eigendata based algorithms use, respectively, SVD based principal vector chain constructions, Gram-Schmidt orthogonalization techniques, the Arnoldi method, or the Schur Normal Form of A in their formulations. They are helped by Datta’s 1973 method that symmetrizes unreduced Hessenberg matrices directly. The eigendata based methods work well and quickly for generic matrices A and create well conditioned matrix symmetrizers through eigenvector dyad accumulation. But all of the eigen based methods have differing deficiencies with matrices A that have ill-conditioned or complicated eigen structures with nontrivial Jordan normal forms. Our symmetrizer studies for matrices with ill-conditioned eigensystems lead to two open problems of matrix optimization.; This research was partially supported by the Ministerio de Economía y Competitividad of Spain through the research grant MTM2012-32542.

Link permanente para citações:

## A Symmetric Rank-one Quasi Newton Method for Non-negative Matrix Factorization

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 24/05/2013

Relevância na Pesquisa

46.16%

#Mathematics - Numerical Analysis#Computer Science - Learning#Computer Science - Numerical Analysis#15A18

As we all known, the nonnegative matrix factorization (NMF) is a dimension
reduction method that has been widely used in image processing, text
compressing and signal processing etc. In this paper, an algorithm for
nonnegative matrix approximation is proposed. This method mainly bases on the
active set and the quasi-Newton type algorithm, by using the symmetric rank-one
and negative curvature direction technologies to approximate the Hessian
matrix. Our method improves the recent results of those methods in [Pattern
Recognition, 45(2012)3557-3565; SIAM J. Sci. Comput., 33(6)(2011)3261-3281;
Neural Computation, 19(10)(2007)2756-2779, etc.]. Moreover, the object function
decreases faster than many other NMF methods. In addition, some numerical
experiments are presented in the synthetic data, imaging processing and text
clustering. By comparing with the other six nonnegative matrix approximation
methods, our experiments confirm to our analysis.; Comment: 19 pages, 13 figures, Submitted to PP on Feb. 5, 2013

Link permanente para citações:

## Explicit Integration of the Full Symmetric Toda Hierarchy and the Sorting Property

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 22/02/1995

Relevância na Pesquisa

35.92%

We give an explicit formula for the solution to the initial value
problem of the full symmetric Toda hierarchy. The formula is obtained
by the orthogonalization procedure of Szeg\"{o}, and is also
interpreted as a consequence of the QR factorization method of Symes
\cite{symes}. The sorting property of the dynamics is also proved
for the case of a generic symmetric matrix in the sense described in the text,
and generalizations of tridiagonal formulae are given for the
case of matrices with $2M+1$ nonzero diagonals.; Comment: 13 pages, Latex.

Link permanente para citações:

## Symmetric Determinantal Representations in Characteristic 2

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Relevância na Pesquisa

35.92%

This paper studies Symmetric Determinantal Representations (SDR) in
characteristic 2, that is the representation of a multivariate polynomial P by
a symmetric matrix M such that P=det(M), and where each entry of M is either a
constant or a variable.
We first give some sufficient conditions for a polynomial to have an SDR. We
then give a non-trivial necessary condition, which implies that some
polynomials have no SDR, answering a question of Grenet et al.
A large part of the paper is then devoted to the case of multilinear
polynomials. We prove that the existence of an SDR for a multilinear polynomial
is equivalent to the existence of a factorization of the polynomial in certain
quotient rings. We develop some algorithms to test the factorizability in these
rings and use them to find SDRs when they exist. Altogether, this gives us
polynomial-time algorithms to factorize the polynomials in the quotient rings
and to build SDRs. We conclude by describing the case of Alternating
Determinantal Representations in any characteristic.; Comment: 24 pages, 3 figures

Link permanente para citações:

## Overlapping Community Detection in Complex Networks using Symmetric Binary Matrix Factorization

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 23/03/2013

Relevância na Pesquisa

46.08%

Discovering overlapping community structures is a crucial step to
understanding the structure and dynamics of many networks. In this paper we
develop a symmetric binary matrix factorization model (SBMF) to identify
overlapping communities. Our model allows us not only to assign community
memberships explicitly to nodes, but also to distinguish outliers from
overlapping nodes. In addition, we propose a modified partition density to
evaluate the quality of community structures. We use this to determine the most
appropriate number of communities. We evaluate our methods using both synthetic
benchmarks and real world networks, demonstrating the effectiveness of our
approach.

Link permanente para citações:

## Coordinate Descent Methods for Symmetric Nonnegative Matrix Factorization

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 04/09/2015

Relevância na Pesquisa

46.19%

#Computer Science - Numerical Analysis#Computer Science - Computer Vision and Pattern Recognition#Computer Science - Learning#Mathematics - Optimization and Control#Statistics - Machine Learning

Given a symmetric nonnegative matrix $A$, symmetric nonnegative matrix
factorization (symNMF) is the problem of finding a nonnegative matrix $H$,
usually with much fewer columns than $A$, such that $A \approx HH^T$. SymNMF
can be used for data analysis and in particular for various clustering tasks.
In this paper, we propose simple and very efficient coordinate descent schemes
to solve this problem, and that can handle large and sparse input matrices. The
effectiveness of our methods is illustrated on synthetic and real-world data
sets, and we show that they perform favorably compared to recent
state-of-the-art methods.; Comment: 25 pages, 7 figures, 6 tables

Link permanente para citações:

## Fast symmetric factorization of hierarchical matrices with applications

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 01/05/2014

Relevância na Pesquisa

26.28%

#Mathematics - Numerical Analysis#Computer Science - Numerical Analysis#Physics - Fluid Dynamics#Statistics - Computation

We present a fast direct algorithm for computing symmetric factorizations,
i.e. $A = WW^T$, of symmetric positive-definite hierarchical matrices with
weak-admissibility conditions. The computational cost for the symmetric
factorization scales as $\mathcal{O}(n \log^2 n)$ for hierarchically
off-diagonal low-rank matrices. Once this factorization is obtained, the cost
for inversion, application, and determinant computation scales as
$\mathcal{O}(n \log n)$. In particular, this allows for the near optimal
generation of correlated random variates in the case where $A$ is a covariance
matrix. This symmetric factorization algorithm depends on two key ingredients.
First, we present a novel symmetric factorization formula for low-rank updates
to the identity of the form $I+UKU^T$. This factorization can be computed in
$\mathcal{O}(n)$ time, if the rank of the perturbation is sufficiently small.
Second, combining this formula with a recursive divide-and-conquer strategy,
near linear complexity symmetric factorizations for hierarchically structured
matrices can be obtained. We present numerical results for matrices relevant to
problems in probability \& statistics (Gaussian processes), interpolation
(Radial basis functions), and Brownian dynamics calculations in fluid mechanics
(the Rotne-Prager-Yamakawa tensor).; Comment: 15 pages...

Link permanente para citações:

## The Matrix Ridge Approximation: Algorithms and Applications

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 17/12/2013

Relevância na Pesquisa

35.96%

We are concerned with an approximation problem for a symmetric positive
semidefinite matrix due to motivation from a class of nonlinear machine
learning methods. We discuss an approximation approach that we call {matrix
ridge approximation}. In particular, we define the matrix ridge approximation
as an incomplete matrix factorization plus a ridge term. Moreover, we present
probabilistic interpretations using a normal latent variable model and a
Wishart model for this approximation approach. The idea behind the latent
variable model in turn leads us to an efficient EM iterative method for
handling the matrix ridge approximation problem. Finally, we illustrate the
applications of the approximation approach in multivariate data analysis.
Empirical studies in spectral clustering and Gaussian process regression show
that the matrix ridge approximation with the EM iteration is potentially
useful.

Link permanente para citações:

## A Hebbian/Anti-Hebbian Network Derived from Online Non-Negative Matrix Factorization Can Cluster and Discover Sparse Features

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 02/03/2015

Relevância na Pesquisa

46.02%

#Quantitative Biology - Neurons and Cognition#Computer Science - Neural and Evolutionary Computing#Statistics - Machine Learning

Despite our extensive knowledge of biophysical properties of neurons, there
is no commonly accepted algorithmic theory of neuronal function. Here we
explore the hypothesis that single-layer neuronal networks perform online
symmetric nonnegative matrix factorization (SNMF) of the similarity matrix of
the streamed data. By starting with the SNMF cost function we derive an online
algorithm, which can be implemented by a biologically plausible network with
local learning rules. We demonstrate that such network performs soft clustering
of the data as well as sparse feature discovery. The derived algorithm
replicates many known aspects of sensory anatomy and biophysical properties of
neurons including unipolar nature of neuronal activity and synaptic weights,
local synaptic plasticity rules and the dependence of learning rate on
cumulative neuronal activity. Thus, we make a step towards an algorithmic
theory of neuronal function, which should facilitate large-scale neural circuit
simulations and biologically inspired artificial intelligence.; Comment: 2014 Asilomar Conference on Signals, Systems and Computers

Link permanente para citações:

## A Hebbian/Anti-Hebbian Network for Online Sparse Dictionary Learning Derived from Symmetric Matrix Factorization

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Relevância na Pesquisa

66.23%

#Quantitative Biology - Neurons and Cognition#Computer Science - Neural and Evolutionary Computing#Statistics - Machine Learning

Olshausen and Field (OF) proposed that neural computations in the primary
visual cortex (V1) can be partially modeled by sparse dictionary learning. By
minimizing the regularized representation error they derived an online
algorithm, which learns Gabor-filter receptive fields from a natural image
ensemble in agreement with physiological experiments. Whereas the OF algorithm
can be mapped onto the dynamics and synaptic plasticity in a single-layer
neural network, the derived learning rule is nonlocal - the synaptic weight
update depends on the activity of neurons other than just pre- and postsynaptic
ones - and hence biologically implausible. Here, to overcome this problem, we
derive sparse dictionary learning from a novel cost-function - a regularized
error of the symmetric factorization of the input's similarity matrix. Our
algorithm maps onto a neural network of the same architecture as OF but using
only biologically plausible local learning rules. When trained on natural
images our network learns Gabor-filter receptive fields and reproduces the
correlation among synaptic weights hard-wired in the OF network. Therefore,
online symmetric matrix factorization may serve as an algorithmic theory of
neural computation.; Comment: 2014 Asilomar Conference on Signals...

Link permanente para citações:

## Community detection in bipartite networks using weighted symmetric binary matrix factorization

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 16/02/2015

Relevância na Pesquisa

46.08%

In this paper we propose weighted symmetric binary matrix factorization
(wSBMF) framework to detect overlapping communities in bipartite networks,
which describe relationships between two types of nodes. Our method improves
performance by recognizing the distinction between two types of missing
edges---ones among the nodes in each node type and the others between two node
types. Our method can also explicitly assign community membership and
distinguish outliers from overlapping nodes, as well as incorporating existing
knowledge on the network. We propose a generalized partition density for
bipartite networks as a quality function, which identifies the most appropriate
number of communities. The experimental results on both synthetic and
real-world networks demonstrate the effectiveness of our method.; Comment: International Journal of Modern Physics C (2014)

Link permanente para citações:

## Resolution-limit-free and local Non-negative Matrix Factorization quality functions for graph clustering

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 22/07/2014

Relevância na Pesquisa

45.98%

Many graph clustering quality functions suffer from a resolution limit, the
inability to find small clusters in large graphs. So called
resolution-limit-free quality functions do not have this limit. This property
was previously introduced for hard clustering, that is, graph partitioning.
We investigate the resolution-limit-free property in the context of
Non-negative Matrix Factorization (NMF) for hard and soft graph clustering. To
use NMF in the hard clustering setting, a common approach is to assign each
node to its highest membership cluster. We show that in this case symmetric NMF
is not resolution-limit-free, but that it becomes so when hardness constraints
are used as part of the optimization. The resulting function is strongly linked
to the Constant Potts Model. In soft clustering, nodes can belong to more than
one cluster, with varying degrees of membership. In this setting
resolution-limit-free turns out to be too strong a property. Therefore we
introduce locality, which roughly states that changing one part of the graph
does not affect the clustering of other parts of the graph. We argue that this
is a desirable property, provide conditions under which NMF quality functions
are local, and propose a novel class of local probabilistic NMF quality
functions for soft graph clustering.

Link permanente para citações:

## Approximating Matrices with Multiple Symmetries

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Relevância na Pesquisa

26.24%

If a tensor with various symmetries is properly unfolded, then the resulting
matrix inherits those symmetries. As tensor computations become increasingly
important it is imperative that we develop efficient structure preserving
methods for matrices with multiple symmetries. In this paper we consider how to
exploit and preserve structure in the pivoted Cholesky factorization when
approximating a matrix $A$ that is both symmetric ($A=A^T$) and what we call
{\em perfect shuffle symmetric}, or {\em perf-symmetric}. The latter property
means that $A = \Pi A\Pi$ where $\Pi$ is a permutation with the property that
$\Pi v = v$ if $v$ is the vec of a symmetric matrix and $\Pi v = -v$ if $v$ is
the vec of a skew-symmetric matrix. Matrices with this structure can arise when
an order-4 tensor $\cal A$ is unfolded and its elements satisfy ${\cal
A}(i_{1},i_{2},i_{3},i_{4}) = {\cal A}(i_{2},i_{1},i_{3},i_{4}) ={\cal
A}(i_{1},i_{2},i_{4},i_{3}) ={\cal A}(i_{3},i_{4},i_{1},i_{2}).$ This is the
case in certain quantum chemistry applications where the tensor entries are
electronic repulsion integrals. Our technique involves a closed-form block
diagonalization followed by one or two half-sized pivoted Cholesky
factorizations. This framework allows for a lazy evaluation feature that is
important if the entries in $\cal A$ are expensive to compute. In addition to
being a structure preserving rank reduction technique...

Link permanente para citações:

## MahNMF: Manhattan Non-negative Matrix Factorization

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 14/07/2012

Relevância na Pesquisa

46.09%

#Statistics - Machine Learning#Computer Science - Learning#Computer Science - Numerical Analysis#65K10#I.2.4#I.2.10#I.4.6#I.4.8#I.5.3#I.5.4#G.1.6

Non-negative matrix factorization (NMF) approximates a non-negative matrix
$X$ by a product of two non-negative low-rank factor matrices $W$ and $H$. NMF
and its extensions minimize either the Kullback-Leibler divergence or the
Euclidean distance between $X$ and $W^T H$ to model the Poisson noise or the
Gaussian noise. In practice, when the noise distribution is heavy tailed, they
cannot perform well. This paper presents Manhattan NMF (MahNMF) which minimizes
the Manhattan distance between $X$ and $W^T H$ for modeling the heavy tailed
Laplacian noise. Similar to sparse and low-rank matrix decompositions, MahNMF
robustly estimates the low-rank part and the sparse part of a non-negative
matrix and thus performs effectively when data are contaminated by outliers. We
extend MahNMF for various practical applications by developing box-constrained
MahNMF, manifold regularized MahNMF, group sparse MahNMF, elastic net inducing
MahNMF, and symmetric MahNMF. The major contribution of this paper lies in two
fast optimization algorithms for MahNMF and its extensions: the rank-one
residual iteration (RRI) method and Nesterov's smoothing method. In particular,
by approximating the residual matrix by the outer product of one row of W and
one row of $H$ in MahNMF...

Link permanente para citações:

## Non-negative matrix factorization for semi-supervised data clustering

Fonte: Springer
Publicador: Springer

Tipo: Artigo de Revista Científica

EN_US

Relevância na Pesquisa

66.13%

Traditional clustering algorithms are inapplicable to many real-world problems where limited knowledge from domain experts is available. Incorporating the do-
main knowledge can guide a clustering algorithm, consequently improving the quality
of clustering. In this paper, we propose SS-NMF: a Semi-Supervised Non-negative Ma-
trix Factorization framework for data clustering. In SS-NMF, users are able to provide
supervision for clustering in terms of pairwise constraints on a few data objects spec-
ifying whether they \must" or \cannot" be clustered together. Through an iterative
algorithm, we perform symmetric tri-factorization of the data similarity matrix to in-
fer the clusters. Theoretically, we show the correctness and convergence of SS-NMF.
Moveover, we show that SS-NMF provides a general framework for semi-supervised
clustering. Existing approaches can be considered as special cases of it. Through extensive experiments conducted on publicly available datasets, we demonstrate the superior
performance of SS-NMF for clustering.; The original
publication is available at www.springerlink.com.

Link permanente para citações:

## Symmetries That Latin Squares Inherit from 1-Factorizations

Fonte: John Wiley & Sons Inc
Publicador: John Wiley & Sons Inc

Tipo: Artigo de Revista Científica

Relevância na Pesquisa

26.27%

#Keywords: 1-factorization#Atomic latin square#Autotopy, paratopy#Idempotent#Latin square#Main class#Perfect 1-factorization#Totally symmetric

A 1-factorization of a graph is a decomposition of the graph into edge disjoint perfect matchings. There is a well-known method, which we call the double struck K sign-construction, for building a 1-factorization of Kn,n from a 1-factorization of Kn+1. The 1-factorization of Kn,n can be written as a latin square of order n. The double struck K sign-construction has been used, among other things, to make perfect 1-factorizations, subsquare-free latin squares, and atomic latin squares. This paper studies the relationship between the factorizations involved in the K-construction. In particular, we show how symmetries (automorphisms) of the starting factorization are inherited as symmetries by the end product, either as automorphisms of the factorization or as autotopies of the latin square. Suppose that the double struck K sign-construction produces a latin square L from a 1-factorization F of Kn+1. We show that the main class of L determines the isomorphism class of F, although the converse is false. We also prove a number of restrictions on the symmetries (autotopies and paratopies) which L may possess, many of which are simple consequences of the fact that L must be symmetric (in the usual matrix sense) and idempotent. In some circumstances...

Link permanente para citações: