Coverage for /usr/lib/python3/dist-packages/sympy/polys/matrices/lll.py: 9%

1from __future__ import annotations 

2 

3from math import floor as mfloor 

4 

5from sympy.polys.domains import ZZ, QQ 

6from sympy.polys.matrices.exceptions import DMRankError, DMShapeError, DMValueError, DMDomainError 

7 

8 

9def _ddm_lll(x, delta=QQ(3, 4), return_transform=False): 

10 if QQ(1, 4) >= delta or delta >= QQ(1, 1): 

11 raise DMValueError("delta must lie in range (0.25, 1)") 

12 if x.shape[0] > x.shape[1]: 

13 raise DMShapeError("input matrix must have shape (m, n) with m <= n") 

14 if x.domain != ZZ: 

15 raise DMDomainError("input matrix domain must be ZZ") 

16 m = x.shape[0] 

17 n = x.shape[1] 

18 k = 1 

19 y = x.copy() 

20 y_star = x.zeros((m, n), QQ) 

21 mu = x.zeros((m, m), QQ) 

22 g_star = [QQ(0, 1) for _ in range(m)] 

23 half = QQ(1, 2) 

24 T = x.eye(m, ZZ) if return_transform else None 

25 linear_dependent_error = "input matrix contains linearly dependent rows" 

26 

27 def closest_integer(x): 

28 return ZZ(mfloor(x + half)) 

29 

30 def lovasz_condition(k: int) -> bool: 

31 return g_star[k] >= ((delta - mu[k][k - 1] ** 2) * g_star[k - 1]) 

32 

33 def mu_small(k: int, j: int) -> bool: 

34 return abs(mu[k][j]) <= half 

35 

36 def dot_rows(x, y, rows: tuple[int, int]): 

37 return sum([x[rows[0]][z] * y[rows[1]][z] for z in range(x.shape[1])]) 

38 

39 def reduce_row(T, mu, y, rows: tuple[int, int]): 

40 r = closest_integer(mu[rows[0]][rows[1]]) 

41 y[rows[0]] = [y[rows[0]][z] - r * y[rows[1]][z] for z in range(n)] 

42 mu[rows[0]][:rows[1]] = [mu[rows[0]][z] - r * mu[rows[1]][z] for z in range(rows[1])] 

43 mu[rows[0]][rows[1]] -= r 

44 if return_transform: 

45 T[rows[0]] = [T[rows[0]][z] - r * T[rows[1]][z] for z in range(m)] 

46 

47 for i in range(m): 

48 y_star[i] = [QQ.convert_from(z, ZZ) for z in y[i]] 

49 for j in range(i): 

50 row_dot = dot_rows(y, y_star, (i, j)) 

51 try: 

52 mu[i][j] = row_dot / g_star[j] 

53 except ZeroDivisionError: 

54 raise DMRankError(linear_dependent_error) 

55 y_star[i] = [y_star[i][z] - mu[i][j] * y_star[j][z] for z in range(n)] 

56 g_star[i] = dot_rows(y_star, y_star, (i, i)) 

57 while k < m: 

58 if not mu_small(k, k - 1): 

59 reduce_row(T, mu, y, (k, k - 1)) 

60 if lovasz_condition(k): 

61 for l in range(k - 2, -1, -1): 

62 if not mu_small(k, l): 

63 reduce_row(T, mu, y, (k, l)) 

64 k += 1 

65 else: 

66 nu = mu[k][k - 1] 

67 alpha = g_star[k] + nu ** 2 * g_star[k - 1] 

68 try: 

69 beta = g_star[k - 1] / alpha 

70 except ZeroDivisionError: 

71 raise DMRankError(linear_dependent_error) 

72 mu[k][k - 1] = nu * beta 

73 g_star[k] = g_star[k] * beta 

74 g_star[k - 1] = alpha 

75 y[k], y[k - 1] = y[k - 1], y[k] 

76 mu[k][:k - 1], mu[k - 1][:k - 1] = mu[k - 1][:k - 1], mu[k][:k - 1] 

77 for i in range(k + 1, m): 

78 xi = mu[i][k] 

79 mu[i][k] = mu[i][k - 1] - nu * xi 

80 mu[i][k - 1] = mu[k][k - 1] * mu[i][k] + xi 

81 if return_transform: 

82 T[k], T[k - 1] = T[k - 1], T[k] 

83 k = max(k - 1, 1) 

84 assert all([lovasz_condition(i) for i in range(1, m)]) 

85 assert all([mu_small(i, j) for i in range(m) for j in range(i)]) 

86 return y, T 

87 

88 

89def ddm_lll(x, delta=QQ(3, 4)): 

90 return _ddm_lll(x, delta=delta, return_transform=False)[0] 

91 

92 

93def ddm_lll_transform(x, delta=QQ(3, 4)): 

94 return _ddm_lll(x, delta=delta, return_transform=True)