Coverage for local/lib/python2.7/site-packages/sage/rings/padics/lattice_precision.py : 79%
Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
|
r""" Lattice precision for the parents ``ZpLC``/``QpLC`` and ``ZpLF``/``QpLF``
AUTHOR:
- Xavier Caruso (2018-02): initial version
TESTS::
sage: R = ZpLC(2) doctest:...: FutureWarning: This class/method/function is marked as experimental. It, its functionality or its interface might change without a formal deprecation. See http://trac.sagemath.org/23505 for details. sage: prec = R.precision() sage: prec Precision lattice on 0 objects
sage: S = ZpLF(2) sage: prec = S.precision() sage: prec Precision module on 0 objects """
# **************************************************************************** # Copyright (C) 2018 Xavier Caruso <xavier.caruso@normalesup.org> # # This program is free software: you can redistribute it and/or modify # it under the terms of the GNU General Public License as published by # the Free Software Foundation, either version 2 of the License, or # (at your option) any later version. # http://www.gnu.org/licenses/ # ****************************************************************************
from sage.misc.misc import walltime
from sage.structure.sage_object import SageObject from sage.structure.unique_representation import UniqueRepresentation from sage.misc.abstract_method import abstract_method from sage.misc.cachefunc import cached_method
from sage.rings.integer_ring import ZZ from sage.rings.rational_field import QQ from sage.rings.infinity import Infinity
from sage.rings.padics.precision_error import PrecisionError
# The default minimal size after which re-echelonization is not performed, # i.e., when a variable is not referenced anymore and could be deleted but its # corresponding column is further than this threshold from the right end of the # matrix representing the precision lattice, then the column is not removed # from the matrix because the re-echelonization would be too costly. DEFAULT_THRESHOLD_DELETION = 50
# The number of additional digits used for internal computations STARTING_ADDITIONAL_PREC = 5
class pRational: r""" This class implements rational numbers viewed as elements of ``Qp``. In particular, it provides additional methods which are specific to ``p``-adics (as ``p``-adic valuation).
Only for internal use.
INPUT:
- ``p`` -- a prime number
- ``x`` -- a rational number
- ``exponent`` -- an integer (default: 0)
- ``valuation`` -- an integer or None (default: ``None``), the ``p``-adic valuation of this element
If not ``None``, this method trusts the given value to the attribute ``valuation``.
TESTS::
sage: from sage.rings.padics.lattice_precision import pRational sage: x = pRational(2, 5); x 5 sage: y = pRational(2, 5/3, 2); y 2^2 * 5/3
sage: x + y 35/3 sage: x - y -5/3 sage: x * y 2^2 * 25/3 sage: x / y 2^-2 * 3
sage: x.valuation() 0 sage: y.valuation() 2
sage: z = pRational(2, 1024, valuation=4) sage: z 1024 sage: z.valuation() 4 """ def __init__(self, p, x, exponent=0, valuation=None): r""" Construct the element ``x * p^exponent``
TESTS::
sage: from sage.rings.padics.lattice_precision import pRational sage: pRational(2, 5) 5 sage: pRational(2, 5/3, 2) 2^2 * 5/3 """ else:
def __repr__(self): r""" Return a string representation of this element.
TESTS::
sage: from sage.rings.padics.lattice_precision import pRational sage: pRational(2, 5, 2) # indirect doctest 2^2 * 5 """ else:
def reduce(self, prec): r""" Return this element reduced modulo ``p^prec``.
INPUT:
- ``prec`` -- an integer
TESTS::
sage: from sage.rings.padics.lattice_precision import pRational sage: x = pRational(2, 1234567); x 1234567 sage: x.reduce(12) 1671
sage: x = pRational(2, 1234/567); x 1234/567 sage: x.reduce(12) 190 """ else: # probably we should use Newton iteration instead # (but it is actually slower for now - Python implementation) else: x = 0 else:
def reduce_relative(self, prec): r""" Return this element reduced modulo ``p^n`` where ``n = prec + val(x)``.
INPUT:
- ``prec`` -- a nonnegative integer
TESTS::
sage: from sage.rings.padics.lattice_precision import pRational sage: x = pRational(2, 1234567); x 1234567 sage: x.reduce_relative(12) 1671
sage: x = pRational(2, 1234/567); x 1234/567 sage: x.reduce_relative(12) 190 """
def normalize(self): r""" Normalize this element, i.e. write it as ``p^v * u`` where ``u`` is coprime to `p`.
TESTS::
sage: from sage.rings.padics.lattice_precision import pRational sage: x = pRational(2, 123456, 7); x 2^7 * 123456 sage: x.normalize(); x 2^13 * 1929 """ else:
def valuation(self): r""" Return the `p`-adic valuation of this element.
TESTS::
sage: from sage.rings.padics.lattice_precision import pRational sage: x = pRational(2, 123456, 7); x 2^7 * 123456 sage: x.valuation() 13 """
def is_p_power(self): r""" Return true if this element is a power of `p`.
TESTS::
sage: from sage.rings.padics.lattice_precision import pRational sage: x = pRational(2, 1024, 2); x 2^2 * 1024 sage: x.is_p_power() True
sage: y = pRational(2, 123456, 7); y 2^7 * 123456 sage: y.is_p_power() False """
def is_zero(self): r""" Return true if this element vanishes.
TESTS::
sage: from sage.rings.padics.lattice_precision import pRational sage: x = pRational(2, 123456, 7); x 2^7 * 123456 sage: x.is_zero() False
sage: (x-x).is_zero() True """
def __add__(self, other): r""" Return the sum of ``self`` and ``other``.
TESTS::
sage: from sage.rings.padics.lattice_precision import pRational sage: x = pRational(2, 123456, 7); x 2^7 * 123456 sage: y = pRational(2, 891011, 12); y 2^12 * 891011 sage: x + y 2^7 * 28635808 """ else: else:
def __sub__(self, other): r""" Return the subtraction of ``self`` by ``other``.
TESTS::
sage: from sage.rings.padics.lattice_precision import pRational sage: x = pRational(2, 123456, 7); x 2^7 * 123456 sage: y = pRational(2, 891011, 12); y 2^12 * 891011 sage: x - y 2^7 * -28388896 """
def __neg__(self): r""" Return the opposite of this element.
TESTS::
sage: from sage.rings.padics.lattice_precision import pRational sage: x = pRational(2, 123456, 7); x 2^7 * 123456 sage: -x 2^7 * -123456 """
def __mul__(self, other): r""" Return the product of ``self`` and ``other``.
TESTS::
sage: from sage.rings.padics.lattice_precision import pRational sage: x = pRational(2, 123456, 7); x 2^7 * 123456 sage: y = pRational(2, 891011, 12); y 2^12 * 891011 sage: x * y 2^19 * 110000654016 """ else:
def __div__(self, other): r""" Return the quotient of ``self`` by ``other``.
TESTS::
sage: from sage.rings.padics.lattice_precision import pRational sage: x = pRational(2, 123456, 7); x 2^7 * 123456 sage: y = pRational(2, 891011, 12); y 2^12 * 891011 sage: x / y 2^-5 * 123456/891011 """ else:
def __lshift__(self, n): r""" Return the product of this element by ``p^n``.
INPUT:
- ``n`` -- a relative integer
TESTS::
sage: from sage.rings.padics.lattice_precision import pRational sage: x = pRational(2, 123456, 7); x 2^7 * 123456 sage: x << 10 2^17 * 123456 """ else:
def __rshift__(self, n): r""" Return the quotient of this element by ``p^n``.
INPUT:
- ``n`` -- a relative integer
TESTS::
sage: from sage.rings.padics.lattice_precision import pRational sage: x = pRational(2, 123456, 7); x 2^7 * 123456 sage: x >> 10 2^-3 * 123456 """
def unit_part(self): r""" Return the unit part of this element, that is the part ``u`` in the writing ``u * p^v`` with ``u`` coprime to `p`.
TESTS::
sage: from sage.rings.padics.lattice_precision import pRational sage: x = pRational(2, 123456, 7); x 2^7 * 123456 sage: x.unit_part() 1929 """ raise ValueError("the unit part of zero is not defined")
def xgcd(self, other): r""" Return the gcd of ``self`` and ``other`` together with two element ``u`` and ``v`` such that ``u*self + v*other = gcd``.
The ``gcd`` is normalized so that it is a power of `p`.
TESTS::
sage: from sage.rings.padics.lattice_precision import pRational sage: x = pRational(2, 123456, 7); x 2^7 * 123456 sage: y = pRational(2, 891011, 12); y 2^12 * 891011
sage: d, u, v = x.xgcd(y) sage: d 2^7 * 32 sage: d.normalize(); d 2^12 * 1
sage: u*x + v*y 2^7 * 32 """ else: else:
def value(self): r""" Return this element as a rational number.
TESTS::
sage: from sage.rings.padics.lattice_precision import pRational sage: x = pRational(2, 123456, 7); x 2^7 * 123456 sage: x.value() 15802368 """
def list(self, prec): r""" Return the list of the digits of this element (written in radix `p`) up to position ``prec``.
The first zeros are omitted.
TESTS::
sage: from sage.rings.padics.lattice_precision import pRational sage: x = pRational(2, 123456); x 123456 sage: x.list(5) [] sage: x.list(20) [1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0]
sage: y = pRational(2, 123/456); y 41/152 sage: y.list(10) [1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1]
sage: z = pRational(2, 0) sage: z.list(10) [] sage: z.list(100) [] """
class DifferentialPrecisionGeneric(SageObject): r""" A generic class for precision objects obtained by automatic differentiation.
INPUT:
- ``p`` -- a prime number
- ``label`` -- a string, the label of the parents to which the elements belong that are tracked by this precision module
.. NOTE::
This object is used internally by the parent ring. You should not create instances of this class on your own.
EXAMPLES::
sage: R = ZpLC(2, label='init') sage: R.precision() Precision lattice on 0 objects (label: init) """ def __init__(self, p, label): r""" TESTS::
sage: prec = ZpLC(2, label='init').precision() sage: from sage.rings.padics.lattice_precision import DifferentialPrecisionGeneric sage: isinstance(prec, DifferentialPrecisionGeneric) True
""" # and values corresponding columns in the matrix # representing the precision lattice
def __reduce__(self): r""" TESTS::
sage: R = ZpLF(2) sage: prec = R.precision() sage: dumps(prec) Traceback (most recent call last): ... NotImplementedError: pickling/unpickling precision modules is not implemented yet """ raise NotImplementedError("pickling/unpickling precision modules is not implemented yet")
def _repr_(self): r""" Return a string representation of this precision object.
EXAMPLES::
sage: R = ZpLC(2) sage: R.precision() Precision lattice on ... objects
If a label has been specified, it is included in the representation::
sage: R = ZpLC(2, label="mylabel") sage: R.precision() Precision lattice on 0 objects (label: mylabel) """
def threshold_deletion(self, threshold=None): r""" Return (and set) the threshold for column deletion.
When a variable dies, i.e., goes out of scope, the ambient space in which the precision module lives can be reduced (by projection onto the hyperplane defined by the dead variable). This reduction has a cost because it leads to re-echelonization of a part of the matrix that encodes the precision. The size of this part is roughly measured by the number of columns between the last column and the one corresponding to the dead variable.
This threshold returned by this method is the maximal distance until which a column of a dead variable is removed and the matrix re-echelonized. Beyond the threshold, the column of the dead variable is kept in this matrix as if the variable were not destroyed.
INPUT:
- ``threshold`` -- a non-negative integer, ``Infinity`` or ``None`` (default: ``None``): if not ``None`` set the threshold to the given value.
.. NOTE::
Setting the threshold to ``0`` disables the dimension reduction.
Setting the threshold to ``Infinity`` forces the dimension reduction after each deletion.
EXAMPLES::
sage: R = ZpLC(2, label='threshold_deletion') sage: prec = R.precision() sage: prec.threshold_deletion() 50
sage: prec.threshold_deletion(20) 20 sage: prec.threshold_deletion() 20
sage: prec.threshold_deletion(-2) Traceback (most recent call last): ... ValueError: The threshold must be a nonnegative integer or Infinity """ else:
def prime(self): r""" Return the underlying prime number attached to this precision lattice.
EXAMPLES::
sage: R = ZpLC(2, label="mylabel") sage: R.precision().prime() 2 """
def _index(self, ref): r""" Return the index of the column in the precision matrix that corresponds to ``ref``.
Only for internal use.
TESTS::
sage: from sage.rings.padics.lattice_precision import pAdicLatticeElementWeakProxy sage: R = ZpLC(2, label="index") sage: prec = R.precision() sage: x = R(1, 10) sage: y = R(1, 5)
sage: prec._index(pAdicLatticeElementWeakProxy(x)) 0 sage: prec._index(pAdicLatticeElementWeakProxy(y)) 1
sage: del x sage: prec.del_elements() sage: prec._index(pAdicLatticeElementWeakProxy(y)) 0 """
def ambient_dimension(self): r""" Return the dimension of the vector space in which the precision module/lattice lives.
EXAMPLES:
sage: R = ZpLC(2, label='ambient_dim') sage: prec = R.precision()
sage: x, y = R(1, 10), R(1, 5) sage: prec.ambient_dimension() 2 sage: prec.dimension() 2
sage: u = x + y sage: prec.ambient_dimension() 3 sage: prec.dimension() 3
In the case of ``ZpLC`` (lattice-cap precision), it is always equal to the dimension of the lattice.
In the case of ``ZpLF`` (lattice-float precision), the precision object is not necessarily a lattice and then may have smaller dimension::
sage: R = ZpLF(2, label='ambient_dim') sage: prec = R.precision()
sage: x, y = R(1, 10), R(1, 5) sage: prec.ambient_dimension() 2 sage: prec.dimension() 2
sage: u = x + y sage: prec.ambient_dimension() 3 sage: prec.dimension() 2 """
@abstract_method def dimension(self): r""" Return the dimension of this precision module.
EXAMPLES::
sage: R = ZpLC(5, label='dim') sage: prec = R.precision() sage: prec.dimension() 0
sage: x = R(1, 10) sage: prec.dimension() 1 """ pass
@abstract_method def _new_element(self, *args, **kwargs): r""" Insert a new element in this precision module.
TESTS::
sage: R = ZpLC(2) sage: x = R.random_element() sage: y = R.random_element() sage: z = x*y # indirect doctest """ pass
def _record_collected_element(self, ref): r""" Record that the element with weak reference ``ref`` has been collected by the garbage collector.
INPUT:
- ``ref`` -- the weak reference of the collected element
TESTS::
sage: R = ZpLC(2, label='gc') sage: prec = R.precision()
sage: x = R.random_element() sage: prec._collected_references []
sage: del x sage: prec._collected_references [WeakProxy#...] """
@abstract_method def del_elements(self, threshold=None): r""" Delete (or mark for future deletion) the columns of precision matrix corresponding to elements that were collected by the garbage collector.
INPUT:
- ``threshold`` -- an integer or ``None`` (default: ``None``): a column whose distance to the right is greater than the threshold is not erased but marked for deletion; if ``None``, always erase (never mark for deletion).
EXAMPLES::
sage: R = ZpLC(2, label='del_elements') sage: prec = R.precision()
sage: x = R(1, 10) sage: prec Precision lattice on 1 object (label: del_elements) sage: prec.precision_lattice() [1024]
sage: del x sage: prec Precision lattice on 1 object (label: del_elements) sage: prec.precision_lattice() [1024]
sage: prec.del_elements() sage: prec Precision lattice on 0 objects (label: del_elements) sage: prec.precision_lattice() [] """ pass
@abstract_method def _precision_absolute(self, x): r""" Return the absolute precision of the given element.
INPUT:
- ``x`` -- the element whose absolute precision is requested
.. NOTE::
The absolute precision is obtained by projecting the precision lattice onto the line of coordinate ``dx``.
This function is not meant to be called directly. Call ``x.precision_absolute()`` instead.
EXAMPLES::
sage: R = ZpLC(2) sage: x = R(1, 10); x 1 + O(2^10) sage: y = R(1, 5); y 1 + O(2^5) sage: z = x + y; z 2 + O(2^5) sage: z.precision_absolute() # indirect doctest 5 """ pass
@abstract_method def precision_lattice(self, elements=None): r""" Return a lattice modeling the precision on the given set of elements or, if not given, on the whole set of elements tracked by the precision module.
INPUT:
- ``elements`` -- a list of elements or ``None`` (default: ``None``)
EXAMPLES::
sage: R = ZpLC(2, label='precision_lattice') sage: prec = R.precision() sage: x = R(1, 10); y = R(1, 5) sage: u = x + y sage: v = x - y sage: prec.precision_lattice() [ 1024 0 1024 1024] [ 0 32 32 1099511627744] [ 0 0 2097152 0] [ 0 0 0 1099511627776] sage: prec.precision_lattice([u, v]) [ 32 2016] [ 0 2048]
If the precision module does not project to a lattice, an error is raised.
sage: R = ZpLF(2, label='precision_lattice') sage: prec = R.precision() sage: x = R(1, 10); y = R(1, 5) sage: u = x + y sage: v = x - y sage: prec.precision_lattice([x,y,u,v]) Traceback (most recent call last): ... PrecisionError: the differential is not surjective """ pass
def diffused_digits(self, elements=None): r""" Return the number of diffused digits of precision within a subset of elements.
A diffused digit of precision is a known digit which is not located on a single variable but only appears on a suitable linear combination of variables.
The number of diffused digits of precision quantifies the quality of the approximation of the lattice precision by a jagged precision (that is a precision which is split over all variables).
We refer to [CRV2018]_ for a detail exposition of the notion of diffused digits.
EXAMPLES::
sage: R = ZpLC(2) sage: prec = R.precision() sage: x = R(1, 10); y = R(1, 5) sage: u = x + y sage: v = x - y
sage: prec.diffused_digits([x, y]) 0 sage: prec.diffused_digits([u, v]) 6
The elements `u` and `v` are known at absolute precision `O(2^5)`. However, the sum `u + v = 2x` is known at precision `O(2^11)`, that is with `6` more digits. That is where the `6` diffused digits of precision comes from.
Here is another example with matrices::
sage: M = matrix(R, 2, 2, [R(3, 5), R(7, 5), R(1, 5), R(11, 1)]) sage: N = M^10
The next syntax provides as easy way to select an interesting subset of variables (the selected subset consists of the four entries of the matrix ``N``)::
sage: prec.diffused_digits(N) 17
Note that, in some cases, the number of diffused digits can be infinite::
sage: R = ZpLF(2) sage: prec = R.precision() sage: x = R(1, 10) sage: y = x sage: prec.diffused_digits([x, y]) +Infinity """
def tracked_elements(self, values=True, dead=True): r""" Return the list of tracked elements.
INPUT:
- ``values`` -- a boolean (default: ``True``); if false, the method returns a list of weak references on tracked elements instead
- ``dead`` -- a boolean (default: ``True``); whether dead elements for which the corresponding column is still not erased should be listed or not
EXAMPLES::
sage: R = ZpLC(2, label='tracked') sage: prec = R.precision() sage: x = R(1, 10); y = R(1, 5) sage: prec.tracked_elements() [1 + O(2^10), 1 + O(2^5)] sage: prec.tracked_elements(values=False) [WeakProxy#..., WeakProxy#..., WeakProxy#...] sage: prec.tracked_elements(values=False, dead=False) [WeakProxy#..., WeakProxy#...]
sage: u = x + y sage: v = x - y sage: prec.tracked_elements() [1 + O(2^10), 1 + O(2^5), 2 + O(2^5), O(2^5)] sage: prec.tracked_elements(values=False) [WeakProxy#..., WeakProxy#..., WeakProxy#..., WeakProxy#..., WeakProxy#...]
sage: del x; del y sage: prec.tracked_elements() [None, None, 2 + O(2^5), O(2^5), None] sage: prec.tracked_elements(values=False) [WeakProxy#..., WeakProxy#..., WeakProxy#...] """
# History
def history_enable(self): r""" Enable history.
We refer to the documentation of the method :meth:`history` for a complete documentation (including examples) about history.
TESTS::
sage: R = ZpLC(2, label='history_en') sage: prec = R.precision()
sage: print(prec.history()) # history is disabled by default Traceback (most recent call last): ... ValueError: History is not tracked
sage: prec.history_enable() sage: print(prec.history()) Timings ---
.. SEEALSO::
:meth:`history`, :meth:`history_disable`, :meth:`history_clear` """
def history_disable(self): r""" Disable history.
We refer to the documentation of the method :meth:`history` for a complete documentation (including examples) about history.
TESTS::
sage: R = ZpLC(2, label='history_dis') sage: prec = R.precision()
sage: print(prec.history()) # history is disabled by default Traceback (most recent call last): ... ValueError: History is not tracked
sage: prec.history_enable() sage: print(prec.history()) Timings ---
sage: prec.history_disable() sage: print(prec.history()) Traceback (most recent call last): ... ValueError: History is not tracked
.. SEEALSO::
:meth:`history`, :meth:`history_enable`, :meth:`history_clear` """
def history_clear(self): r""" Clear history.
We refer to the documentation of the method :meth:`history` for a complete documentation (including examples) about history.
TESTS::
sage: R = ZpLC(2, label='history_clear') sage: prec = R.precision() sage: prec.history_enable()
sage: x = R(1, 10); y = R(1, 5) sage: x, y = x+y, x-y sage: print(prec.history()) # somewhat random Timings 0.000213s oooo
When we clear history, only the last line is kept::
sage: prec.history_clear() sage: print(prec.history()) Timings oooo --- oooo
sage: prec.del_elements()
sage: print(prec.history()) # somewhat random Timings oooo 0.000005s ~~oo 0.000285s oo
.. SEEALSO::
:meth:`history`, :meth:`history_enable`, :meth:`history_disable` """ raise ValueError("History is not tracked")
def _format_history(self, time, status, timings): r""" Return a formatted output for the history.
This is a helper function for the method :meth:`history`.
TESTS::
sage: R = ZpLC(2, label='history_en') sage: prec = R.precision() sage: prec._format_history(1.23456789, ['o', 'o', 'o', 'o', 'o', 'o', '~', 'o', 'o'], true) '1.234568s oooooo~oo' sage: prec._format_history(1.23456789, ['o', 'o', 'o', 'o', 'o', 'o', '~', 'o', 'o'], false) 'oooooo~oo'
sage: prec._format_history(12.3456789, ['o', 'o', 'o', 'o', 'o', 'o', '~', 'o', 'o'], true) ' >= 10s oooooo~oo' sage: prec._format_history(10^(-10), ['o', 'o', 'o', 'o', 'o', 'o', '~', 'o', 'o'], true) ' --- oooooo~oo' sage: prec._format_history(-1, ['o', 'o', 'o', 'o', 'o', 'o', '~', 'o', 'o'], true) ' Timings oooooo~oo' """ else: else:
def history(self, compact=True, separate_reduce=False, timings=True, output_type='asciiart'): r""" Show history.
The history records creations and deletions of elements attached to this precision lattice, together with many timings.
INPUT:
- ``compact`` -- a boolean (default: ``True``); if true, all consecutive operations of the same type appear on a single row
- ``separate_reduce`` -- a boolean (default: ``False``); specify whether partial/full Hermite reduction should be displayed separatedly
- ``timings`` -- a boolean (default: ``True``); specify whether timings should be displayed
- ``output_type`` -- only ``asciiart`` is implemented for now.
IMPORTANT NOTE:
History is disabled by default. It should then be enabled (through a call to the method :meth:`history_enable`) before use.
EXAMPLES::
sage: R = ZpLC(2, label='history_en') sage: prec = R.precision()
We first enable history::
sage: prec.history_enable()
At the beginning, the history is of course empty::
sage: print(prec.history()) Timings ---
Now we start creating and deleting elements::
sage: L = [ R.random_element() for _ in range(20) ] sage: for p in range(20): ....: if is_prime(p): L[p] = None sage: prec.del_elements()
sage: print(prec.history()) # somewhat random Timings 0.001108s oooooooooooooooooooo 0.000009s oo~~o~o~ooo~o~ooo~o~ 0.014250s oooooooooooo
The legend is the following:: - the symbol ``o`` represents a tracked element, - the symbol ``~`` represents an element which is marked for deletion.
On the history, we see: - 1st line: twenty new elements were created (this corresponds to the affectation of the list ``L``); - 2nd line: elements at prime positions were marked for deletion (this corresponds to the ``for`` loop); - 3rd line: the above elements are indeed deleted (this corresponds to the call of the method :meth:`del_elements`.
Here are some variants::
sage: print(prec.history(timings=False)) oooooooooooooooooooo oo~~o~o~ooo~o~ooo~o~ oooooooooooo
sage: print(prec.history(separate_reduce=True)) # somewhat random Timings 0.001063s oooooooooooooooooooo 0.000014s oo~~o~o~ooo~o~ooo~o~ 0.000798s oo~~o~o~ooo~ooooo 0.000233s oo~~o~o~ooo~orrrr 0.000824s oo~~o~o~oooooooo 0.000375s oo~~o~o~ooorrrrr 0.001724s oo~~o~ooooooooo 0.001020s oo~~o~orrrrrrrr 0.001989s oo~~oooooooooo 0.001303s oo~~orrrrrrrrr 0.002352s oo~oooooooooo 0.001632s oo~rrrrrrrrrr 0.002265s oooooooooooo 0.001630s oorrrrrrrrrr --- oooooooooooo
The symbol ``r`` represents a column of the precision matrix which is currently under partial Hermite reduction.
Timings for automatic reduction do not appear because they are included in the timings for deletion.
The symbol ``R`` is used to symbolize a column which is under full Hermite reduction. Note that full Hermite reduction are never performed automatically but needs to be called by hand::
sage: prec.reduce() sage: print(prec.history(separate_reduce=True)) # somewhat random Timings 0.001063s oooooooooooooooooooo 0.000014s oo~~o~o~ooo~o~ooo~o~ 0.000798s oo~~o~o~ooo~ooooo 0.000233s oo~~o~o~ooo~orrrr 0.000824s oo~~o~o~oooooooo 0.000375s oo~~o~o~ooorrrrr 0.001724s oo~~o~ooooooooo 0.001020s oo~~o~orrrrrrrr 0.001989s oo~~oooooooooo 0.001303s oo~~orrrrrrrrr 0.002352s oo~oooooooooo 0.001632s oo~rrrrrrrrrr 0.002265s oooooooooooo 0.001630s oorrrrrrrrrr 0.001486s RRRRRRRRRRRR --- oooooooooooo
Here is a more common example with matrices::
sage: R = ZpLC(3) sage: prec = R.precision() sage: prec.history_enable() sage: M = random_matrix(R, 5) sage: d = M.determinant() sage: print(prec.history()) # somewhat random --- 0.004212s oooooooooooooooooooooooooooooooooooo 0.000003s oooooooooooooooooooooooooooooooooo~~ 0.000010s oooooooooooooooooooooooooooooooooo 0.001560s ooooooooooooooooooooooooooooooooooooooooo 0.000004s ooooooooooooooooooooooooooooo~oooo~oooo~o 0.002168s oooooooooooooooooooooooooooooooooooooo 0.001787s ooooooooooooooooooooooooooooooooooooooooo 0.000004s oooooooooooooooooooooooooooooooooooooo~~o 0.000198s ooooooooooooooooooooooooooooooooooooooo 0.001152s ooooooooooooooooooooooooooooooooooooooooo 0.000005s ooooooooooooooooooooooooooooooooo~oooo~~o 0.000853s oooooooooooooooooooooooooooooooooooooo 0.000610s ooooooooooooooooooooooooooooooooooooooo [...] 0.003879s ooooooooooooooooooooooooooooooooooooooooooooooooooooooooo 0.000006s oooooooooooooooooooooooooooooooooooooooooooooooooooo~~~~~ 0.000036s oooooooooooooooooooooooooooooooooooooooooooooooooooo 0.006737s oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo 0.000005s oooooooooooooooooooooooooooooooooooooooooooooooooooo~~~~~ooooo 0.002637s ooooooooooooooooooooooooooooooooooooooooooooooooooooooooo 0.007118s ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo 0.000008s oooooooooooooooooooooooooooooooooooooooooooooooooooo~~~~o~~~~oooo 0.003504s ooooooooooooooooooooooooooooooooooooooooooooooooooooooooo 0.005371s ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo 0.000006s ooooooooooooooooooooooooooooooooooooooooooooooooooooo~~~o~~~ooo 0.001858s ooooooooooooooooooooooooooooooooooooooooooooooooooooooooo 0.003584s ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo 0.000004s oooooooooooooooooooooooooooooooooooooooooooooooooooooo~~o~~oo 0.000801s ooooooooooooooooooooooooooooooooooooooooooooooooooooooooo 0.001916s ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo 0.000022s ooooooooooooooooooooooooooooo~~~~~~~~~~~~~~~~~~~~~~oooo~o~o 0.014705s ooooooooooooooooooooooooooooooooooo 0.001292s ooooooooooooooooooooooooooooooooooooo
We observe that deleted variables appear mostly on the right. This is the so-called principal of temporal locality.
.. SEEALSO::
:meth:`history_enable`, :meth:`history_disable`, :meth:`history_clear` """ # Legend: # o : tracked element # ~ : element marked for deletion # r : partial reduction # R : full Hermite reduction status[index] = '~' else: else: status = status[:index] + ['o'] + status[index:] else: raise NotImplementedError
def timings(self, action=None): r""" Return cumulated timings (grouped by actions) since the last time history has been cleared.
INPUT:
- ``action`` -- ``None`` (the default), ``add``, ``mark``, ``del``, ``partial reduce`` or ``full reduce``; if not None, return the cumulated timing corresponding to this action; otherwise, return a dictionary
Here are the meanings of the keywords above: - ``add``: time spent in adding new colunmns to the precision matrix (corresponding to the creation of new elements) - ``mark``: time spent in marking elements for deletion - ``del``: time spent in deleting columns of the precision matrix and re-echelonizing the matrix - ``partial reduce``: time spent in partial Hermite reduction - ``full reduce``: time spent in full Hermite reduction.
EXAMPLES::
sage: R = ZpLC(2, label='timings') sage: prec = R.precision() sage: prec.history_enable() sage: M = random_matrix(R, 5, 5) sage: N = M^10 sage: prec.timings() # somewhat random {'add': 1.0530245304107666, 'del': 0.24358701705932617, 'mark': 0.0013289451599121094, 'partial reduce': 0.21604204177856445 'full reduce': 0}
TESTS::
sage: prec.history_clear() sage: prec.timings() {'add': 0, 'del': 0, 'full reduce': 0, 'mark': 0, 'partial reduce': 0} """ raise ValueError("History is not tracked") if tme_by_event.has_key(action): return tme_by_event[action] else: raise ValueError("invalid event")
class PrecisionLattice(UniqueRepresentation, DifferentialPrecisionGeneric): r""" A class for handling precision lattices which are used to track precision in the ZpLC model.
The precision lattice is stored as a triangular matrix whose rows are generators of the lattice.
INPUT:
- ``p`` -- a prime number
- ``label`` -- a string, the label of the parents to which the elements tracked by this lattice belong.
.. NOTE::
You should not create instances of this class directly. The precision lattice is automatically initialized at the creation of the parent.
EXAMPLES::
sage: R = ZpLC(2, label='init') sage: R.precision() Precision lattice on 0 objects (label: init) """ def __init__(self, p, label): r""" TESTS::
sage: from sage.rings.padics.lattice_precision import PrecisionLattice sage: R = ZpLC(2) sage: isinstance(R.precision(), PrecisionLattice) True
"""
# We need to copy this method. # Indeed otherwise it is inherited from UniqueRepresentation def __reduce__(self): r""" TESTS::
sage: R = ZpLC(2) sage: prec = R.precision() sage: dumps(prec) Traceback (most recent call last): ... NotImplementedError: pickling/unpickling precision modules is not implemented yet """
def _index(self, ref): r""" Return the index of the element whose reference is ``ref``.
TESTS::
sage: from sage.rings.padics.lattice_precision import pAdicLatticeElementWeakProxy sage: R = ZpLC(2, label="index") sage: prec = R.precision() sage: x = R(1, 10) sage: y = R(1, 5)
sage: prec._index(pAdicLatticeElementWeakProxy(x)) 0 sage: prec._index(pAdicLatticeElementWeakProxy(y)) 1
sage: del x sage: prec.del_elements() sage: prec._index(pAdicLatticeElementWeakProxy(y)) 0 """
def dimension(self): r""" Return the dimension of this lattice.
EXAMPLES::
sage: R = ZpLC(5, label='dimension') sage: prec = R.precision() sage: prec.dimension() 0
sage: x = R(1, 10) sage: prec.dimension() 1 """
def reduce(self, index=0, partial=False): r""" Reduce the size of the entries above the diagonal of the precision matrix.
INPUT:
- ``index`` -- an integer, the starting row for which the reduction is performed
- ``partial`` -- a boolean (default: False) specifying whether a partial or a full Hermite reduction should be performed
NOTE:
The partial reduction has cost `O(m^2)` where `m` is the number of rows that need to be reduced (that is the difference between the total number of rows and ``index``).
The full Hermite reduction has cost `O(m^3)`.
.. NOTE::
The software ensures that the precision lattice is always partially reduced. Calling the function manually with the argument ``partial=True`` should then just do nothing.
TESTS::
sage: R = ZpLC(2) sage: x = R.random_element() sage: del x sage: R.precision().del_elements() # indirect doctest """ # Partial reduction # Cost: O(m^2) with m = n-index # We update history else: # Full Hermite reduction # Cost: O(m^3) with m = n-index # In what follows, we assume that col[j] is a power of p col[i] = reduced col[i].normalize() for j2 in range(j+1, n): col2 = self._matrix[self._elements[j2]] col2[i] -= scalar*col2[i] col2[i].normalize() # We update history
def _new_element(self, x, dx, bigoh, dx_mode='linear_combination', capped=False): r""" Update the lattice when a new element is created.
This function is not meant to be called manually. It is automatically called by the parent when a new element is created.
INPUT:
- ``x`` -- the newly created element
- ``dx`` -- a dictionary representing the differential of ``x``
- ``bigoh`` -- an integer or ``None`` (default: ``None``): the bigoh to be added to the precision of ``x``; if ``None``, the default cap is used.
- ``dx_mode`` -- a string, either ``linear_combination`` (the default) or ``values``
- ``capped`` -- a boolean, whether this element has been capped according to the parent's cap
If ``dx_mode`` is ``linear_combination``, the dictionary ``dx`` encodes the expression of the differential of ``x``. For example, if ``x`` was defined as ``x = y*z`` then:
.. MATH::
dx = y dz + z dy
and the corresponding dictionary is ``{z: y, y: z}`` (except that the keys are not the elements themselves but weak references to them).
If ``dx_mode`` is ``values``, the dictionary ``dx`` directly specifies the entries that have to be stored in the precision lattice. This mode is only used for multiple conversion between different parents (see :meth:`multiple_conversion`).
TESTS::
sage: R = ZpLC(2) sage: x = R.random_element() sage: y = R.random_element() sage: z = x*y # indirect doctest """ # First we delete some elements marked for deletion
# Then we add the new element scalar = pRational(p, scalar) else: raise ValueError("dx_mode must be either 'linear_combination' or 'values'")
# We update history
def del_elements(self, threshold=None): r""" Erase columns of the lattice precision matrix corresponding to elements which are marked for deletion and echelonize the matrix in order to keep it upper triangular.
INPUT:
- ``threshold`` -- an integer or ``None`` (default: ``None``): a column whose distance to the right is greater than the threshold is not erased
EXAMPLES::
sage: R = ZpLC(2, label='delelts') sage: prec = R.precision()
sage: x = R(1, 10) sage: prec Precision lattice on 1 object (label: delelts) sage: prec.precision_lattice() [1024]
sage: del x sage: prec Precision lattice on 1 object (label: delelts) sage: prec.precision_lattice() [1024]
sage: prec.del_elements() sage: prec Precision lattice on 0 objects (label: delelts) sage: prec.precision_lattice() [] """
# We mark new collected elements for deletion # The list self._collected_references can be updated while # the loop runs. # However, we do not need to copy it because Python supports # iteration over a list to which elements are added.
# We erase corresponding columns and echelonize
# Now, we echelonize else:
# We update history
# And we reduce a bit # (we do not perform a complete reduction because it is costly)
def _lift_to_precision(self, x, prec): r""" Lift the specified element to the specified precision.
INPUT:
- ``x`` -- the element whose precision has to be lifted
- ``prec`` -- the new precision
NOTE:
The new precision lattice is computed as the intersection of the current precision lattice with the subspace
..MATH::
p^{prec} \Z_p dx \oplus \bigoplus_{y \neq x} \Q_p dy
This function may change at the same time the precision of other elements having the same parent.
.. NOTE::
This function is not meant to be called directly. Use ``x.lift_to_precision`` instead.
EXAMPLES::
sage: R = ZpLC(2) sage: x = R(1, 10); x 1 + O(2^10) sage: y = R(1, 5); y 1 + O(2^5) sage: z = x + y; z 2 + O(2^5)
sage: prec = R.precision() sage: prec._lift_to_precision(z, 12) sage: z 2 + O(2^12) sage: y 1 + O(2^10) """
rows_by_val[v].append(i) else:
# We clear the entry on the i-th row # We rescale the piv-th row # Now the entry on the piv-th row has valuation w # We update the dictionary accordingly
def _precision_absolute_data(self, x): r""" Return absolute precision data for ``x``.
.. NOTE::
Helper method for :meth:`_precision_absolute` and :meth:`_is_precision_capped`.
TESTS::
sage: R = ZpLC(2) sage: x = R(1, 10); x 1 + O(2^10) sage: y = R(1, 5); y 1 + O(2^5) sage: z = x + y; z 2 + O(2^5) sage: z.precision_absolute() # indirect doctest 5 """
def _precision_absolute(self, x): r""" Return the absolute precision of the given element.
INPUT:
- ``x`` -- an element in the parent corresponding to this lattice
.. NOTE::
The absolute precision is obtained by projecting the precision lattice onto the line of coordinate ``dx``.
This function is not meant to be called directly. Call ``x.precision_absolute()`` instead.
EXAMPLES::
sage: R = ZpLC(2) sage: x = R(1, 10); x 1 + O(2^10) sage: y = R(1, 5); y 1 + O(2^5) sage: z = x + y; z 2 + O(2^5) sage: z.precision_absolute() # indirect doctest 5 """
def _is_precision_capped(self, x): r""" Return whether the absolute precision of ``x`` results from a cap coming from the parent.
INPUT:
- ``x`` -- an element in the parent corresponding to this lattice
.. NOTE::
This function is not meant to be called directly. Call ``x.is_precision_capped`` instead.
EXAMPLES::
sage: R = ZpLC(2) sage: x = R(1, 10); x 1 + O(2^10) sage: x.is_precision_capped() # indirect doctest False
sage: y = x-x; y O(2^40) sage: y.is_precision_capped() # indirect doctest True """
def precision_lattice(self, elements=None): r""" Return a matrix representing the precision lattice on a subset of elements.
INPUT:
- ``elements`` -- a list of elements or ``None`` (default: ``None``)
- ``echelon`` -- a boolean (default: ``True``); whether the result should be in echelon form
EXAMPLES::
sage: R = ZpLC(2, label='preclattice') sage: prec = R.precision() sage: x = R(1, 10); y = R(1, 5) sage: u = x + y sage: v = x - y sage: prec.precision_lattice() [ 1024 0 1024 1024] [ 0 32 32 1099511627744] [ 0 0 2097152 0] [ 0 0 0 1099511627776] sage: prec.precision_lattice([u, v]) [ 32 2016] [ 0 2048]
Here is another example with matrices::
sage: M = matrix(R, 2, 2, [R(3, 5), R(7, 5), R(1, 5), R(11, 1)]) sage: N = M^10 sage: prec.precision_lattice() 23 x 23 dense matrix over Integer Ring (use the '.str()' method to see the entries)
The next syntax provides as easy way to select an interesting subset of variables (the selected subset consists of the four entries of the matrix ``N``)::
sage: prec.precision_lattice(N) [ 2048 512 28160 230400] [ 0 2048 14336 258048] [ 0 0 65536 65536] [ 0 0 0 262144]
We can give a list of matrices as well::
sage: prec.precision_lattice([M, N]) [ 32 0 0 0 226115584 96788480 52174848 82804736] [ 0 32 0 0 52174848 121765888 11829248 28516352] [ 0 0 32 0 96788480 42762240 121765888 199614464] [ 0 0 0 2 5175296 12475904 1782272 4045824] [ 0 0 0 0 268435456 0 0 0] [ 0 0 0 0 0 268435456 0 0] [ 0 0 0 0 0 0 268435456 0] [ 0 0 0 0 0 0 0 268435456] """ else: M *= self._p ** (-val) M *= self._p ** val
class PrecisionModule(UniqueRepresentation, DifferentialPrecisionGeneric): r""" A class for handling precision modules which are used to track precision in the ZpLF model.
The precision module (which is not necessarily a lattice) is stored as a matrix whose rows are generators. """ def __init__(self, p, label, prec): r""" Initialize this precision module.
INPUT:
- ``p`` -- a prime number
- ``label`` -- a string, the label of the parents to which belong the elements tracked by this precision module
NOTE:
The precision module is automatically initialized at the creation of the parent.
TESTS::
sage: R = ZpLF(2, label='init') sage: R.precision() Precision module on 0 objects (label: init) """ # elements whose valuation are not less than self._zero_cap are assumed to vanish
# We need to copy this method. # Indeed otherwise it is inherited from UniqueRepresentation def __reduce__(self): r""" TESTS::
sage: R = ZpLF(2) sage: prec = R.precision() sage: dumps(prec) Traceback (most recent call last): ... NotImplementedError: pickling/unpickling precision modules is not implemented yet """
def internal_prec(self): r""" Return the relative precision at which computations is handled internally.
It is slightly greater than the actual precision and increases a bit (at a logarithmic rate) when new elements are created and/or computed.
EXAMPLES::
sage: R = ZpLF(5, prec=20, label='internal_prec') sage: prec = R.precision()
sage: prec.internal_prec() 25
sage: L = [ R.random_element() for _ in range(50) ] sage: prec.internal_prec() 28 """
def dimension(self): r""" Return the dimension of this precision module.
EXAMPLES:
In general, the dimension increases by 1 when a new element with a given precision is created::
sage: R = ZpLF(2, label='dimension') sage: prec = R.precision()
sage: prec.dimension() 0 sage: x = R.random_element(prec=10) sage: prec.dimension() 1 sage: y = R.random_element(prec=10) sage: prec.dimension() 2
However in general it does not increase while doing computations::
sage: u = x + y sage: v = x^2 + 3*y + x*y + y^3 sage: prec.dimension() 2
Of course, it may also decrease when a sufficient number of variables are collected::
sage: del x, y, u sage: prec.del_elements() sage: prec.dimension() 1
sage: del v sage: prec.del_elements() sage: prec.dimension() 0 """
def is_lattice(self): r""" Return ``True`` if this precision module is a lattice (i.e. has maximal dimension).
EXAMPLES::
sage: R = ZpLF(2, label='is_lattice') sage: prec = R.precision()
sage: x = R(1, 10) sage: y = R(1, 5) sage: prec.is_lattice() True
sage: u = x + y sage: prec.is_lattice() False
.. SEEALSO::
:meth:`dimension` """
def _new_element(self, x, dx, bigoh, dx_mode='linear_combination'): r""" Update the lattice when a new element is created.
This function is not meant to be called manually. It is automatically called by the parent when a new element is created.
INPUT:
- ``x`` -- the newly created element
- ``dx`` -- a dictionary representing the differential of ``x``
- ``bigoh`` -- an integer or ``None`` (default: ``None``): the bigoh to be added to the precision of ``x``; if ``None``, the default cap is used.
- ``dx_mode`` -- a string, either ``"linear_combination"`` (the default) or ``"values"``
If ``dx_mode`` is ``"linear_combination"``, the dictionary ``dx`` encodes the expression of the differential of ``x``. For example, if ``x`` was defined as ``x = y*z`` then:
.. MATH::
dx = y dz + z dy
and the corresponding dictionary is ``{z: y, y: z}`` (except that the keys are not the elements themselves but weak references to them).
If ``dx_mode`` is ``"values"``, the dictionary ``dx`` directly specifies the entries that have to stored in the precision module. This mode is only used for multiple conversion between different parents (see :meth:`multiple_conversion`).
TESTS::
sage: R = ZpLF(2) sage: x = R.random_element() sage: y = R.random_element() sage: z = x*y # indirect doctest """ # First we delete some elements marked for deletion self.del_elements(threshold=self._threshold_deletion)
# We increase the internal prec # The heuristic behind this is the following: when computing # with N digits of precision, we except that about N-log_p(c) # of them are correct after c elementary operations.
scalar = pRational(p, scalar) elif dx_mode == 'values': for elt, scalar in dx: ref = pAdicLatticeElementWeakProxy(elt) if not isinstance(scalar, pRational): scalar = pRational(p, scalar) i = self._index(ref) col[i] = scalar else: raise ValueError("dx_mode must be either 'linear_combination' or 'values'")
# We update history self._history.append(('add', None, walltime(tme)))
def del_elements(self, threshold=None): r""" Erase columns of the lattice precision matrix corresponding to elements which were collected by the garbage collector. Then reduce the matrix in order to keep it in echelon form.
INPUT:
- ``threshold`` -- an integer or ``None`` (default: ``None``): a non-pivot column whose distance to the right is greater than the threshold is not erased but only marked for future deletion
EXAMPLES::
sage: R = ZpLF(2, label='delelts') sage: prec = R.precision()
sage: x = R(1, 10) sage: prec Precision module on 1 object (label: delelts) sage: prec.precision_lattice() [1024]
sage: del x sage: prec Precision module on 1 object (label: delelts) sage: prec.precision_lattice() [1024]
sage: prec.del_elements() sage: prec Precision module on 0 objects (label: delelts) sage: prec.precision_lattice() [] """
# We mark new collected elements for deletion # The list self._collected_references can be updated while # the loop runs. # However, we do not need to copy it because Python supports # iteration over a list to which elements are added. else: self._history.append(('mark', index, walltime(tme))) else: # if the column is not a pivot, we erase it without delay # (btw, is it a good idea?) self._history.append(('del', index, walltime(tme)))
# We erase corresponding columns and echelonize
# another pivot has been found, we place it in front
# No pivot was found. We re-echelonize del self._matrix[self._elements[i]][-1] # col is the column of index "end" # its size is (length + 1) col = self._matrix[self._elements[j]] a1 = u*col[length-1]; a2 = v*col[length]; a = a1 + a2 b1 = up*col[length-1]; b2 = vp*col[length]; b = b1 + b2 if a.valuation() > min(a1.valuation(), a2.valuation()) + self._zero_cap: col[length-1] = self._approx_zero else: col[length-1] = a.reduce_relative(self._internal_prec) if b.valuation() > min(b1.valuation(), b2.valuation()) + self._zero_cap: col[length] = self._approx_zero else: col[length] = b.reduce_relative(self._internal_prec)
# We update history self._history.append(('del', index, walltime(tme)))
def _lift_to_precision(self, x, prec): r""" Lift the specified element to the specified precision.
INPUT:
- ``x`` -- the element whose precision has to be lifted
- ``prec`` -- the new precision
NOTE:
The new precision lattice is computed as the intersection of the current precision lattice with the subspace
..MATH::
p^{prec} \Z_p dx \oplus \bigoplus_{y \neq x} \Q_p dy
This function may change at the same time the precision of other elements having the same parent.
.. NOTE::
This function is not meant to be called directly. Use ``x.lift_to_precision`` instead.
EXAMPLES::
sage: R = ZpLF(2) sage: x = R(1, 10); x 1 + O(2^10) sage: y = R(1, 5); y 1 + O(2^5) sage: u = x^2 + x*y sage: v = y^2 + x*y sage: w = u + v
sage: prec = R.precision() sage: prec._lift_to_precision(w, 11) sage: w 2^2 + O(2^11) sage: y 1 + O(2^9) """
rows_by_val[v].append(i) else:
# We clear the entry on the i-th row scalar = (col[i]/col[piv]).reduce(prec-v) for j in range(n): col_cur = self._matrix[self._elements[j]] if len(col_cur) > piv: col_cur[i] -= scalar*col_cur[piv] col_cur[i] = col_cur[i].reduce_relative(self._internal_prec) # We rescale the piv-th row # (if w is Infinity, we delete it) del col_cur[piv] else: # Now the entry on the piv-th row has valuation w # We update the dictionary accordingly rows_by_val[w].append(piv)
def _precision_absolute(self, x): r""" Return the absolute precision of the given element.
INPUT:
- ``x`` -- the element whose absolute precision is requested
.. NOTE::
The absolute precision is obtained by projecting the precision module onto the line of coordinate ``dx``.
This function is not meant to be called directly. Call ``x.precision_absolute()`` instead.
EXAMPLES::
sage: R = ZpLF(2) sage: prec = R.precision()
sage: x = R(1, 10); x 1 + O(2^10) sage: y = R(1, 5); y 1 + O(2^5) sage: z = x + y; z 2 + O(2^5) sage: z.precision_absolute() # indirect doctest 5
In some cases, the absolute precision returned by this function may be infinite::
sage: y = R(1) sage: prec._precision_absolute(y) +Infinity
However calling the method :meth:`absolute_precision` of the element itself reintroduces a cap::
sage: y.precision_absolute() 20 """ else:
def precision_lattice(self, elements=None): r""" Return a matrix representing the precision lattice on a subset of elements.
INPUT:
- ``elements`` -- a list of elements or ``None`` (default: ``None``)
EXAMPLES::
sage: R = ZpLF(2, label='preclattice') sage: prec = R.precision() sage: x = R(1, 10); y = R(1, 5) sage: prec.precision_lattice() [1024 0] [ 0 32]
sage: u = x + y sage: v = x - y sage: prec.precision_lattice([u, v]) [ 32 2016] [ 0 2048]
If the precision module does not project to a lattice, an error is raised.
sage: prec.precision_lattice([x, y, u, v]) Traceback (most recent call last): ... PrecisionError: the differential is not surjective
Here is another example with matrices::
sage: M = matrix(R, 2, 2, [R(3, 5), R(7, 5), R(1, 5), R(11, 1)]) sage: N = M^10
The next syntax provides as easy way to select an interesting subset of variables (the selected subset consists of the four entries of the matrix ``N``)::
sage: prec.precision_lattice(N) [ 2048 512 28160 230400] [ 0 2048 14336 258048] [ 0 0 65536 65536] [ 0 0 0 262144] """ else: M *= self._p ** (-val) M *= self._p ** val
class pAdicLatticeElementWeakProxy(object): r""" The implementations of :class:`DifferentialPrecisionGeneric` hold weak references to :class:`pAdicLatticeElement`. They are stored in dictionaries, e.g., a dictionary that maps an element to the corresponding column in the precision lattice matrix. However, weak references as implemented by Python are tricky to use as dictionary keys. Their equality depends on the equality of the element they point to (as long as that element is alive) and then on the equality by ``id``. This means that statements such as: ``ref in D == ref in D`` could be false if the garbage collector kicks in between the two invocations. To prevent very subtle and hardly reproducible bugs, we wrap weak references in a proxy that gives every lattice element a unique increasing id and uses that id for comparisons.
EXAMPLES:
Proxy elements exist only internally and are not usually exposed to the user::
sage: from sage.rings.padics.lattice_precision import pAdicLatticeElementWeakProxy sage: R = ZpLF(2, label='proxy') sage: p = R(2) sage: prec = R.precision() sage: proxy = prec._elements[0] sage: isinstance(proxy, pAdicLatticeElementWeakProxy) True """ _next_id = 0
def __init__(self, element, callback=None): r""" TESTS::
sage: from sage.rings.padics.lattice_precision import pAdicLatticeElementWeakProxy sage: R = ZpLF(2, label='proxy') sage: p = R(2) sage: pAdicLatticeElementWeakProxy(p) == pAdicLatticeElementWeakProxy(p) True sage: pAdicLatticeElementWeakProxy(p) is pAdicLatticeElementWeakProxy(p) False
"""
def __hash__(self): r""" Return a hash value for this proxy.
EXAMPLES::
sage: from sage.rings.padics.lattice_precision import pAdicLatticeElementWeakProxy sage: R = ZpLF(2, label='proxy') sage: p = R(2) sage: hash(pAdicLatticeElementWeakProxy(p)) == hash(pAdicLatticeElementWeakProxy(p)) True
"""
def __eq__(self, other): r""" Return whether this proxy is undistinguishable from ``other``.
EXAMPLES::
sage: from sage.rings.padics.lattice_precision import pAdicLatticeElementWeakProxy sage: R = ZpLF(2, label='proxy') sage: p = R(2) sage: q = R(2) sage: pAdicLatticeElementWeakProxy(p) == pAdicLatticeElementWeakProxy(p) True sage: pAdicLatticeElementWeakProxy(q) == pAdicLatticeElementWeakProxy(p) False
"""
def __call__(self): r""" Return the lattice element this proxy points to, or ``None`` if the target has already been finalized.
EXAMPLES::
sage: from sage.rings.padics.lattice_precision import pAdicLatticeElementWeakProxy sage: R = ZpLF(2, label='proxy') sage: p = R(2) sage: pAdicLatticeElementWeakProxy(p)() 2 + O(2^21)
"""
def __repr__(self): r""" Return a printable representation of this proxy.
EXAMPLES::
sage: from sage.rings.padics.lattice_precision import pAdicLatticeElementWeakProxy sage: R = ZpLF(2, label='proxy_repr') sage: p = R(2) sage: R.precision()._elements # indirect doctest [WeakProxy#...]
"""
def list_of_padics(elements): r""" Convert a list of p-adic composed elements (such as polynomials, matrices) to a list of weak references of their p-adic coefficients.
This is a helper function for the method :meth:`precision_lattice`.
TESTS::
sage: from sage.rings.padics.lattice_precision import list_of_padics sage: R = ZpLC(2) sage: M = random_matrix(R, 2, 2) sage: list_of_padics(M) [WeakProxy#..., WeakProxy#..., WeakProxy#..., WeakProxy#...] """ elements = elements.coefficients() |