Lattice precision for the parents ZpLC/QpLC and ZpLF/QpLF

AUTHOR:

  • Xavier Caruso (2018-02): initial version

class sage.rings.padics.lattice_precision.DifferentialPrecisionGeneric(p, label)[source]

Bases: SageObject

A generic class for precision objects obtained by automatic differentiation.

INPUT:

  • p – a prime number

  • label – 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)

>>> from sage.all import *
>>> R = ZpLC(Integer(2), label='init')
>>> R.precision()
Precision lattice on 0 objects (label: init)
ambient_dimension()[source]

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

>>> from sage.all import *
>>> R = ZpLC(Integer(2), label='ambient_dim')
>>> prec = R.precision()

>>> x, y = R(Integer(1), Integer(10)), R(Integer(1), Integer(5))
>>> prec.ambient_dimension()
2
>>> prec.dimension()
2

>>> u = x + y
>>> prec.ambient_dimension()
3
>>> 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
[Python] 
>>> from sage.all import *
>>> R = ZpLF(Integer(2), label='ambient_dim')
>>> prec = R.precision()

>>> x, y = R(Integer(1), Integer(10)), R(Integer(1), Integer(5))
>>> prec.ambient_dimension()
2
>>> prec.dimension()
2

>>> u = x + y
>>> prec.ambient_dimension()
3
>>> prec.dimension()
2
del_elements(threshold=None)[source]

Delete (or mark for future deletion) the columns of precision matrix corresponding to elements that were collected by the garbage collector.

INPUT:

  • threshold – 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()                                              # needs sage.geometry.polyhedron
[1024]

sage: del x
sage: prec
Precision lattice on 1 object (label: del_elements)
sage: prec.precision_lattice()                                              # needs sage.geometry.polyhedron
[1024]

sage: prec.del_elements()
sage: prec
Precision lattice on 0 objects (label: del_elements)
sage: prec.precision_lattice()                                              # needs sage.geometry.polyhedron
[]

>>> from sage.all import *
>>> R = ZpLC(Integer(2), label='del_elements')
>>> prec = R.precision()

>>> x = R(Integer(1), Integer(10))
>>> prec
Precision lattice on 1 object (label: del_elements)
>>> prec.precision_lattice()                                              # needs sage.geometry.polyhedron
[1024]

>>> del x
>>> prec
Precision lattice on 1 object (label: del_elements)
>>> prec.precision_lattice()                                              # needs sage.geometry.polyhedron
[1024]

>>> prec.del_elements()
>>> prec
Precision lattice on 0 objects (label: del_elements)
>>> prec.precision_lattice()                                              # needs sage.geometry.polyhedron
[]
diffused_digits(elements=None)[source]

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])                                          # needs sage.geometry.polyhedron
0
sage: prec.diffused_digits([u, v])                                          # needs sage.geometry.polyhedron
6

>>> from sage.all import *
>>> R = ZpLC(Integer(2))
>>> prec = R.precision()
>>> x = R(Integer(1), Integer(10)); y = R(Integer(1), Integer(5))
>>> u = x + y
>>> v = x - y

>>> prec.diffused_digits([x, y])                                          # needs sage.geometry.polyhedron
0
>>> prec.diffused_digits([u, v])                                          # needs sage.geometry.polyhedron
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)])            # needs sage.modules
sage: N = M^10                                                              # needs sage.modules
[Python] 
>>> from sage.all import *
>>> M = matrix(R, Integer(2), Integer(2), [R(Integer(3), Integer(5)), R(Integer(7), Integer(5)), R(Integer(1), Integer(5)), R(Integer(11), Integer(1))])            # needs sage.modules
>>> N = M**Integer(10)                                                              # needs sage.modules

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)                                               # needs sage.geometry.polyhedron sage.modules
17

>>> from sage.all import *
>>> prec.diffused_digits(N)                                               # needs sage.geometry.polyhedron sage.modules
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])                                          # needs sage.geometry.polyhedron
+Infinity
[Python] 
>>> from sage.all import *
>>> R = ZpLF(Integer(2))
>>> prec = R.precision()
>>> x = R(Integer(1), Integer(10))
>>> y = x
>>> prec.diffused_digits([x, y])                                          # needs sage.geometry.polyhedron
+Infinity
dimension()[source]

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

>>> from sage.all import *
>>> R = ZpLC(Integer(5), label='dim')
>>> prec = R.precision()
>>> prec.dimension()
0

>>> x = R(Integer(1), Integer(10))
>>> prec.dimension()
1
history(compact=True, separate_reduce=False, timings=True, output_type='asciiart')[source]

Show history.

The history records creations and deletions of elements attached to this precision lattice, together with many timings.

INPUT:

  • compact – boolean (default: True); if True, all consecutive operations of the same type appear on a single row

  • separate_reduce – boolean (default: False); specify whether partial/full Hermite reduction should be displayed separately

  • timings – 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 history_enable()) before use.

EXAMPLES:

sage: R = ZpLC(2, label='history_en')
sage: prec = R.precision()

>>> from sage.all import *
>>> R = ZpLC(Integer(2), label='history_en')
>>> prec = R.precision()

We first enable history:

sage: prec.history_enable()
[Python] 
>>> from sage.all import *
>>> prec.history_enable()

At the beginning, the history is of course empty:

sage: print(prec.history())
 Timings
   ---

>>> from sage.all import *
>>> 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
[Python] 
>>> from sage.all import *
>>> L = [R.random_element() for _ in range(Integer(20))]
>>> for p in range(Integer(20)):
...    if is_prime(p): L[p] = None
>>> prec.del_elements()

>>> 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 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

>>> from sage.all import *
>>> print(prec.history(timings=False))
oooooooooooooooooooo
oo~~o~o~ooo~o~ooo~o~
oooooooooooo

>>> 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
[Python] 
>>> from sage.all import *
>>> prec.reduce()
>>> 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)                                               # needs sage.geometry.polyhedron
sage: d = M.determinant()                                                   # needs sage.geometry.polyhedron
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

>>> from sage.all import *
>>> R = ZpLC(Integer(3))
>>> prec = R.precision()
>>> prec.history_enable()
>>> M = random_matrix(R, Integer(5))                                               # needs sage.geometry.polyhedron
>>> d = M.determinant()                                                   # needs sage.geometry.polyhedron
>>> 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.

See also

history_enable(), history_disable(), history_clear()

history_clear()[source]

Clear history.

We refer to the documentation of the method history() for a complete documentation (including examples) about history.

See also

history(), history_enable(), history_disable()

history_disable()[source]

Disable history.

We refer to the documentation of the method history() for a complete documentation (including examples) about history.

See also

history(), history_enable(), history_clear()

history_enable()[source]

Enable history.

We refer to the documentation of the method history() for a complete documentation (including examples) about history.

See also

history(), history_disable(), history_clear()

precision_lattice(elements=None)[source]

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 – 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()                                              # needs sage.geometry.polyhedron
[         1024             0          1024          1024]
[            0            32            32 1099511627744]
[            0             0       2097152             0]
[            0             0             0 1099511627776]
sage: prec.precision_lattice([u, v])                                        # needs sage.geometry.polyhedron
[  32 2016]
[   0 2048]

>>> from sage.all import *
>>> R = ZpLC(Integer(2), label='precision_lattice')
>>> prec = R.precision()
>>> x = R(Integer(1), Integer(10)); y = R(Integer(1), Integer(5))
>>> u = x + y
>>> v = x - y
>>> prec.precision_lattice()                                              # needs sage.geometry.polyhedron
[         1024             0          1024          1024]
[            0            32            32 1099511627744]
[            0             0       2097152             0]
[            0             0             0 1099511627776]
>>> prec.precision_lattice([u, v])                                        # needs sage.geometry.polyhedron
[  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])                                     # needs sage.geometry.polyhedron
Traceback (most recent call last):
...
PrecisionError: the differential is not surjective
[Python] 
>>> from sage.all import *
>>> R = ZpLF(Integer(2), label='precision_lattice')
>>> prec = R.precision()
>>> x = R(Integer(1), Integer(10)); y = R(Integer(1), Integer(5))
>>> u = x + y
>>> v = x - y
>>> prec.precision_lattice([x,y,u,v])                                     # needs sage.geometry.polyhedron
Traceback (most recent call last):
...
PrecisionError: the differential is not surjective
prime()[source]

Return the underlying prime number attached to this precision lattice.

EXAMPLES:

sage: R = ZpLC(2, label='mylabel')
sage: R.precision().prime()
2

>>> from sage.all import *
>>> R = ZpLC(Integer(2), label='mylabel')
>>> R.precision().prime()
2
threshold_deletion(threshold=None)[source]

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 – nonnegative 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

>>> from sage.all import *
>>> R = ZpLC(Integer(2), label='threshold_deletion')
>>> prec = R.precision()
>>> prec.threshold_deletion()
50

>>> prec.threshold_deletion(Integer(20))
20
>>> prec.threshold_deletion()
20

>>> prec.threshold_deletion(-Integer(2))
Traceback (most recent call last):
...
ValueError: The threshold must be a nonnegative integer or Infinity
timings(action=None)[source]

Return cumulated timings (grouped by actions) since the last time history has been cleared.

INPUT:

  • action – None (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 columns 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)                                            # needs sage.geometry.polyhedron
sage: N = M^10                                                              # needs sage.geometry.polyhedron
sage: prec.timings()    # somewhat random
{'add': 1.0530245304107666,
 'del': 0.24358701705932617,
 'mark': 0.0013289451599121094,
 'partial reduce': 0.21604204177856445
 'full reduce': 0}

>>> from sage.all import *
>>> R = ZpLC(Integer(2), label='timings')
>>> prec = R.precision()
>>> prec.history_enable()
>>> M = random_matrix(R, Integer(5), Integer(5))                                            # needs sage.geometry.polyhedron
>>> N = M**Integer(10)                                                              # needs sage.geometry.polyhedron
>>> prec.timings()    # somewhat random
{'add': 1.0530245304107666,
 'del': 0.24358701705932617,
 'mark': 0.0013289451599121094,
 'partial reduce': 0.21604204177856445
 'full reduce': 0}
tracked_elements(values=True, dead=True)[source]

Return the list of tracked elements.

INPUT:

  • values – boolean (default: True); if False, the method returns a list of weak references on tracked elements instead

  • dead – 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#...]

>>> from sage.all import *
>>> R = ZpLC(Integer(2), label='tracked')
>>> prec = R.precision()
>>> x = R(Integer(1), Integer(10)); y = R(Integer(1), Integer(5))
>>> prec.tracked_elements()
[1 + O(2^10), 1 + O(2^5)]
>>> prec.tracked_elements(values=False)
[WeakProxy#...,
 WeakProxy#...,
 WeakProxy#...]
>>> prec.tracked_elements(values=False, dead=False)
[WeakProxy#...,
 WeakProxy#...]

>>> u = x + y
>>> v = x - y
>>> prec.tracked_elements()
[1 + O(2^10), 1 + O(2^5), 2 + O(2^5), O(2^5)]
>>> prec.tracked_elements(values=False)
[WeakProxy#...,
 WeakProxy#...,
 WeakProxy#...,
 WeakProxy#...,
 WeakProxy#...]
>>> del x; del y
>>> prec.tracked_elements()
[None, None, 2 + O(2^5), O(2^5), None]
>>> prec.tracked_elements(values=False)
[WeakProxy#...,
 WeakProxy#...,
 WeakProxy#...]
class sage.rings.padics.lattice_precision.PrecisionLattice(p, label)[source]

Bases: UniqueRepresentation, DifferentialPrecisionGeneric

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 – 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)

>>> from sage.all import *
>>> R = ZpLC(Integer(2), label='init')
>>> R.precision()
Precision lattice on 0 objects (label: init)
del_elements(threshold=None)[source]

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 – 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()                                              # needs sage.geometry.polyhedron
[1024]

sage: del x
sage: prec
Precision lattice on 1 object (label: delelts)
sage: prec.precision_lattice()                                              # needs sage.geometry.polyhedron
[1024]

sage: prec.del_elements()
sage: prec
Precision lattice on 0 objects (label: delelts)
sage: prec.precision_lattice()                                              # needs sage.geometry.polyhedron
[]

>>> from sage.all import *
>>> R = ZpLC(Integer(2), label='delelts')
>>> prec = R.precision()

>>> x = R(Integer(1), Integer(10))
>>> prec
Precision lattice on 1 object (label: delelts)
>>> prec.precision_lattice()                                              # needs sage.geometry.polyhedron
[1024]

>>> del x
>>> prec
Precision lattice on 1 object (label: delelts)
>>> prec.precision_lattice()                                              # needs sage.geometry.polyhedron
[1024]

>>> prec.del_elements()
>>> prec
Precision lattice on 0 objects (label: delelts)
>>> prec.precision_lattice()                                              # needs sage.geometry.polyhedron
[]
dimension()[source]

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

>>> from sage.all import *
>>> R = ZpLC(Integer(5), label='dimension')
>>> prec = R.precision()
>>> prec.dimension()
0

>>> x = R(Integer(1), Integer(10))
>>> prec.dimension()
1
precision_lattice(elements=None)[source]

Return a matrix representing the precision lattice on a subset of elements.

INPUT:

  • elements – list of elements or None (default: None)

  • echelon – 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()                                              # needs sage.geometry.polyhedron
[         1024             0          1024          1024]
[            0            32            32 1099511627744]
[            0             0       2097152             0]
[            0             0             0 1099511627776]
sage: prec.precision_lattice([u, v])                                        # needs sage.geometry.polyhedron
[  32 2016]
[   0 2048]

>>> from sage.all import *
>>> R = ZpLC(Integer(2), label='preclattice')
>>> prec = R.precision()
>>> x = R(Integer(1), Integer(10)); y = R(Integer(1), Integer(5))
>>> u = x + y
>>> v = x - y
>>> prec.precision_lattice()                                              # needs sage.geometry.polyhedron
[         1024             0          1024          1024]
[            0            32            32 1099511627744]
[            0             0       2097152             0]
[            0             0             0 1099511627776]
>>> prec.precision_lattice([u, v])                                        # needs sage.geometry.polyhedron
[  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)])            # needs sage.modules
sage: N = M^10                                                              # needs sage.modules
sage: prec.precision_lattice()                                              # needs sage.geometry.polyhedron sage.modules
23 x 23 dense matrix over Integer Ring (use the '.str()' method to see the entries)
[Python] 
>>> from sage.all import *
>>> M = matrix(R, Integer(2), Integer(2), [R(Integer(3), Integer(5)), R(Integer(7), Integer(5)), R(Integer(1), Integer(5)), R(Integer(11), Integer(1))])            # needs sage.modules
>>> N = M**Integer(10)                                                              # needs sage.modules
>>> prec.precision_lattice()                                              # needs sage.geometry.polyhedron sage.modules
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)                                             # needs sage.modules
[  2048    512  28160 230400]
[     0   2048  14336 258048]
[     0      0  65536  65536]
[     0      0      0 262144]

>>> from sage.all import *
>>> prec.precision_lattice(N)                                             # needs sage.modules
[  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])                                        # needs sage.modules
[       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]
[Python] 
>>> from sage.all import *
>>> prec.precision_lattice([M, N])                                        # needs sage.modules
[       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]
reduce(index=0, partial=False)[source]

Reduce the size of the entries above the diagonal of the precision matrix.

INPUT:

  • index – integer; the starting row for which the reduction is performed

  • partial – 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.

class sage.rings.padics.lattice_precision.PrecisionModule(p, label, prec)[source]

Bases: UniqueRepresentation, DifferentialPrecisionGeneric

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.

del_elements(threshold=None)[source]

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 – 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()                                              # needs sage.geometry.polyhedron
[1024]

sage: del x
sage: prec
Precision module on 1 object (label: delelts)
sage: prec.precision_lattice()                                              # needs sage.geometry.polyhedron
[1024]

sage: prec.del_elements()
sage: prec
Precision module on 0 objects (label: delelts)
sage: prec.precision_lattice()                                              # needs sage.geometry.polyhedron
[]

>>> from sage.all import *
>>> R = ZpLF(Integer(2), label='delelts')
>>> prec = R.precision()

>>> x = R(Integer(1), Integer(10))
>>> prec
Precision module on 1 object (label: delelts)
>>> prec.precision_lattice()                                              # needs sage.geometry.polyhedron
[1024]

>>> del x
>>> prec
Precision module on 1 object (label: delelts)
>>> prec.precision_lattice()                                              # needs sage.geometry.polyhedron
[1024]

>>> prec.del_elements()
>>> prec
Precision module on 0 objects (label: delelts)
>>> prec.precision_lattice()                                              # needs sage.geometry.polyhedron
[]
dimension()[source]

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

>>> from sage.all import *
>>> R = ZpLF(Integer(2), label='dimension')
>>> prec = R.precision()

>>> prec.dimension()
0
>>> x = R.random_element(prec=Integer(10))
>>> prec.dimension()
1
>>> y = R.random_element(prec=Integer(10))
>>> 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
[Python] 
>>> from sage.all import *
>>> u = x + y
>>> v = x**Integer(2) + Integer(3)*y + x*y + y**Integer(3)
>>> 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

>>> from sage.all import *
>>> del x, y, u
>>> prec.del_elements()
>>> prec.dimension()
1

>>> del v
>>> prec.del_elements()
>>> prec.dimension()
0
internal_prec()[source]

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

>>> from sage.all import *
>>> R = ZpLF(Integer(5), prec=Integer(20), label='internal_prec')
>>> prec = R.precision()

>>> prec.internal_prec()
25

>>> L = [R.random_element() for _ in range(Integer(50))]
>>> prec.internal_prec()
28
is_lattice()[source]

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

>>> from sage.all import *
>>> R = ZpLF(Integer(2), label='is_lattice')
>>> prec = R.precision()

>>> x = R(Integer(1), Integer(10))
>>> y = R(Integer(1), Integer(5))
>>> prec.is_lattice()
True

>>> u = x + y
>>> prec.is_lattice()
False

See also

dimension()

precision_lattice(elements=None)[source]

Return a matrix representing the precision lattice on a subset of elements.

INPUT:

  • elements – 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()                                              # needs sage.geometry.polyhedron
[1024    0]
[   0   32]

sage: u = x + y
sage: v = x - y
sage: prec.precision_lattice([u, v])                                        # needs sage.geometry.polyhedron
[  32 2016]
[   0 2048]

>>> from sage.all import *
>>> R = ZpLF(Integer(2), label='preclattice')
>>> prec = R.precision()
>>> x = R(Integer(1), Integer(10)); y = R(Integer(1), Integer(5))
>>> prec.precision_lattice()                                              # needs sage.geometry.polyhedron
[1024    0]
[   0   32]

>>> u = x + y
>>> v = x - y
>>> prec.precision_lattice([u, v])                                        # needs sage.geometry.polyhedron
[  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])                                  # needs sage.geometry.polyhedron
Traceback (most recent call last):
...
PrecisionError: the differential is not surjective
[Python] 
>>> from sage.all import *
>>> prec.precision_lattice([x, y, u, v])                                  # needs sage.geometry.polyhedron
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)])            # needs sage.modules
sage: N = M^10                                                              # needs sage.modules

>>> from sage.all import *
>>> M = matrix(R, Integer(2), Integer(2), [R(Integer(3), Integer(5)), R(Integer(7), Integer(5)), R(Integer(1), Integer(5)), R(Integer(11), Integer(1))])            # needs sage.modules
>>> N = M**Integer(10)                                                              # needs sage.modules

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)                                             # needs sage.geometry.polyhedron sage.modules
[  2048    512  28160 230400]
[     0   2048  14336 258048]
[     0      0  65536  65536]
[     0      0      0 262144]
[Python] 
>>> from sage.all import *
>>> prec.precision_lattice(N)                                             # needs sage.geometry.polyhedron sage.modules
[  2048    512  28160 230400]
[     0   2048  14336 258048]
[     0      0  65536  65536]
[     0      0      0 262144]
sage.rings.padics.lattice_precision.list_of_padics(elements)[source]

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 precision_lattice().

class sage.rings.padics.lattice_precision.pAdicLatticeElementWeakProxy(element, callback=None)[source]

Bases: object

The implementations of DifferentialPrecisionGeneric hold weak references to 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

>>> from sage.all import *
>>> from sage.rings.padics.lattice_precision import pAdicLatticeElementWeakProxy
>>> R = ZpLF(Integer(2), label='proxy')
>>> p = R(Integer(2))
>>> prec = R.precision()
>>> proxy = prec._elements[Integer(0)]
>>> isinstance(proxy, pAdicLatticeElementWeakProxy)
True
class sage.rings.padics.lattice_precision.pRational(p, x, exponent=0, valuation=None)[source]

Bases: object

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 – integer (default: 0)

  • valuation – 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.

is_p_power()[source]

Return True if this element is a power of \(p\).

is_zero()[source]

Return True if this element vanishes.

list(prec)[source]

Return the list of the digits of this element (written in radix \(p\)) up to position prec.

The first zeros are omitted.

normalize()[source]

Normalize this element, i.e. write it as p^v * u where u is coprime to \(p\).

reduce(prec)[source]

Return this element reduced modulo p^prec.

INPUT:

  • prec – integer

reduce_relative(prec)[source]

Return this element reduced modulo p^n where n = prec + val(x).

INPUT:

  • prec – nonnegative integer

unit_part()[source]

Return the unit part of this element, that is the part u in the writing u * p^v with u coprime to \(p\).

valuation()[source]

Return the \(p\)-adic valuation of this element.

value()[source]

Return this element as a rational number.

xgcd(other)[source]

Return the gcd of self and other together with two elements u and v such that u*self + v*other = gcd.

The gcd is normalized so that it is a power of \(p\).