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 @pytest.mark.parametrize('name, A, A_rref, den', RREF_EXAMPLES) 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) @pytest.mark.parametrize('name, A, A_rref, den', RREF_EXAMPLES) def test_dm_dense_rref(name, A, A_rref, den): A = A.to_field() _check_divide(A.rref(), A_rref, den) @pytest.mark.parametrize('name, A, A_rref, den', RREF_EXAMPLES) def test_dm_dense_rref_den(name, A, A_rref, den): _check_cancel(A.rref_den(), A_rref, den) @pytest.mark.parametrize('name, A, A_rref, den', RREF_EXAMPLES) def test_dm_sparse_rref(name, A, A_rref, den): A = A.to_field().to_sparse() _check_divide(A.rref(), A_rref, den) @pytest.mark.parametrize('name, A, A_rref, den', RREF_EXAMPLES) def test_dm_sparse_rref_den(name, A, A_rref, den): A = A.to_sparse() _check_cancel(A.rref_den(), A_rref, den) @pytest.mark.parametrize('name, A, A_rref, den', RREF_EXAMPLES) 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) @pytest.mark.parametrize('name, A, A_rref, den', RREF_EXAMPLES) 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) @pytest.mark.parametrize('name, A, A_rref, den', RREF_EXAMPLES) 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) @pytest.mark.parametrize('name, A, A_rref, den', RREF_EXAMPLES) def test_ddm_rref_den(name, A, A_rref, den): A = A.to_ddm() _check_cancel(A.rref_den(), A_rref, den) @pytest.mark.parametrize('name, A, A_rref, den', RREF_EXAMPLES) def test_sdm_rref_den(name, A, A_rref, den): A = A.to_sdm() _check_cancel(A.rref_den(), A_rref, den) @pytest.mark.parametrize('name, A, A_rref, den', RREF_EXAMPLES) def test_ddm_rref(name, A, A_rref, den): A = A.to_field().to_ddm() _check_divide(A.rref(), A_rref, den) @pytest.mark.parametrize('name, A, A_rref, den', RREF_EXAMPLES) def test_sdm_rref(name, A, A_rref, den): A = A.to_field().to_sdm() _check_divide(A.rref(), A_rref, den) @pytest.mark.parametrize('name, A, A_rref, den', RREF_EXAMPLES) 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) @pytest.mark.parametrize('name, A, A_rref, den', RREF_EXAMPLES) 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) @pytest.mark.parametrize('name, A, A_rref, den', RREF_EXAMPLES) 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) @pytest.mark.parametrize('name, A, A_rref, den', RREF_EXAMPLES) 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)