Definitividade de formas quadráticas – uma abordagem polinomial
Nenhuma Miniatura disponível
Data
2016-11-18
Autores
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal de Goiás
Resumo
Quadratic forms are algebraic expressions that have important role in different areas of
computer science, mathematics, physics, statistics and others. We deal with rational quadratic
forms and integral quadratic forms, with rational and integer coefficients respectively.
Existing methods for recognition of rational quadratic forms have exponential time
complexity or use approximation that weaken the result reliability. We develop a polinomial
algorithm that improves the best-case of rational quadratic forms recognition in
constant time. In addition, new strategies were used to guarantee the results reliability,
by representing rational numbers as a fraction of integers, and to identify linear combinations
that are linearly independent, using Gauss reduction. About the recognition of
integral quadratic forms, we identified that the existing algorithms have exponential time
complexity for weakly nonnegative type and are polynomial for weakly positive type,
however the degree of the polynomial depends on the algebra dimension and can be very
large. We have introduced a polynomial algorithm for the recognition of weakly nonnegative
quadratic forms. The related algorithm identify hypercritical restrictions testing every
subgraph of 9 vertices of the quadratic form associated graph. By adding Depth First Search
approach, a similar strategy was used in the recognition of weakly positive type. We
have also shown that the recognition of integral quadratic forms can be done by mutations
in the related exchange matrix.
Descrição
Citação
ALVES, J. S. Definitividade de formas quadráticas: uma abordagem polinomial. 2016. 64 f. Tese (Doutorado em Ciência da Computação) - Universidade Federal de Goiás, Goiânia, 2016.