Improve performance of function fields

[kwankyu]

We provide a dedicated reversed Hermite normal form computation implementation for function fields. It seems that we gain 30% in performance.

Performance comparison of ideal arithmetic:

sage: k.<a> = GF(16)
sage: K.<x> = FunctionField(k)
sage: Y = polygen(K, 'Y')
sage: L.<y> = K.extension(Y^4 + Y - x^5)
sage: O = L.maximal_order()
sage: i = O.ideal(y)
sage: j = O.ideal(x, 1/y)
sage: I = (i + j)^10
sage: J = (i / j)^10
sage: timeit('I + J')  # add
sage: timeit('I * J')  # mul
sage: timeit('I / J')  # div
sage: timeit('I^10')   # pow

	add	mul	div	pow
Before	9.56ms	31.8ms	153.0ms	522ms
After	5.37ms	25.1ms	96.3ms	391ms

CC: @slel

Component: performance

Author: Kwankyu Lee

Branch/Commit: 1e24242

Reviewer: Travis Scrimshaw

Issue created by migration from https://trac.sagemath.org/ticket/31841

[kwankyu]

Branch: u/klee/31841

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

671eef1

Improve performance of function field

[sagetrac-git]

Commit: 671eef1

[kwankyu]

Author: Kwankyu Lee

[slel]

comment:7

Don't forget to set to needs review when ready for review.

[tscrim]

comment:8

One quick comment: you did not declare cdef Py_ssize_t ip.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

1e24242

Improve performance of function fields

[sagetrac-git]

Changed commit from 671eef1 to 1e24242

[tscrim]

comment:13

LGTM.

[tscrim]

Reviewer: Travis Scrimshaw

[vbraun]

Changed branch from u/klee/31841 to 1e24242