Spaces:
Running
Running
| from sympy import ZZ, QQ, ZZ_I, EX, Matrix, eye, zeros, symbols | |
| from sympy.polys.matrices import DM, DomainMatrix | |
| from sympy.polys.matrices.dense import ddm_irref_den, ddm_irref | |
| from sympy.polys.matrices.ddm import DDM | |
| from sympy.polys.matrices.sdm import SDM, sdm_irref, sdm_rref_den | |
| import pytest | |
| # | |
| # The dense and sparse implementations of rref_den are ddm_irref_den and | |
| # sdm_irref_den. These can give results that differ by some factor and also | |
| # give different results if the order of the rows is changed. The tests below | |
| # show all results on lowest terms as should be returned by cancel_denom. | |
| # | |
| # The EX domain is also a case where the dense and sparse implementations | |
| # can give results in different forms: the results should be equivalent but | |
| # are not canonical because EX does not have a canonical form. | |
| # | |
| a, b, c, d = symbols('a, b, c, d') | |
| qq_large_1 = DM([ | |
| [ (1,2), (1,3), (1,5), (1,7), (1,11), (1,13), (1,17), (1,19), (1,23), (1,29), (1,31)], | |
| [ (1,37), (1,41), (1,43), (1,47), (1,53), (1,59), (1,61), (1,67), (1,71), (1,73), (1,79)], | |
| [ (1,83), (1,89), (1,97),(1,101),(1,103),(1,107),(1,109),(1,113),(1,127),(1,131),(1,137)], | |
| [(1,139),(1,149),(1,151),(1,157),(1,163),(1,167),(1,173),(1,179),(1,181),(1,191),(1,193)], | |
| [(1,197),(1,199),(1,211),(1,223),(1,227),(1,229),(1,233),(1,239),(1,241),(1,251),(1,257)], | |
| [(1,263),(1,269),(1,271),(1,277),(1,281),(1,283),(1,293),(1,307),(1,311),(1,313),(1,317)], | |
| [(1,331),(1,337),(1,347),(1,349),(1,353),(1,359),(1,367),(1,373),(1,379),(1,383),(1,389)], | |
| [(1,397),(1,401),(1,409),(1,419),(1,421),(1,431),(1,433),(1,439),(1,443),(1,449),(1,457)], | |
| [(1,461),(1,463),(1,467),(1,479),(1,487),(1,491),(1,499),(1,503),(1,509),(1,521),(1,523)], | |
| [(1,541),(1,547),(1,557),(1,563),(1,569),(1,571),(1,577),(1,587),(1,593),(1,599),(1,601)], | |
| [(1,607),(1,613),(1,617),(1,619),(1,631),(1,641),(1,643),(1,647),(1,653),(1,659),(1,661)]], | |
| QQ) | |
| qq_large_2 = qq_large_1 + 10**100 * DomainMatrix.eye(11, QQ) | |
| RREF_EXAMPLES = [ | |
| ( | |
| 'zz_1', | |
| DM([[1, 2, 3]], ZZ), | |
| DM([[1, 2, 3]], ZZ), | |
| ZZ(1), | |
| ), | |
| ( | |
| 'zz_2', | |
| DomainMatrix([], (0, 0), ZZ), | |
| DomainMatrix([], (0, 0), ZZ), | |
| ZZ(1), | |
| ), | |
| ( | |
| 'zz_3', | |
| DM([[1, 2], | |
| [3, 4]], ZZ), | |
| DM([[1, 0], | |
| [0, 1]], ZZ), | |
| ZZ(1), | |
| ), | |
| ( | |
| 'zz_4', | |
| DM([[1, 0], | |
| [3, 4]], ZZ), | |
| DM([[1, 0], | |
| [0, 1]], ZZ), | |
| ZZ(1), | |
| ), | |
| ( | |
| 'zz_5', | |
| DM([[0, 2], | |
| [3, 4]], ZZ), | |
| DM([[1, 0], | |
| [0, 1]], ZZ), | |
| ZZ(1), | |
| ), | |
| ( | |
| 'zz_6', | |
| DM([[1, 2, 3], | |
| [4, 5, 6], | |
| [7, 8, 9]], ZZ), | |
| DM([[1, 0, -1], | |
| [0, 1, 2], | |
| [0, 0, 0]], ZZ), | |
| ZZ(1), | |
| ), | |
| ( | |
| 'zz_7', | |
| DM([[0, 0, 0], | |
| [0, 0, 0], | |
| [1, 0, 0]], ZZ), | |
| DM([[1, 0, 0], | |
| [0, 0, 0], | |
| [0, 0, 0]], ZZ), | |
| ZZ(1), | |
| ), | |
| ( | |
| 'zz_8', | |
| DM([[0, 0, 0], | |
| [0, 0, 0], | |
| [0, 0, 0]], ZZ), | |
| DM([[0, 0, 0], | |
| [0, 0, 0], | |
| [0, 0, 0]], ZZ), | |
| ZZ(1), | |
| ), | |
| ( | |
| 'zz_9', | |
| DM([[1, 1, 0], | |
| [0, 0, 2], | |
| [0, 0, 0]], ZZ), | |
| DM([[1, 1, 0], | |
| [0, 0, 1], | |
| [0, 0, 0]], ZZ), | |
| ZZ(1), | |
| ), | |
| ( | |
| 'zz_10', | |
| DM([[2, 2, 0], | |
| [0, 0, 2], | |
| [0, 0, 0]], ZZ), | |
| DM([[1, 1, 0], | |
| [0, 0, 1], | |
| [0, 0, 0]], ZZ), | |
| ZZ(1), | |
| ), | |
| ( | |
| 'zz_11', | |
| DM([[2, 2, 0], | |
| [0, 2, 2], | |
| [0, 0, 2]], ZZ), | |
| DM([[1, 0, 0], | |
| [0, 1, 0], | |
| [0, 0, 1]], ZZ), | |
| ZZ(1), | |
| ), | |
| ( | |
| 'zz_12', | |
| DM([[ 1, 2, 3], | |
| [ 4, 5, 6], | |
| [ 7, 8, 9], | |
| [10, 11, 12]], ZZ), | |
| DM([[1, 0, -1], | |
| [0, 1, 2], | |
| [0, 0, 0], | |
| [0, 0, 0]], ZZ), | |
| ZZ(1), | |
| ), | |
| ( | |
| 'zz_13', | |
| DM([[ 1, 2, 3], | |
| [ 4, 5, 6], | |
| [ 7, 8, 9], | |
| [10, 11, 13]], ZZ), | |
| DM([[ 1, 0, 0], | |
| [ 0, 1, 0], | |
| [ 0, 0, 1], | |
| [ 0, 0, 0]], ZZ), | |
| ZZ(1), | |
| ), | |
| ( | |
| 'zz_14', | |
| DM([[1, 2, 4, 3], | |
| [4, 5, 10, 6], | |
| [7, 8, 16, 9]], ZZ), | |
| DM([[1, 0, 0, -1], | |
| [0, 1, 2, 2], | |
| [0, 0, 0, 0]], ZZ), | |
| ZZ(1), | |
| ), | |
| ( | |
| 'zz_15', | |
| DM([[1, 2, 4, 3], | |
| [4, 5, 10, 6], | |
| [7, 8, 17, 9]], ZZ), | |
| DM([[1, 0, 0, -1], | |
| [0, 1, 0, 2], | |
| [0, 0, 1, 0]], ZZ), | |
| ZZ(1), | |
| ), | |
| ( | |
| 'zz_16', | |
| DM([[1, 2, 0, 1], | |
| [1, 1, 9, 0]], ZZ), | |
| DM([[1, 0, 18, -1], | |
| [0, 1, -9, 1]], ZZ), | |
| ZZ(1), | |
| ), | |
| ( | |
| 'zz_17', | |
| DM([[1, 1, 1], | |
| [1, 2, 2]], ZZ), | |
| DM([[1, 0, 0], | |
| [0, 1, 1]], ZZ), | |
| ZZ(1), | |
| ), | |
| ( | |
| # Here the sparse implementation and dense implementation give very | |
| # different denominators: 4061232 and -1765176. | |
| 'zz_18', | |
| DM([[94, 24, 0, 27, 0], | |
| [79, 0, 0, 0, 0], | |
| [85, 16, 71, 81, 0], | |
| [ 0, 0, 72, 77, 0], | |
| [21, 0, 34, 0, 0]], ZZ), | |
| DM([[ 1, 0, 0, 0, 0], | |
| [ 0, 1, 0, 0, 0], | |
| [ 0, 0, 1, 0, 0], | |
| [ 0, 0, 0, 1, 0], | |
| [ 0, 0, 0, 0, 0]], ZZ), | |
| ZZ(1), | |
| ), | |
| ( | |
| # Let's have a denominator that cannot be cancelled. | |
| 'zz_19', | |
| DM([[1, 2, 4], | |
| [4, 5, 6]], ZZ), | |
| DM([[3, 0, -8], | |
| [0, 3, 10]], ZZ), | |
| ZZ(3), | |
| ), | |
| ( | |
| 'zz_20', | |
| DM([[0, 0, 0, 0, 0], | |
| [0, 0, 0, 0, 0], | |
| [0, 0, 0, 0, 4]], ZZ), | |
| DM([[0, 0, 0, 0, 1], | |
| [0, 0, 0, 0, 0], | |
| [0, 0, 0, 0, 0]], ZZ), | |
| ZZ(1), | |
| ), | |
| ( | |
| 'zz_21', | |
| DM([[0, 0, 0, 0, 0, 1, 0, 0, 0, 0], | |
| [1, 0, 0, 0, 0, 0, 1, 0, 0, 0], | |
| [0, 1, 0, 0, 0, 0, 0, 1, 0, 0], | |
| [0, 0, 0, 1, 0, 0, 0, 0, 1, 0], | |
| [0, 0, 0, 0, 1, 0, 0, 0, 0, 1]], ZZ), | |
| DM([[1, 0, 0, 0, 0, 0, 1, 0, 0, 0], | |
| [0, 1, 0, 0, 0, 0, 0, 1, 0, 0], | |
| [0, 0, 0, 1, 0, 0, 0, 0, 1, 0], | |
| [0, 0, 0, 0, 1, 0, 0, 0, 0, 1], | |
| [0, 0, 0, 0, 0, 1, 0, 0, 0, 0]], ZZ), | |
| ZZ(1), | |
| ), | |
| ( | |
| 'zz_22', | |
| DM([[1, 1, 1, 0, 1], | |
| [1, 1, 0, 1, 0], | |
| [1, 0, 1, 0, 1], | |
| [1, 1, 0, 1, 0], | |
| [1, 0, 0, 0, 0]], ZZ), | |
| DM([[1, 0, 0, 0, 0], | |
| [0, 1, 0, 0, 0], | |
| [0, 0, 1, 0, 1], | |
| [0, 0, 0, 1, 0], | |
| [0, 0, 0, 0, 0]], ZZ), | |
| ZZ(1), | |
| ), | |
| ( | |
| 'zz_large_1', | |
| DM([ | |
| [ 0, 0, 0, 81, 0, 0, 75, 0, 0, 0, 0, 0, 0, 27, 0, 0, 0, 0, 0, 0], | |
| [ 0, 0, 0, 0, 0, 86, 0, 92, 79, 54, 0, 7, 0, 0, 0, 0, 79, 0, 0, 0], | |
| [89, 54, 81, 0, 0, 20, 0, 0, 0, 0, 0, 0, 51, 0, 94, 0, 0, 77, 0, 0], | |
| [ 0, 0, 0, 96, 0, 0, 0, 0, 0, 0, 0, 0, 48, 29, 0, 0, 5, 0, 32, 0], | |
| [ 0, 70, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 60, 0, 0, 0, 11], | |
| [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 37, 0, 43, 0, 0], | |
| [ 0, 0, 0, 0, 0, 38, 91, 0, 0, 0, 0, 38, 0, 0, 0, 0, 0, 26, 0, 0], | |
| [69, 0, 0, 0, 0, 0, 94, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 55], | |
| [ 0, 13, 18, 49, 49, 88, 0, 0, 35, 54, 0, 0, 51, 0, 0, 0, 0, 0, 0, 87], | |
| [ 0, 0, 0, 0, 31, 0, 40, 0, 0, 0, 0, 0, 0, 50, 0, 0, 0, 0, 88, 0], | |
| [ 0, 0, 0, 0, 0, 0, 0, 0, 98, 0, 0, 0, 15, 53, 0, 92, 0, 0, 0, 0], | |
| [ 0, 0, 0, 95, 0, 0, 0, 36, 0, 0, 0, 0, 0, 72, 0, 0, 0, 0, 73, 19], | |
| [ 0, 65, 14, 96, 0, 0, 0, 0, 0, 0, 0, 0, 0, 90, 0, 0, 0, 34, 0, 0], | |
| [ 0, 0, 0, 16, 39, 44, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 51, 0, 0], | |
| [ 0, 17, 0, 0, 0, 99, 84, 13, 50, 84, 0, 0, 0, 0, 95, 0, 43, 33, 20, 0], | |
| [79, 0, 17, 52, 99, 12, 69, 0, 98, 0, 68, 0, 0, 0, 0, 0, 0, 0, 0, 0], | |
| [ 0, 0, 0, 82, 0, 44, 0, 0, 0, 97, 0, 0, 0, 0, 0, 10, 0, 0, 31, 0], | |
| [ 0, 0, 21, 0, 67, 0, 0, 0, 0, 0, 4, 0, 50, 0, 0, 0, 33, 0, 0, 0], | |
| [ 0, 0, 0, 0, 9, 42, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8], | |
| [ 0, 77, 0, 0, 0, 0, 0, 0, 0, 0, 34, 93, 0, 0, 0, 0, 47, 0, 0, 0]], | |
| ZZ), | |
| DM([[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], | |
| [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], | |
| [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], | |
| [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], | |
| [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], | |
| [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], | |
| [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], | |
| [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], | |
| [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], | |
| [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], | |
| [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0], | |
| [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0], | |
| [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0], | |
| [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0], | |
| [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0], | |
| [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0], | |
| [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0], | |
| [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0], | |
| [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0], | |
| [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]], ZZ), | |
| ZZ(1), | |
| ), | |
| ( | |
| 'zz_large_2', | |
| DM([ | |
| [ 0, 0, 0, 0, 50, 0, 6, 81, 0, 1, 86, 0, 0, 98, 82, 94, 4, 0, 0, 29], | |
| [ 0, 44, 43, 0, 62, 0, 0, 0, 60, 0, 0, 0, 0, 71, 9, 0, 57, 41, 0, 93], | |
| [ 0, 0, 28, 0, 74, 89, 42, 0, 28, 0, 6, 0, 0, 0, 44, 0, 0, 0, 77, 19], | |
| [ 0, 21, 82, 0, 30, 88, 0, 89, 68, 0, 0, 0, 79, 41, 0, 0, 99, 0, 0, 0], | |
| [31, 0, 0, 0, 19, 64, 0, 0, 79, 0, 5, 0, 72, 10, 60, 32, 64, 59, 0, 24], | |
| [ 0, 0, 0, 0, 0, 57, 0, 94, 0, 83, 20, 0, 0, 9, 31, 0, 49, 26, 58, 0], | |
| [ 0, 65, 56, 31, 64, 0, 0, 0, 0, 0, 0, 52, 85, 0, 0, 0, 0, 51, 0, 0], | |
| [ 0, 35, 0, 0, 0, 69, 0, 0, 64, 0, 0, 0, 0, 70, 0, 0, 90, 0, 75, 76], | |
| [69, 7, 0, 90, 0, 0, 84, 0, 47, 69, 19, 20, 42, 0, 0, 32, 71, 35, 0, 0], | |
| [39, 0, 90, 0, 0, 4, 85, 0, 0, 55, 0, 0, 0, 35, 67, 40, 0, 40, 0, 77], | |
| [98, 63, 0, 71, 0, 50, 0, 2, 61, 0, 38, 0, 0, 0, 0, 75, 0, 40, 33, 56], | |
| [ 0, 73, 0, 64, 0, 38, 0, 35, 61, 0, 0, 52, 0, 7, 0, 51, 0, 0, 0, 34], | |
| [ 0, 0, 28, 0, 34, 5, 63, 45, 14, 42, 60, 16, 76, 54, 99, 0, 28, 30, 0, 0], | |
| [58, 37, 14, 0, 0, 0, 94, 0, 0, 90, 0, 0, 0, 0, 0, 0, 0, 8, 90, 53], | |
| [86, 74, 94, 0, 49, 10, 60, 0, 40, 18, 0, 0, 0, 31, 60, 24, 0, 1, 0, 29], | |
| [53, 0, 0, 97, 0, 0, 58, 0, 0, 39, 44, 47, 0, 0, 0, 12, 50, 0, 0, 11], | |
| [ 4, 0, 92, 10, 28, 0, 0, 89, 0, 0, 18, 54, 23, 39, 0, 2, 0, 48, 0, 92], | |
| [ 0, 0, 90, 77, 95, 33, 0, 0, 49, 22, 39, 0, 0, 0, 0, 0, 0, 40, 0, 0], | |
| [96, 0, 0, 0, 0, 38, 86, 0, 22, 76, 0, 0, 0, 0, 83, 88, 95, 65, 72, 0], | |
| [81, 65, 0, 4, 60, 0, 19, 0, 0, 68, 0, 0, 89, 0, 67, 22, 0, 0, 55, 33]], | |
| ZZ), | |
| DM([ | |
| [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], | |
| [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], | |
| [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], | |
| [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], | |
| [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], | |
| [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], | |
| [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], | |
| [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], | |
| [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], | |
| [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], | |
| [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0], | |
| [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0], | |
| [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0], | |
| [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0], | |
| [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0], | |
| [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0], | |
| [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0], | |
| [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0], | |
| [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0], | |
| [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]], | |
| ZZ), | |
| ZZ(1), | |
| ), | |
| ( | |
| 'zz_large_3', | |
| DM([ | |
| [62,35,89,58,22,47,30,28,52,72,17,56,80,26,64,21,10,35,24,42,96,32,23,50,92,37,76,94,63,66], | |
| [20,47,96,34,10,98,19,6,29,2,19,92,61,94,38,41,32,9,5,94,31,58,27,41,72,85,61,62,40,46], | |
| [69,26,35,68,25,52,94,13,38,65,81,10,29,15,5,4,13,99,85,0,80,51,60,60,26,77,85,2,87,25], | |
| [99,58,69,15,52,12,18,7,27,56,12,54,21,92,38,95,33,83,28,1,44,8,29,84,92,12,2,25,46,46], | |
| [93,13,55,48,35,87,24,40,23,35,25,32,0,19,0,85,4,79,26,11,46,75,7,96,76,11,7,57,99,75], | |
| [128,85,26,51,161,173,77,78,85,103,123,58,91,147,38,91,161,36,123,81,102,25,75,59,17,150,112,65,77,143], | |
| [15,59,61,82,12,83,34,8,94,71,66,7,91,21,48,69,26,12,64,38,97,87,38,15,51,33,93,43,66,89], | |
| [74,74,53,39,69,90,41,80,32,66,40,83,87,87,61,38,12,80,24,49,37,90,19,33,56,0,46,57,56,60], | |
| [82,11,0,25,56,58,39,49,92,93,80,38,19,62,33,85,19,61,14,30,45,91,97,34,97,53,92,28,33,43], | |
| [83,79,41,16,95,35,53,45,26,4,71,76,61,69,69,72,87,92,59,72,54,11,22,83,8,57,77,55,19,22], | |
| [49,34,13,31,72,77,52,70,46,41,37,6,42,66,35,6,75,33,62,57,30,14,26,31,9,95,89,13,12,90], | |
| [29,3,49,30,51,32,77,41,38,50,16,1,87,81,93,88,58,91,83,0,38,67,29,64,60,84,5,60,23,28], | |
| [79,51,13,20,89,96,25,8,39,62,86,52,49,81,3,85,86,3,61,24,72,11,49,28,8,55,23,52,65,53], | |
| [96,86,73,20,41,20,37,18,10,61,85,24,40,83,69,41,4,92,23,99,64,33,18,36,32,56,60,98,39,24], | |
| [32,62,47,80,51,66,17,1,9,30,65,75,75,88,99,92,64,53,53,86,38,51,41,14,35,18,39,25,26,32], | |
| [39,21,8,16,33,6,35,85,75,62,43,34,18,68,71,28,32,18,12,0,81,53,1,99,3,5,45,99,35,33], | |
| [19,95,89,45,75,94,92,5,84,93,34,17,50,56,79,98,68,82,65,81,51,90,5,95,33,71,46,61,14,7], | |
| [53,92,8,49,67,84,21,79,49,95,66,48,36,14,62,97,26,45,58,31,83,48,11,89,67,72,91,34,56,89], | |
| [56,76,99,92,40,8,0,16,15,48,35,72,91,46,81,14,86,60,51,7,33,12,53,78,48,21,3,89,15,79], | |
| [81,43,33,49,6,49,36,32,57,74,87,91,17,37,31,17,67,1,40,38,69,8,3,48,59,37,64,97,11,3], | |
| [98,48,77,16,2,48,57,38,63,59,79,35,16,71,60,86,71,41,14,76,80,97,77,69,4,58,22,55,26,73], | |
| [80,47,78,44,31,48,47,29,29,62,19,21,17,24,19,3,53,93,97,57,13,54,12,10,77,66,60,75,32,21], | |
| [86,63,2,13,71,38,86,23,18,15,91,65,77,65,9,92,50,0,17,42,99,80,99,27,10,99,92,9,87,84], | |
| [66,27,72,13,13,15,72,75,39,3,14,71,15,68,10,19,49,54,11,29,47,20,63,13,97,47,24,62,16,96], | |
| [42,63,83,60,49,68,9,53,75,87,40,25,12,63,0,12,0,95,46,46,55,25,89,1,51,1,1,96,80,52], | |
| [35,9,97,13,86,39,66,48,41,57,23,38,11,9,35,72,88,13,41,60,10,64,71,23,1,5,23,57,6,19], | |
| [70,61,5,50,72,60,77,13,41,94,1,45,52,22,99,47,27,18,99,42,16,48,26,9,88,77,10,94,11,92], | |
| [55,68,58,2,72,56,81,52,79,37,1,40,21,46,27,60,37,13,97,42,85,98,69,60,76,44,42,46,29,73], | |
| [73,0,43,17,89,97,45,2,68,14,55,60,95,2,74,85,88,68,93,76,38,76,2,51,45,76,50,79,56,18], | |
| [72,58,41,39,24,80,23,79,44,7,98,75,30,6,85,60,20,58,77,71,90,51,38,80,30,15,33,10,82,8]], | |
| ZZ), | |
| Matrix([ | |
| [eye(29) * 2028539767964472550625641331179545072876560857886207583101, | |
| Matrix([ 4260575808093245475167216057435155595594339172099000182569, | |
| 169148395880755256182802335904188369274227936894862744452, | |
| 4915975976683942569102447281579134986891620721539038348914, | |
| 6113916866367364958834844982578214901958429746875633283248, | |
| 5585689617819894460378537031623265659753379011388162534838, | |
| 359776822829880747716695359574308645968094838905181892423, | |
| -2800926112141776386671436511182421432449325232461665113305, | |
| 941642292388230001722444876624818265766384442910688463158, | |
| 3648811843256146649321864698600908938933015862008642023935, | |
| -4104526163246702252932955226754097174212129127510547462419, | |
| -704814955438106792441896903238080197619233342348191408078, | |
| 1640882266829725529929398131287244562048075707575030019335, | |
| -4068330845192910563212155694231438198040299927120544468520, | |
| 136589038308366497790495711534532612862715724187671166593, | |
| 2544937011460702462290799932536905731142196510605191645593, | |
| 755591839174293940486133926192300657264122907519174116472, | |
| -3683838489869297144348089243628436188645897133242795965021, | |
| -522207137101161299969706310062775465103537953077871128403, | |
| -2260451796032703984456606059649402832441331339246756656334, | |
| -6476809325293587953616004856993300606040336446656916663680, | |
| 3521944238996782387785653800944972787867472610035040989081, | |
| 2270762115788407950241944504104975551914297395787473242379, | |
| -3259947194628712441902262570532921252128444706733549251156, | |
| -5624569821491886970999097239695637132075823246850431083557, | |
| -3262698255682055804320585332902837076064075936601504555698, | |
| 5786719943788937667411185880136324396357603606944869545501, | |
| -955257841973865996077323863289453200904051299086000660036, | |
| -1294235552446355326174641248209752679127075717918392702116, | |
| -3718353510747301598130831152458342785269166356215331448279, | |
| ]),], | |
| [zeros(1, 29), zeros(1, 1)], | |
| ]).to_DM().to_dense(), | |
| ZZ(2028539767964472550625641331179545072876560857886207583101), | |
| ), | |
| ( | |
| 'qq_1', | |
| DM([[(1,2), 0], [0, 2]], QQ), | |
| DM([[1, 0], [0, 1]], QQ), | |
| QQ(1), | |
| ), | |
| ( | |
| # Standard square case | |
| 'qq_2', | |
| DM([[0, 1], | |
| [1, 1]], QQ), | |
| DM([[1, 0], | |
| [0, 1]], QQ), | |
| QQ(1), | |
| ), | |
| ( | |
| # m < n case | |
| 'qq_3', | |
| DM([[1, 2, 1], | |
| [3, 4, 1]], QQ), | |
| DM([[1, 0, -1], | |
| [0, 1, 1]], QQ), | |
| QQ(1), | |
| ), | |
| ( | |
| # same m < n but reversed | |
| 'qq_4', | |
| DM([[3, 4, 1], | |
| [1, 2, 1]], QQ), | |
| DM([[1, 0, -1], | |
| [0, 1, 1]], QQ), | |
| QQ(1), | |
| ), | |
| ( | |
| # m > n case | |
| 'qq_5', | |
| DM([[1, 0], | |
| [1, 3], | |
| [0, 1]], QQ), | |
| DM([[1, 0], | |
| [0, 1], | |
| [0, 0]], QQ), | |
| QQ(1), | |
| ), | |
| ( | |
| # Example with missing pivot | |
| 'qq_6', | |
| DM([[1, 0, 1], | |
| [3, 0, 1]], QQ), | |
| DM([[1, 0, 0], | |
| [0, 0, 1]], QQ), | |
| QQ(1), | |
| ), | |
| ( | |
| # This is intended to trigger the threshold where we give up on | |
| # clearing denominators. | |
| 'qq_large_1', | |
| qq_large_1, | |
| DomainMatrix.eye(11, QQ).to_dense(), | |
| QQ(1), | |
| ), | |
| ( | |
| # This is intended to trigger the threshold where we use rref_den over | |
| # QQ. | |
| 'qq_large_2', | |
| qq_large_2, | |
| DomainMatrix.eye(11, QQ).to_dense(), | |
| QQ(1), | |
| ), | |
| ( | |
| # Example with missing pivot and no replacement | |
| # This example is just enough to show a different result from the dense | |
| # and sparse versions of the algorithm: | |
| # | |
| # >>> A = Matrix([[0, 1], [0, 2], [1, 0]]) | |
| # >>> A.to_DM().to_sparse().rref_den()[0].to_Matrix() | |
| # Matrix([ | |
| # [1, 0], | |
| # [0, 1], | |
| # [0, 0]]) | |
| # >>> A.to_DM().to_dense().rref_den()[0].to_Matrix() | |
| # Matrix([ | |
| # [2, 0], | |
| # [0, 2], | |
| # [0, 0]]) | |
| # | |
| 'qq_7', | |
| DM([[0, 1], | |
| [0, 2], | |
| [1, 0]], QQ), | |
| DM([[1, 0], | |
| [0, 1], | |
| [0, 0]], QQ), | |
| QQ(1), | |
| ), | |
| ( | |
| # Gaussian integers | |
| 'zz_i_1', | |
| DM([[(0,1), 1, 1], | |
| [ 1, 1, 1]], ZZ_I), | |
| DM([[1, 0, 0], | |
| [0, 1, 1]], ZZ_I), | |
| ZZ_I(1), | |
| ), | |
| ( | |
| # EX: test_issue_23718 | |
| 'EX_1', | |
| DM([ | |
| [a, b, 1], | |
| [c, d, 1]], EX), | |
| DM([[a*d - b*c, 0, -b + d], | |
| [ 0, a*d - b*c, a - c]], EX), | |
| EX(a*d - b*c), | |
| ), | |
| ] | |
| def _to_DM(A, ans): | |
| """Convert the answer to DomainMatrix.""" | |
| if isinstance(A, DomainMatrix): | |
| return A.to_dense() | |
| elif isinstance(A, Matrix): | |
| return A.to_DM(ans.domain).to_dense() | |
| if not (hasattr(A, 'shape') and hasattr(A, 'domain')): | |
| shape, domain = ans.shape, ans.domain | |
| else: | |
| shape, domain = A.shape, A.domain | |
| if isinstance(A, (DDM, list)): | |
| return DomainMatrix(list(A), shape, domain).to_dense() | |
| elif isinstance(A, (SDM, dict)): | |
| return DomainMatrix(dict(A), shape, domain).to_dense() | |
| else: | |
| assert False # pragma: no cover | |
| def _pivots(A_rref): | |
| """Return the pivots from the rref of A.""" | |
| return tuple(sorted(map(min, A_rref.to_sdm().values()))) | |
| def _check_cancel(result, rref_ans, den_ans): | |
| """Check the cancelled result.""" | |
| rref, den, pivots = result | |
| if isinstance(rref, (DDM, SDM, list, dict)): | |
| assert type(pivots) is list | |
| pivots = tuple(pivots) | |
| rref = _to_DM(rref, rref_ans) | |
| rref2, den2 = rref.cancel_denom(den) | |
| assert rref2 == rref_ans | |
| assert den2 == den_ans | |
| assert pivots == _pivots(rref) | |
| def _check_divide(result, rref_ans, den_ans): | |
| """Check the divided result.""" | |
| rref, pivots = result | |
| if isinstance(rref, (DDM, SDM, list, dict)): | |
| assert type(pivots) is list | |
| pivots = tuple(pivots) | |
| rref_ans = rref_ans.to_field() / den_ans | |
| rref = _to_DM(rref, rref_ans) | |
| assert rref == rref_ans | |
| assert _pivots(rref) == pivots | |
| def test_Matrix_rref(name, A, A_rref, den): | |
| K = A.domain | |
| A = A.to_Matrix() | |
| A_rref_found, pivots = A.rref() | |
| if K.is_EX: | |
| A_rref_found = A_rref_found.expand() | |
| _check_divide((A_rref_found, pivots), A_rref, den) | |
| def test_dm_dense_rref(name, A, A_rref, den): | |
| A = A.to_field() | |
| _check_divide(A.rref(), A_rref, den) | |
| def test_dm_dense_rref_den(name, A, A_rref, den): | |
| _check_cancel(A.rref_den(), A_rref, den) | |
| def test_dm_sparse_rref(name, A, A_rref, den): | |
| A = A.to_field().to_sparse() | |
| _check_divide(A.rref(), A_rref, den) | |
| def test_dm_sparse_rref_den(name, A, A_rref, den): | |
| A = A.to_sparse() | |
| _check_cancel(A.rref_den(), A_rref, den) | |
| def test_dm_sparse_rref_den_keep_domain(name, A, A_rref, den): | |
| A = A.to_sparse() | |
| A_rref_f, den_f, pivots_f = A.rref_den(keep_domain=False) | |
| A_rref_f = A_rref_f.to_field() / den_f | |
| _check_divide((A_rref_f, pivots_f), A_rref, den) | |
| def test_dm_sparse_rref_den_keep_domain_CD(name, A, A_rref, den): | |
| A = A.to_sparse() | |
| A_rref_f, den_f, pivots_f = A.rref_den(keep_domain=False, method='CD') | |
| A_rref_f = A_rref_f.to_field() / den_f | |
| _check_divide((A_rref_f, pivots_f), A_rref, den) | |
| def test_dm_sparse_rref_den_keep_domain_GJ(name, A, A_rref, den): | |
| A = A.to_sparse() | |
| A_rref_f, den_f, pivots_f = A.rref_den(keep_domain=False, method='GJ') | |
| A_rref_f = A_rref_f.to_field() / den_f | |
| _check_divide((A_rref_f, pivots_f), A_rref, den) | |
| def test_ddm_rref_den(name, A, A_rref, den): | |
| A = A.to_ddm() | |
| _check_cancel(A.rref_den(), A_rref, den) | |
| def test_sdm_rref_den(name, A, A_rref, den): | |
| A = A.to_sdm() | |
| _check_cancel(A.rref_den(), A_rref, den) | |
| def test_ddm_rref(name, A, A_rref, den): | |
| A = A.to_field().to_ddm() | |
| _check_divide(A.rref(), A_rref, den) | |
| def test_sdm_rref(name, A, A_rref, den): | |
| A = A.to_field().to_sdm() | |
| _check_divide(A.rref(), A_rref, den) | |
| def test_ddm_irref(name, A, A_rref, den): | |
| A = A.to_field().to_ddm().copy() | |
| pivots_found = ddm_irref(A) | |
| _check_divide((A, pivots_found), A_rref, den) | |
| def test_ddm_irref_den(name, A, A_rref, den): | |
| A = A.to_ddm().copy() | |
| (den_found, pivots_found) = ddm_irref_den(A, A.domain) | |
| result = (A, den_found, pivots_found) | |
| _check_cancel(result, A_rref, den) | |
| def test_sparse_sdm_rref(name, A, A_rref, den): | |
| A = A.to_field().to_sdm() | |
| _check_divide(sdm_irref(A)[:2], A_rref, den) | |
| def test_sparse_sdm_rref_den(name, A, A_rref, den): | |
| A = A.to_sdm().copy() | |
| K = A.domain | |
| _check_cancel(sdm_rref_den(A, K), A_rref, den) | |