Differences between revisions 1 and 5 (spanning 4 versions)
 ⇤ ← Revision 1 as of 2009-06-04 13:33:51 → Size: 733 Editor: Minh Nguyen Comment: Lay out structure of release tour ← Revision 5 as of 2009-06-05 21:39:11 → ⇥ Size: 8404 Editor: Minh Nguyen Comment: Summarize #6043 Deletions are marked like this. Additions are marked like this. Line 13: Line 13: * Factoring rational functions (Soroosh Yazdani) -- New method {{{factor()}}} in the class {{{FractionFieldElement}}} of {{{sage/rings/fraction_field_element.pyx}}} to return the factorization of self over the base ring. Here's an example for working with this new method: {{{sage: K. = QQ["x"]sage: f = (x^3 + x) / (x-3)sage: f.factor()(x - 3)^-1 * x * (x^2 + 1) }}} * Faster {{{basis_matrix()}}} for ambient modules (John Cremona) -- The speed-up can be up to 376x faster than previously. The following timing statistics were obtained using the machine sage.math: {{{# BEFOREsage: K = FreeModule(ZZ, 2000)sage: %time I = K.basis_matrix()CPU times: user 292.74 s, sys: 20.11 s, total: 312.85 sWall time: 312.90 s# AFTERsage: K = FreeModule(ZZ, 2000)sage: %time I = K.basis_matrix()CPU times: user 0.41 s, sys: 0.43 s, total: 0.84 sWall time: 0.83 s }}} * Optimize the construction of Lagrange interpolation polynomials (Minh Van Nguyen) -- Rewrite the method {{{lagrange_polynomial()}}} in the class {{{PolynomialRing_field}}} of {{{sage/rings/polynomial/polynomial_ring.py}}} for generating the {{{n}}}-th Lagrange interpolation polynomial. The method now provides two new options:  * {{{algorithm}}} --- (default: {{{divided_difference}}}) If {{{algorithm="divided_difference"}}}, then use the method of divided difference. If {{{algorithm="neville"}}}, then use a variant of Neville's method to recursively generate the {{{n}}}-th Lagrange interpolation polynomial. This adaptation of Neville's method is more memory efficient than the original Neville's method, since the former doesn't generate the full Neville table resulting from Neville's recursive procedure. Instead the adaptation only keeps track of the current and previous rows of the said table.  * {{{previous_row}}} --- (default: {{{None}}}) This is only relevant if used together with {{{algorithm="neville"}}}. Here "previous row" refers to the last row in the Neville table that was obtained from a previous computation of an {{{n}}}-th Lagrange interpolation polynomial using Neville's method. If the last row is provided, then use a memory efficient variant of Neville's method to recursively generate a better interpolation polynomial from the results of previous computation.  There's also the new method {{{divided_difference()}}} to compute the Newton divided-difference coefficients of the {{{n}}}-th Lagrange interpolation polynomial. The following are some timing statistics obtained using sage.math. When the results of previous computations are fed to {{{lagrange_polynomial}}} in order to produce better interpolation polynomials, we can gain an efficiency of up to 42%.  {{{# BEFORE# using the definition of Lagrange interpolation polynomialsage: R = PolynomialRing(QQ, 'x')sage: %timeit R.lagrange_polynomial([(0,1),(2,2),(3,-2),(-4,9)])1000 loops, best of 3: 1.71 ms per loopsage: R = PolynomialRing(GF(2**3,'a'), 'x')sage: a = R.base_ring().gen()sage: timeit("R.lagrange_polynomial([(a^2+a,a),(a,1),(a^2,a^2+a+1)])")625 loops, best of 3: 233 µs per loop# without using precomputed values to generate successively better interpolation polynomialssage: R = PolynomialRing(QQ, 'x')sage: timeit("R.lagrange_polynomial([(0,1),(2,2)])");625 loops, best of 3: 571 µs per loopsage: # add two more pointssage: timeit("R.lagrange_polynomial([(0,1),(2,2),(3,-2),(-4,9)])");125 loops, best of 3: 2.29 ms per loopsage: sage: R = PolynomialRing(GF(2**3,'a'), 'x')sage: a = R.base_ring().gen()sage: timeit("R.lagrange_polynomial([(a^2+a,a),(a,1)])")625 loops, best of 3: 76.1 µs per loopsage: # add another pointsage: timeit("R.lagrange_polynomial([(a^2+a,a),(a,1),(a^2,a^2+a+1)])")625 loops, best of 3: 229 µs per loopsage:sage: R = PolynomialRing(QQ, 'x')sage: points = [(random(), random()) for i in xrange(100)]sage: time R.lagrange_polynomial(points);CPU times: user 1.21 s, sys: 0.00 s, total: 1.21 sWall time: 1.21 ssage: # add three more pointssage: for i in xrange(3): points.append((random(), random()))....: sage: time R.lagrange_polynomial(points);CPU times: user 1.28 s, sys: 0.01 s, total: 1.29 sWall time: 1.29 ssage: # add another 100 pointssage: for i in xrange(100): points.append((random(), random()))....: sage: time R.lagrange_polynomial(points);CPU times: user 5.87 s, sys: 0.02 s, total: 5.89 sWall time: 5.89 s# AFTER# using the method of divided-differencesage: R = PolynomialRing(QQ, 'x')sage: %timeit R.lagrange_polynomial([(0,1),(2,2),(3,-2),(-4,9)])1000 loops, best of 3: 827 µs per loopsage: R = PolynomialRing(GF(2**3,'a'), 'x')sage: a = R.base_ring().gen()sage: timeit("R.lagrange_polynomial([(a^2+a,a),(a,1),(a^2,a^2+a+1)])")625 loops, best of 3: 111 µs per loop# using precomputed values to generate successively better interpolation polynomialssage: R = PolynomialRing(QQ, 'x')sage: timeit("R.lagrange_polynomial([(0,1),(2,2)], neville=True)");625 loops, best of 3: 332 µs per loopsage: p = R.lagrange_polynomial([(0,1),(2,2)], neville=True);sage: # add two more pointssage: timeit("R.lagrange_polynomial([(0,1),(2,2),(3,-2),(-4,9)], neville=True, previous_row=p)");625 loops, best of 3: 1.41 ms per loopsage:sage: R = PolynomialRing(GF(2**3,'a'), 'x')sage: a = R.base_ring().gen()sage: timeit("R.lagrange_polynomial([(a^2+a,a),(a,1)], neville=True)");625 loops, best of 3: 36.4 µs per loopsage: p = R.lagrange_polynomial([(a^2+a,a),(a,1)], neville=True);sage: # add another pointsage: timeit("R.lagrange_polynomial([(a^2+a,a),(a,1),(a^2,a^2+a+1)], neville=True, previous_row=p)");625 loops, best of 3: 131 µs per loopsage:sage: R = PolynomialRing(QQ, 'x')sage: points = [(random(), random()) for i in xrange(100)]sage: time R.lagrange_polynomial(points, neville=True);CPU times: user 1.26 s, sys: 0.00 s, total: 1.26 sWall time: 1.26 ssage: p = R.lagrange_polynomial(points, neville=True);sage: # add three more pointssage: for i in xrange(3): points.append((random(), random()))....: sage: time R.lagrange_polynomial(points, neville=True, previous_row=p);CPU times: user 0.09 s, sys: 0.00 s, total: 0.09 sWall time: 0.08 ssage: p = R.lagrange_polynomial(points, neville=True, previous_row=p)sage: # add another 100 pointssage: for i in xrange(100): points.append((random(), random()))....: sage: time R.lagrange_polynomial(points, neville=True, previous_row=p);CPU times: user 4.62 s, sys: 0.00 s, total: 4.62 sWall time: 4.62 s }}} Line 16: Line 151: * FIXME: summarize #5948 Line 19: Line 157: * FIXME: summarize #5732== Calculus == * FIXME: summarize #5404 Line 22: Line 169: * FIXME: summarize #6000 * FIXME: summarize #6167 * FIXME: summarize #6093 * FIXME: summarize #6050 * FIXME: summarize #5931 * FIXME: summarize #5925 Line 25: Line 185: * FIXME: summarize #6120 Line 34: Line 197: * FIXME: summarize #6184 * FIXME: summarize #5599 Line 40: Line 208: * FIXME: summarize #6208 Line 46: Line 217: * FIXME: summarize #5967 * FIXME: summarize #5483 * FIXME: summarize #6139 Line 49: Line 227: * FIXME: summarize #5995== Notebook == * FIXME: summarize #4575 * FIXME: summarize #5895 Line 52: Line 241: * FIXME: summarize #133 * FIXME: summarize #6021 * FIXME: summarize #6206== Numerical == * FIXME: summarize #5827 Line 55: Line 257: * FIXME: summarize #5840 * FIXME: summarize #6173 * FIXME: summarize #5817 * FIXME: summarize #6156 * FIXME: summarize #6169 * FIXME: summarize #6209 * FIXME: summarize #6219 Line 64: Line 281: * FIXME: summarize #6144 * FIXME: summarize #6194 Line 65: Line 287: * FIXME: summarize #6141

# Sage 4.0.1 Release Tour

Sage 4.0.1 was released on FIXME. For the official, comprehensive release note, please refer to FIXME. A nicely formatted version of this release tour can be found at FIXME. The following points are some of the foci of this release:

## Algebra

• Factoring rational functions (Soroosh Yazdani) -- New method factor() in the class FractionFieldElement of sage/rings/fraction_field_element.pyx to return the factorization of self over the base ring. Here's an example for working with this new method:

```sage: K.<x> = QQ["x"]
sage: f = (x^3 + x) / (x-3)
sage: f.factor()
(x - 3)^-1 * x * (x^2 + 1)```
• Faster basis_matrix() for ambient modules (John Cremona) -- The speed-up can be up to 376x faster than previously. The following timing statistics were obtained using the machine sage.math:

```# BEFORE

sage: K = FreeModule(ZZ, 2000)
sage: %time I = K.basis_matrix()
CPU times: user 292.74 s, sys: 20.11 s, total: 312.85 s
Wall time: 312.90 s

# AFTER

sage: K = FreeModule(ZZ, 2000)
sage: %time I = K.basis_matrix()
CPU times: user 0.41 s, sys: 0.43 s, total: 0.84 s
Wall time: 0.83 s```
• Optimize the construction of Lagrange interpolation polynomials (Minh Van Nguyen) -- Rewrite the method lagrange_polynomial() in the class PolynomialRing_field of sage/rings/polynomial/polynomial_ring.py for generating the n-th Lagrange interpolation polynomial. The method now provides two new options:

• algorithm --- (default: divided_difference) If algorithm="divided_difference", then use the method of divided difference. If algorithm="neville", then use a variant of Neville's method to recursively generate the n-th Lagrange interpolation polynomial. This adaptation of Neville's method is more memory efficient than the original Neville's method, since the former doesn't generate the full Neville table resulting from Neville's recursive procedure. Instead the adaptation only keeps track of the current and previous rows of the said table.

• previous_row --- (default: None) This is only relevant if used together with algorithm="neville". Here "previous row" refers to the last row in the Neville table that was obtained from a previous computation of an n-th Lagrange interpolation polynomial using Neville's method. If the last row is provided, then use a memory efficient variant of Neville's method to recursively generate a better interpolation polynomial from the results of previous computation.

There's also the new method divided_difference() to compute the Newton divided-difference coefficients of the n-th Lagrange interpolation polynomial. The following are some timing statistics obtained using sage.math. When the results of previous computations are fed to lagrange_polynomial in order to produce better interpolation polynomials, we can gain an efficiency of up to 42%.

```# BEFORE

# using the definition of Lagrange interpolation polynomial
sage: R = PolynomialRing(QQ, 'x')
sage: %timeit R.lagrange_polynomial([(0,1),(2,2),(3,-2),(-4,9)])
1000 loops, best of 3: 1.71 ms per loop
sage: R = PolynomialRing(GF(2**3,'a'), 'x')
sage: a = R.base_ring().gen()
sage: timeit("R.lagrange_polynomial([(a^2+a,a),(a,1),(a^2,a^2+a+1)])")
625 loops, best of 3: 233 µs per loop

# without using precomputed values to generate successively better interpolation polynomials

sage: R = PolynomialRing(QQ, 'x')
sage: timeit("R.lagrange_polynomial([(0,1),(2,2)])");
625 loops, best of 3: 571 µs per loop
sage: # add two more points
sage: timeit("R.lagrange_polynomial([(0,1),(2,2),(3,-2),(-4,9)])");
125 loops, best of 3: 2.29 ms per loop
sage:
sage: R = PolynomialRing(GF(2**3,'a'), 'x')
sage: a = R.base_ring().gen()
sage: timeit("R.lagrange_polynomial([(a^2+a,a),(a,1)])")
625 loops, best of 3: 76.1 µs per loop
sage: timeit("R.lagrange_polynomial([(a^2+a,a),(a,1),(a^2,a^2+a+1)])")
625 loops, best of 3: 229 µs per loop
sage:
sage: R = PolynomialRing(QQ, 'x')
sage: points = [(random(), random()) for i in xrange(100)]
sage: time R.lagrange_polynomial(points);
CPU times: user 1.21 s, sys: 0.00 s, total: 1.21 s
Wall time: 1.21 s
sage: # add three more points
sage: for i in xrange(3): points.append((random(), random()))
....:
sage: time R.lagrange_polynomial(points);
CPU times: user 1.28 s, sys: 0.01 s, total: 1.29 s
Wall time: 1.29 s
sage: # add another 100 points
sage: for i in xrange(100): points.append((random(), random()))
....:
sage: time R.lagrange_polynomial(points);
CPU times: user 5.87 s, sys: 0.02 s, total: 5.89 s
Wall time: 5.89 s

# AFTER

# using the method of divided-difference
sage: R = PolynomialRing(QQ, 'x')
sage: %timeit R.lagrange_polynomial([(0,1),(2,2),(3,-2),(-4,9)])
1000 loops, best of 3: 827 µs per loop
sage: R = PolynomialRing(GF(2**3,'a'), 'x')
sage: a = R.base_ring().gen()
sage: timeit("R.lagrange_polynomial([(a^2+a,a),(a,1),(a^2,a^2+a+1)])")
625 loops, best of 3: 111 µs per loop

# using precomputed values to generate successively better interpolation polynomials

sage: R = PolynomialRing(QQ, 'x')
sage: timeit("R.lagrange_polynomial([(0,1),(2,2)], neville=True)");
625 loops, best of 3: 332 µs per loop
sage: p = R.lagrange_polynomial([(0,1),(2,2)], neville=True);
sage: # add two more points
sage: timeit("R.lagrange_polynomial([(0,1),(2,2),(3,-2),(-4,9)], neville=True, previous_row=p)");
625 loops, best of 3: 1.41 ms per loop
sage:
sage: R = PolynomialRing(GF(2**3,'a'), 'x')
sage: a = R.base_ring().gen()
sage: timeit("R.lagrange_polynomial([(a^2+a,a),(a,1)], neville=True)");
625 loops, best of 3: 36.4 µs per loop
sage: p = R.lagrange_polynomial([(a^2+a,a),(a,1)], neville=True);
sage: timeit("R.lagrange_polynomial([(a^2+a,a),(a,1),(a^2,a^2+a+1)], neville=True, previous_row=p)");
625 loops, best of 3: 131 µs per loop
sage:
sage: R = PolynomialRing(QQ, 'x')
sage: points = [(random(), random()) for i in xrange(100)]
sage: time R.lagrange_polynomial(points, neville=True);
CPU times: user 1.26 s, sys: 0.00 s, total: 1.26 s
Wall time: 1.26 s
sage: p = R.lagrange_polynomial(points, neville=True);
sage: # add three more points
sage: for i in xrange(3): points.append((random(), random()))
....:
sage: time R.lagrange_polynomial(points, neville=True, previous_row=p);
CPU times: user 0.09 s, sys: 0.00 s, total: 0.09 s
Wall time: 0.08 s
sage: p = R.lagrange_polynomial(points, neville=True, previous_row=p)
sage: # add another 100 points
sage: for i in xrange(100): points.append((random(), random()))
....:
sage: time R.lagrange_polynomial(points, neville=True, previous_row=p);
CPU times: user 4.62 s, sys: 0.00 s, total: 4.62 s
Wall time: 4.62 s```

## Algebraic Geometry

• FIXME: summarize #5948

## Basic Arithmetic

• FIXME: summarize #5732

## Calculus

• FIXME: summarize #5404

## Combinatorics

• FIXME: summarize #6000
• FIXME: summarize #6167
• FIXME: summarize #6093
• FIXME: summarize #6050
• FIXME: summarize #5931
• FIXME: summarize #5925

## Commutative Algebra

• FIXME: summarize #6120

## Graphics

• FIXME: summarize #6184
• FIXME: summarize #5599

## Interfaces

• FIXME: summarize #6208

## Miscellaneous

• FIXME: summarize #5967
• FIXME: summarize #5483
• FIXME: summarize #6139

## Modular Forms

• FIXME: summarize #5995

## Notebook

• FIXME: summarize #4575
• FIXME: summarize #5895

## Number Theory

• FIXME: summarize #133
• FIXME: summarize #6021
• FIXME: summarize #6206

## Numerical

• FIXME: summarize #5827

## Packages

• FIXME: summarize #5840
• FIXME: summarize #6173
• FIXME: summarize #5817
• FIXME: summarize #6156
• FIXME: summarize #6169
• FIXME: summarize #6209
• FIXME: summarize #6219