![]() |
Vcsn
2.3a
Be Rational
|
#include <reduce.hh>
Public Types | |
using | z_weight_t = vcsn::detail::z_impl::value_t |
Specializations for Q and R. More... | |
using | q_weight_t = vcsn::detail::q_impl::value_t |
using | r_weight_t = vcsn::detail::r_impl::value_t |
Public Member Functions | |
left_reductioner (const automaton_t &input) | |
void | linear_representation () |
Create the linear representation of the input. More... | |
void | product_vector_matrix (const vector_t &v, const matrix_t &m, vector_t &res) |
Computes the product of a row vector with a matrix. More... | |
weight_t | scalar_product (const vector_t &v, const vector_t &w) |
Computes the scalar product of two vectors. More... | |
unsigned | find_pivot_by_norm (const vector_t &v, unsigned begin, unsigned *permutation) |
void | z_reduce_vector (vector_t &vbasis, vector_t ¤t, unsigned nb, unsigned *permutation) |
void | z_vector_in_new_basis (std::vector< vector_t > &basis, vector_t ¤t, vector_t &new_vector, unsigned *permutation) |
unsigned | find_pivot (const vector_t &v, unsigned begin, unsigned *permutation) |
Return the first (w.r.t the column permutation) non zero element as pivot. More... | |
weight_t | reduce_vector (vector_t &vbasis, vector_t ¤t, unsigned b, unsigned *permutation) |
Reduce a vector w.r.t. More... | |
void | normalisation_vector (vector_t &v, unsigned pivot, unsigned *permutation) |
Normalize the basis vector such that its pivot is equal to 1. More... | |
void | bottom_up_reduction (std::vector< vector_t > &basis, unsigned *permutation) |
Apply reduction to vectors of the basis to maximize the number of zeros. More... | |
void | vector_in_new_basis (std::vector< vector_t > &basis, vector_t ¤t, vector_t &new_vector, unsigned *permutation) |
Compute the coordinate of a vector in the new basis. More... | |
output_automaton_t | operator() () |
Core algorithm This algorithm computes a basis of I.mu(w). More... | |
Static Public Member Functions | |
static weight_t | norm (const q_weight_t &w) |
static weight_t | norm (const r_weight_t &w) |
Norm for real numbers; a "stable" pivot should minimize this norm. More... | |
static weight_t | norm (const z_weight_t &w) |
Norm for integers. More... | |
static z_weight_t | gcd (z_weight_t x, z_weight_t y, z_weight_t &a, z_weight_t &b) |
Private Types | |
using | automaton_t = Aut |
using | context_t = context_t_of< automaton_t > |
using | weightset_t = typename context_t::weightset_t |
using | output_automaton_t = fresh_automaton_t_of< automaton_t > |
using | label_t = label_t_of< automaton_t > |
using | state_t = state_t_of< automaton_t > |
using | output_state_t = state_t_of< output_automaton_t > |
using | weight_t = typename context_t::weight_t |
using | vector_t = std::vector< weight_t > |
using | matrix_t = std::vector< std::map< std::size_t, weight_t > > |
using | matrix_set_t = std::map< label_t, matrix_t > |
Private Attributes | |
automaton_t | input_ |
const weightset_t_of< automaton_t > | ws_ = *input_->weightset() |
output_automaton_t | res_ |
unsigned | dimension |
vector_t | init |
vector_t | final |
matrix_set_t | letter_matrix_set |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
using vcsn::detail::left_reductioner< Aut >::q_weight_t = vcsn::detail::q_impl::value_t |
using vcsn::detail::left_reductioner< Aut >::r_weight_t = vcsn::detail::r_impl::value_t |
|
private |
|
private |
|
private |
|
private |
using vcsn::detail::left_reductioner< Aut >::z_weight_t = vcsn::detail::z_impl::value_t |
|
inline |
|
inline |
Apply reduction to vectors of the basis to maximize the number of zeros.
Definition at line 462 of file reduce.hh.
References vcsn::detail::left_reductioner< Aut >::reduce_vector().
|
inline |
Return the first (w.r.t the column permutation) non zero element as pivot.
Definition at line 413 of file reduce.hh.
References vcsn::detail::left_reductioner< Aut >::dimension, and vcsn::detail::left_reductioner< Aut >::ws_.
|
inline |
Definition at line 301 of file reduce.hh.
References vcsn::detail::left_reductioner< Aut >::dimension, vcsn::min, vcsn::detail::left_reductioner< Aut >::norm(), and vcsn::detail::left_reductioner< Aut >::ws_.
|
inlinestatic |
Definition at line 325 of file reduce.hh.
References vcsn::res.
Referenced by vcsn::detail::left_reductioner< Aut >::z_reduce_vector().
|
inline |
Create the linear representation of the input.
Definition at line 213 of file reduce.hh.
References vcsn::detail::left_reductioner< Aut >::dimension, vcsn::detail::final_transitions(), vcsn::detail::left_reductioner< Aut >::init, vcsn::detail::initial_transitions(), vcsn::detail::left_reductioner< Aut >::input_, vcsn::detail::left_reductioner< Aut >::letter_matrix_set, and vcsn::detail::transitions().
Referenced by vcsn::detail::left_reductioner< Aut >::operator()().
|
inlinestatic |
Definition at line 282 of file reduce.hh.
References vcsn::detail::q_impl::value_t::den, and vcsn::detail::q_impl::value_t::num.
Referenced by vcsn::detail::left_reductioner< Aut >::find_pivot_by_norm().
|
inlinestatic |
|
inlinestatic |
|
inline |
Normalize the basis vector such that its pivot is equal to 1.
Definition at line 448 of file reduce.hh.
References vcsn::detail::left_reductioner< Aut >::dimension, and vcsn::detail::left_reductioner< Aut >::ws_.
|
inline |
Core algorithm This algorithm computes a basis of I.mu(w).
The basis is scaled.
An automaton where states correspond to the vectors of this basis is built
Definition at line 487 of file reduce.hh.
References vcsn::detail::left_reductioner< Aut >::dimension, vcsn::detail::left_reductioner< Aut >::init, vcsn::detail::left_reductioner< Aut >::letter_matrix_set, vcsn::detail::left_reductioner< Aut >::linear_representation(), vcsn::detail::left_reductioner< Aut >::product_vector_matrix(), vcsn::detail::left_reductioner< Aut >::res_, vcsn::detail::left_reductioner< Aut >::scalar_product(), vcsn::detail::v, and vcsn::detail::left_reductioner< Aut >::ws_.
|
inline |
Computes the product of a row vector with a matrix.
Definition at line 245 of file reduce.hh.
References vcsn::detail::left_reductioner< Aut >::dimension, and vcsn::detail::left_reductioner< Aut >::ws_.
Referenced by vcsn::detail::left_reductioner< Aut >::operator()().
|
inline |
Reduce a vector w.r.t.
a vector of the basis.
When this method is called, in vbasis and current, all the entries that come before (w.r.t the permutation) the pivot are zero. Moreover, vbasis[pivot]=1 This method computes current := current - current[pivot].vbasis
Definition at line 430 of file reduce.hh.
References vcsn::detail::left_reductioner< Aut >::dimension, and vcsn::detail::left_reductioner< Aut >::ws_.
Referenced by vcsn::detail::left_reductioner< Aut >::bottom_up_reduction(), and vcsn::detail::left_reductioner< Aut >::vector_in_new_basis().
|
inline |
Computes the scalar product of two vectors.
Definition at line 258 of file reduce.hh.
References vcsn::detail::left_reductioner< Aut >::dimension, vcsn::res, and vcsn::detail::left_reductioner< Aut >::ws_.
Referenced by vcsn::detail::left_reductioner< Aut >::operator()().
|
inline |
Compute the coordinate of a vector in the new basis.
Definition at line 471 of file reduce.hh.
References vcsn::detail::left_reductioner< Aut >::reduce_vector().
|
inline |
Definition at line 365 of file reduce.hh.
References vcsn::detail::left_reductioner< Aut >::dimension, vcsn::detail::left_reductioner< Aut >::gcd(), and vcsn::detail::left_reductioner< Aut >::ws_.
|
inline |
Definition at line 385 of file reduce.hh.
References vcsn::detail::left_reductioner< Aut >::dimension, and vcsn::detail::left_reductioner< Aut >::ws_.
|
private |
Definition at line 588 of file reduce.hh.
Referenced by vcsn::detail::left_reductioner< Aut >::find_pivot(), vcsn::detail::left_reductioner< Aut >::find_pivot_by_norm(), vcsn::detail::left_reductioner< Aut >::linear_representation(), vcsn::detail::left_reductioner< Aut >::normalisation_vector(), vcsn::detail::left_reductioner< Aut >::operator()(), vcsn::detail::left_reductioner< Aut >::product_vector_matrix(), vcsn::detail::left_reductioner< Aut >::reduce_vector(), vcsn::detail::left_reductioner< Aut >::scalar_product(), vcsn::detail::left_reductioner< Aut >::z_reduce_vector(), and vcsn::detail::left_reductioner< Aut >::z_vector_in_new_basis().
|
private |
|
private |
Definition at line 589 of file reduce.hh.
Referenced by vcsn::detail::left_reductioner< Aut >::linear_representation(), and vcsn::detail::left_reductioner< Aut >::operator()().
|
private |
Definition at line 582 of file reduce.hh.
Referenced by vcsn::detail::left_reductioner< Aut >::linear_representation().
|
private |
Definition at line 591 of file reduce.hh.
Referenced by vcsn::detail::left_reductioner< Aut >::linear_representation(), and vcsn::detail::left_reductioner< Aut >::operator()().
|
private |
Definition at line 585 of file reduce.hh.
Referenced by vcsn::detail::left_reductioner< Aut >::operator()().
|
private |
Definition at line 583 of file reduce.hh.
Referenced by vcsn::detail::left_reductioner< Aut >::find_pivot(), vcsn::detail::left_reductioner< Aut >::find_pivot_by_norm(), vcsn::detail::left_reductioner< Aut >::normalisation_vector(), vcsn::detail::left_reductioner< Aut >::operator()(), vcsn::detail::left_reductioner< Aut >::product_vector_matrix(), vcsn::detail::left_reductioner< Aut >::reduce_vector(), vcsn::detail::left_reductioner< Aut >::scalar_product(), vcsn::detail::left_reductioner< Aut >::z_reduce_vector(), and vcsn::detail::left_reductioner< Aut >::z_vector_in_new_basis().