Skip to content

Vector rational reconstruction #2384

@fredrik-johansson

Description

@fredrik-johansson

There should be functions to reconstruct an _fmpq_vec and fmpq_poly from a modular image, like fmpq_mat_set_fmpz_mat_mod_fmpz.

Note that one can use different strategies. Calling fmpq_reconstruct_fmpz in a loop is good if the coefficients have independent denominators. Trying to track the common denominator as in fmpq_mat_set_fmpz_mat_mod_fmpz is efficient if one has a small common denominator. We could try to figure out (and carefully profile) some heuristic to switch between these strategies.

Another thing worth optimizing is the numerator/denominator bound which by default is taken to be balanced. If we detect small denominators heuristically and allow using most of the bits for the numerator, we can potentially get a 2x speedup for operations like Dixon solving and polynomial interpolation in the common case where the (common) denominator is much smaller than the numerators.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions