Rewrite this function to use numba and nopython mode. You can assume that the input is a 2d matrix correctly formatted. Call it rref still. def rref(matrix, graphlen): PH = 16 extra = 0 col = 0 pivots = [] used_for_row = [set([i]) for i in range(matrix.shape[0])] matrix = matrix%PH while col+extra < matrix.shape[1]-1 and col < matrix.shape[0]: if matrix[col,col+extra] == 0: if np.all(matrix[:,col] == 0): extra += 1 continue other = np.argwhere(matrix[:,col+extra] != 0).flatten()[-1] if other < col: extra += 1 continue matrix[col], matrix[other] = list(matrix[other]), list(matrix[col]) used_for_row[col], used_for_row[other] = used_for_row[other], used_for_row[col] pivots.append(col+extra) pivot = matrix[col,col+extra] if col+extra < graphlen: assert np.abs(pivot) == 1 or np.abs(pivot) == PH-1 else: assert np.abs(pivot) == 2 or np.abs(pivot) == PH-2 pivot //= 2 matrix[col] *= pivot matrix[col] %= PH others = np.argwhere(matrix[:,col+extra]).flatten() for i in others: if i == col: continue used_for_row[i] |= used_for_row[col] if col < graphlen: matrix[i] -= matrix[col]*matrix[i,col+extra] else: while matrix[i,col+extra] != 0: matrix[i] = (matrix[i]-matrix[col])%PH matrix[i] %= PH col += 1 matrix = np.array(matrix)%PH return [sorted(x) for x in used_for_row]
Rewrite this function to use numba and nopython mode. You can assume that the input is a 2d matrix correctly formatted. Call it rref still. def rref(matrix, graphlen): PH = 16 extra = 0 col = 0 pivots = [] used_for_row = [set([i]) for i in range(matrix.shape[0])] matrix = matrix%PH while col+extra < matrix.shape[1]-1 and col < matrix.shape[0]: if matrix[col,col+extra] == 0: if np.all(matrix[:,col] == 0): extra += 1 continue other = np.argwhere(matrix[:,col+extra] != 0).flatten()[-1] if other < col: extra += 1 continue matrix[col], matrix[other] = list(matrix[other]), list(matrix[col]) used_for_row[col], used_for_row[other] = used_for_row[other], used_for_row[col] pivots.append(col+extra) pivot = matrix[col,col+extra] if col+extra < graphlen: assert np.abs(pivot) == 1 or np.abs(pivot) == PH-1 else: assert np.abs(pivot) == 2 or np.abs(pivot) == PH-2 pivot //= 2 matrix[col] *= pivot matrix[col] %= PH others = np.argwhere(matrix[:,col+extra]).flatten() for i in others: if i == col: continue used_for_row[i] |= used_for_row[col] if col < graphlen: matrix[i] -= matrix[col]*matrix[i,col+extra] else: while matrix[i,col+extra] != 0: matrix[i] = (matrix[i]-matrix[col])%PH matrix[i] %= PH col += 1 matrix = np.array(matrix)%PH return [sorted(x) for x in used_for_row]
Okay, here's the `rref` function rewritten using Numba in `nopython` mode. **Key Changes:** 1. **`@numba.njit` Decorator:** Added to enable Numba compilation in `nopython` mode. 2. **Type Hinting:** Added type hints to the function signature (`matrix_in: numba.types.int64[:, :], graphlen: numba.types.int64`). This helps Numba and improves readability. Numba often works without them, but explicit types are safer, especially for arrays. Assuming `int64` based on typical usage, adjust if your matrix uses a different integer type (e.g., `int32`). 3. **Input Copy:** Created `matrix = matrix_in.copy()` to avoid modifying the original input array, which is generally good practice. 4. **`used_for_row` Replacement:** The list of sets (`used_for_row`) is incompatible with `nopython` mode. It's replaced with a 2D NumPy boolean array (`used_for_row_matrix`). `used_for_row_matrix[i, j] = True` means that original row `j` contributed to the final row `i`. It's initialized as an identity matrix. 5. **Set Operations Replacement:** * Swapping sets (`used_for_row[col], used_for_row[other] = ...`) is replaced by swapping rows in the `used_for_row_matrix`. * Set union (`used_for_row[i] |= used_for_row[col]`) is replaced by a boolean OR operation on the rows of `used_for_row_matrix`. A loop is used for this as Numba sometimes handles element-wise boolean operations on rows more reliably this way than direct `np.logical_or` on slices in older versions, though `used_for_row_matrix[i] = np.logical_or(used_for_row_matrix[i], used_for_row_matrix[col])` might also work in recent Numba versions. The loop is explicit and guaranteed to work. 6. **NumPy Row Swapping:** Replaced `matrix[col], matrix[other] = list(matrix[other]), list(matrix[col])` with the efficient NumPy slice assignment `matrix[[col, other]] = matrix[[other, col]]`. 7. **NumPy Operations:** Ensured all array operations (`%`, `*`, `-=`, indexing, `np.where`, `np.eye`, `np.all`) are Numba-compatible. `np.argwhere(...).flatten()[-1]` was replaced with a combination of `np.where` and index selection to find the last suitable row *below* the current row for swapping, which is often more robust in RREF algorithms. `np.where` is generally well-supported. 8. **Return Value Construction:** The final list comprehension creating sorted lists from sets is replaced by: * Iterating through the rows of `used_for_row_matrix`. * Using `np.where(used_for_row_matrix[i])[0]` to get the indices of the original rows that contributed. * Converting these indices to a standard Python list (`list(...)`). * Sorting the list (`list.sort()`, which Numba supports). * Appending this sorted list to a `numba.typed.List` which is necessary for Numba to handle lists of lists in `nopython` mode. 9. **Removed Redundancy:** Removed the final `matrix = np.array(matrix)%PH` as `matrix` is already a NumPy array and modulo operations are applied throughout. 10. **Removed `pivots` list:** This list was created but not used in the return value, so it was removed for simplicity. 11. **Loop Condition:** Adjusted the `while` loop condition slightly to `while col < rows and col + extra < cols:` for clarity, ensuring it doesn't run past matrix boundaries. 12. **Pivot Finding:** Modified the pivot finding logic slightly to explicitly search for swap candidates *below* the current row (`matrix[col + 1:, col + extra]`) using `np.where`. This avoids potential issues if `np.argwhere` on the whole column finds a row index smaller than `col` that was moved there by previous swaps. 13. **Modulo Arithmetic:** Carefully preserved the modulo `PH` operations as in the original code. 14. **Non-Standard RREF Logic:** The specific logic involving `graphlen` and the different handling of pivots (especially making them `2` when `col >= graphlen`) is preserved exactly as in the original, even though it deviates from standard RREF aiming for leading `1`s.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 | import numba import numpy as np from numba.typed import List # Required for list-of-lists return type # Ensure PH is defined globally or passed as an argument if needed outside the function # For this example, it's kept inside as a constant. # PH = 16 @numba.njit(cache=True) # Use njit (nopython=True) and enable caching def rref(matrix_in: numba.types.int64[:, :], graphlen: numba.types.int64): """ Computes a variation of Reduced Row Echelon Form (RREF) modulo PH, tracking the original rows contributing to each final row. Args: matrix_in: The input 2D NumPy array (int64). graphlen: An integer threshold affecting pivot normalization. Returns: A Numba Typed List where each element is a sorted list of original row indices that constitute the corresponding row in the transformed matrix. """ PH = 16 # Modulo base # Work on a copy to avoid modifying the input array matrix = matrix_in.copy() rows, cols = matrix.shape # Replace list of sets with a boolean matrix for Numba compatibility # used_for_row_matrix[i, j] is True if original row j contributes to current row i # Initialize as identity matrix: initially, row i is composed only of original row i used_for_row_matrix = np.eye(rows, dtype=np.bool_) extra = 0 # Tracks columns skipped due to being all zeros below pivot col = 0 # Current row being processed (also target pivot row) # Apply modulo initially and after operations matrix = matrix % PH # Main loop: process rows and columns # Loop while we have rows left (col < rows) and columns left (col + extra < cols) while col < rows and col + extra < cols: pivot_col_idx = col + extra # --- Pivot Selection --- # If the current pivot element matrix[col, pivot_col_idx] is zero, # find a row below it with a non-zero element in the same column to swap. if matrix[col, pivot_col_idx] == 0: # Find indices of rows *below* 'col' with non-zero elements in the pivot column # np.where returns a tuple of arrays; we need the first array for row indices potential_swap_rows = np.where(matrix[col + 1:, pivot_col_idx] != 0)[0] + (col + 1) if len(potential_swap_rows) == 0: # If no non-zero element found below in this column, # this column cannot have a pivot starting at row 'col'. # Move to the next column by incrementing 'extra'. extra += 1 continue # Skip the rest of the loop for this 'col' else: # Choose the *last* row below 'col' with a non-zero element # (Matches the intent of original code's use of [-1]) other = potential_swap_rows[-1] # Swap row 'col' with row 'other' in the matrix matrix[[col, other]] = matrix[[other, col]] # Swap corresponding rows in the tracking matrix used_for_row_matrix[[col, other]] = used_for_row_matrix[[other, col]] # Apply modulo after swap just in case (though values shouldn't change) # matrix[col] %= PH # Not strictly necessary here # matrix[other] %= PH # Not strictly necessary here # --- Pivot Normalization --- # Now matrix[col, pivot_col_idx] is guaranteed non-zero (it's the pivot) current_pivot_val = matrix[col, pivot_col_idx] # Apply the specific normalization logic based on graphlen and pivot value # This part deviates from standard RREF aiming for 1s. if pivot_col_idx < graphlen: # Original asserts imply pivot is 1 or -1 (mod PH) # If pivot is -1 (mod PH), multiply row by -1 (mod PH) to make it 1 if current_pivot_val == PH - 1: matrix[col] = (matrix[col] * (PH - 1)) % PH # If pivot is 1, multiplying by 1 changes nothing. else: # pivot_col_idx >= graphlen # Original asserts imply pivot is 2 or -2 (mod PH) # Original code: pivot //= 2; matrix[col] *= pivot; matrix[col] %= PH if current_pivot_val == 2: multiplier = 1 # 2 // 2 matrix[col] = (matrix[col] * multiplier) % PH # Pivot remains 2 elif current_pivot_val == PH - 2: # 14 = -2 mod 16 multiplier = 7 # 14 // 2 matrix[col] = (matrix[col] * multiplier) % PH # Pivot becomes 14*7 = 98 = 2 mod 16 # In both cases for pivot_col_idx >= graphlen, the pivot element becomes 2. # Ensure the row is correctly modulo PH after normalization matrix[col] %= PH # --- Elimination --- # Eliminate other non-zero entries in the pivot column (pivot_col_idx) # Find indices of all rows (including 'col') with non-zero in pivot column other_rows = np.where(matrix[:, pivot_col_idx] != 0)[0] for i in other_rows: if i == col: continue # Don't eliminate the pivot row itself # Update the tracking matrix: row 'i' now also depends on original rows of 'col' # Equivalent to: used_for_row[i] |= used_for_row[col] for k in range(rows): # Iterate through original row indices if used_for_row_matrix[col, k]: used_for_row_matrix[i, k] = True # Perform row operation R_i = R_i - factor * R_col (mod PH) # or the special subtraction loop based on original logic. factor = matrix[i, pivot_col_idx] # The value we want to eliminate in row i if col < graphlen: # Note: Original code condition depends on 'col', not 'pivot_col_idx' # Standard elimination: R_i = R_i - factor * R_col matrix[i] = (matrix[i] - matrix[col] * factor) % PH else: # col >= graphlen # Special elimination: Subtract R_col repeatedly until element is 0 # Since pivot element matrix[col, pivot_col_idx] is 2 in this case, # and factor must be even for the loop to terminate correctly in Z_16, # this subtracts R_col (factor / 2) times. # The original loop is preserved for exactness: while matrix[i, pivot_col_idx] != 0: matrix[i] = (matrix[i] - matrix[col]) % PH # Ensure modulo PH (already done in loop) # matrix[i] %= PH # Redundant # Move to the next row/pivot col += 1 # --- Prepare Return Value --- # Create a Numba typed list to store the results result = List() # Numba requires explicit typing for list elements if complex (like list-of-list) # We pre-allocate the outer list type. Numba infers inner list type (int). for i in range(rows): # Find original row indices that contributed to final row i original_indices = np.where(used_for_row_matrix[i])[0] # Convert to a standard Python list (Numba can handle lists of primitives) original_indices_list = list(original_indices) # Sort the list in place (Numba supports list.sort()) original_indices_list.sort() # Append the sorted list to the result list result.append(original_indices_list) # The function implicitly returns the modified matrix state via side effects # on the 'matrix' copy, but the explicit return value matches the original: # the tracking information about original rows. return result # Example Usage: if __name__ == '__main__': # Example matrix (ensure dtype is compatible, e.g., np.int64) mat = np.array([ [1, 2, 3, 1, 0, 0], [0, 1, 4, 0, 1, 0], [2, 5, 10, 0, 0, 1] ], dtype=np.int64) gl = 3 # Example graphlen print("Original Matrix:\n", mat) # Call the Numba function used_rows_info = rref(mat, gl) # The 'mat' variable itself is NOT modified because rref works on a copy. # If you wanted the modified matrix, you'd need rref to return it too. # For now, we just print the returned tracking info. print("\nUsed Rows Information (Numba Result):") # Convert Numba typed list back to standard list for printing if needed print(list(used_rows_info)) # Example with a column needing swap and skip mat2 = np.array([ [0, 1, 2], [0, 0, 3], [0, 2, 5] ], dtype=np.int64) gl2 = 1 print("\nOriginal Matrix 2:\n", mat2) used_rows_info2 = rref(mat2, gl2) print("\nUsed Rows Information 2 (Numba Result):") print(list(used_rows_info2)) # Example involving PH and graphlen logic mat3 = np.array([ [1, 15, 0], # 15 = -1 mod 16 [0, 2, 1], [0, 14, 3] # 14 = -2 mod 16 ], dtype=np.int64) gl3 = 1 # Pivot col 0 < gl3, Pivot col 1 >= gl3 print("\nOriginal Matrix 3:\n", mat3) used_rows_info3 = rref(mat3, gl3) print("\nUsed Rows Information 3 (Numba Result):") print(list(used_rows_info3)) |
I extracted the following code from that output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 | import numba import numpy as np from numba.typed import List # Required for list-of-lists return type # Ensure PH is defined globally or passed as an argument if needed outside the function # For this example, it's kept inside as a constant. # PH = 16 @numba.njit(cache=True) # Use njit (nopython=True) and enable caching def rref(matrix_in: numba.types.int64[:, :], graphlen: numba.types.int64): """ Computes a variation of Reduced Row Echelon Form (RREF) modulo PH, tracking the original rows contributing to each final row. Args: matrix_in: The input 2D NumPy array (int64). graphlen: An integer threshold affecting pivot normalization. Returns: A Numba Typed List where each element is a sorted list of original row indices that constitute the corresponding row in the transformed matrix. """ PH = 16 # Modulo base # Work on a copy to avoid modifying the input array matrix = matrix_in.copy() rows, cols = matrix.shape # Replace list of sets with a boolean matrix for Numba compatibility # used_for_row_matrix[i, j] is True if original row j contributes to current row i # Initialize as identity matrix: initially, row i is composed only of original row i used_for_row_matrix = np.eye(rows, dtype=np.bool_) extra = 0 # Tracks columns skipped due to being all zeros below pivot col = 0 # Current row being processed (also target pivot row) # Apply modulo initially and after operations matrix = matrix % PH # Main loop: process rows and columns # Loop while we have rows left (col < rows) and columns left (col + extra < cols) while col < rows and col + extra < cols: pivot_col_idx = col + extra # --- Pivot Selection --- # If the current pivot element matrix[col, pivot_col_idx] is zero, # find a row below it with a non-zero element in the same column to swap. if matrix[col, pivot_col_idx] == 0: # Find indices of rows *below* 'col' with non-zero elements in the pivot column # np.where returns a tuple of arrays; we need the first array for row indices potential_swap_rows = np.where(matrix[col + 1:, pivot_col_idx] != 0)[0] + (col + 1) if len(potential_swap_rows) == 0: # If no non-zero element found below in this column, # this column cannot have a pivot starting at row 'col'. # Move to the next column by incrementing 'extra'. extra += 1 continue # Skip the rest of the loop for this 'col' else: # Choose the *last* row below 'col' with a non-zero element # (Matches the intent of original code's use of [-1]) other = potential_swap_rows[-1] # Swap row 'col' with row 'other' in the matrix matrix[[col, other]] = matrix[[other, col]] # Swap corresponding rows in the tracking matrix used_for_row_matrix[[col, other]] = used_for_row_matrix[[other, col]] # Apply modulo after swap just in case (though values shouldn't change) # matrix[col] %= PH # Not strictly necessary here # matrix[other] %= PH # Not strictly necessary here # --- Pivot Normalization --- # Now matrix[col, pivot_col_idx] is guaranteed non-zero (it's the pivot) current_pivot_val = matrix[col, pivot_col_idx] # Apply the specific normalization logic based on graphlen and pivot value # This part deviates from standard RREF aiming for 1s. if pivot_col_idx < graphlen: # Original asserts imply pivot is 1 or -1 (mod PH) # If pivot is -1 (mod PH), multiply row by -1 (mod PH) to make it 1 if current_pivot_val == PH - 1: matrix[col] = (matrix[col] * (PH - 1)) % PH # If pivot is 1, multiplying by 1 changes nothing. else: # pivot_col_idx >= graphlen # Original asserts imply pivot is 2 or -2 (mod PH) # Original code: pivot //= 2; matrix[col] *= pivot; matrix[col] %= PH if current_pivot_val == 2: multiplier = 1 # 2 // 2 matrix[col] = (matrix[col] * multiplier) % PH # Pivot remains 2 elif current_pivot_val == PH - 2: # 14 = -2 mod 16 multiplier = 7 # 14 // 2 matrix[col] = (matrix[col] * multiplier) % PH # Pivot becomes 14*7 = 98 = 2 mod 16 # In both cases for pivot_col_idx >= graphlen, the pivot element becomes 2. # Ensure the row is correctly modulo PH after normalization matrix[col] %= PH # --- Elimination --- # Eliminate other non-zero entries in the pivot column (pivot_col_idx) # Find indices of all rows (including 'col') with non-zero in pivot column other_rows = np.where(matrix[:, pivot_col_idx] != 0)[0] for i in other_rows: if i == col: continue # Don't eliminate the pivot row itself # Update the tracking matrix: row 'i' now also depends on original rows of 'col' # Equivalent to: used_for_row[i] |= used_for_row[col] for k in range(rows): # Iterate through original row indices if used_for_row_matrix[col, k]: used_for_row_matrix[i, k] = True # Perform row operation R_i = R_i - factor * R_col (mod PH) # or the special subtraction loop based on original logic. factor = matrix[i, pivot_col_idx] # The value we want to eliminate in row i if col < graphlen: # Note: Original code condition depends on 'col', not 'pivot_col_idx' # Standard elimination: R_i = R_i - factor * R_col matrix[i] = (matrix[i] - matrix[col] * factor) % PH else: # col >= graphlen # Special elimination: Subtract R_col repeatedly until element is 0 # Since pivot element matrix[col, pivot_col_idx] is 2 in this case, # and factor must be even for the loop to terminate correctly in Z_16, # this subtracts R_col (factor / 2) times. # The original loop is preserved for exactness: while matrix[i, pivot_col_idx] != 0: matrix[i] = (matrix[i] - matrix[col]) % PH # Ensure modulo PH (already done in loop) # matrix[i] %= PH # Redundant # Move to the next row/pivot col += 1 # --- Prepare Return Value --- # Create a Numba typed list to store the results result = List() # Numba requires explicit typing for list elements if complex (like list-of-list) # We pre-allocate the outer list type. Numba infers inner list type (int). for i in range(rows): # Find original row indices that contributed to final row i original_indices = np.where(used_for_row_matrix[i])[0] # Convert to a standard Python list (Numba can handle lists of primitives) original_indices_list = list(original_indices) # Sort the list in place (Numba supports list.sort()) original_indices_list.sort() # Append the sorted list to the result list result.append(original_indices_list) # The function implicitly returns the modified matrix state via side effects # on the 'matrix' copy, but the explicit return value matches the original: # the tracking information about original rows. return result # Example Usage: if __name__ == '__main__': # Example matrix (ensure dtype is compatible, e.g., np.int64) mat = np.array([ [1, 2, 3, 1, 0, 0], [0, 1, 4, 0, 1, 0], [2, 5, 10, 0, 0, 1] ], dtype=np.int64) gl = 3 # Example graphlen print("Original Matrix:\n", mat) # Call the Numba function used_rows_info = rref(mat, gl) # The 'mat' variable itself is NOT modified because rref works on a copy. # If you wanted the modified matrix, you'd need rref to return it too. # For now, we just print the returned tracking info. print("\nUsed Rows Information (Numba Result):") # Convert Numba typed list back to standard list for printing if needed print(list(used_rows_info)) # Example with a column needing swap and skip mat2 = np.array([ [0, 1, 2], [0, 0, 3], [0, 2, 5] ], dtype=np.int64) gl2 = 1 print("\nOriginal Matrix 2:\n", mat2) used_rows_info2 = rref(mat2, gl2) print("\nUsed Rows Information 2 (Numba Result):") print(list(used_rows_info2)) # Example involving PH and graphlen logic mat3 = np.array([ [1, 15, 0], # 15 = -1 mod 16 [0, 2, 1], [0, 14, 3] # 14 = -2 mod 16 ], dtype=np.int64) gl3 = 1 # Pivot col 0 < gl3, Pivot col 1 >= gl3 print("\nOriginal Matrix 3:\n", mat3) used_rows_info3 = rref(mat3, gl3) print("\nUsed Rows Information 3 (Numba Result):") print(list(used_rows_info3)) |
Running the following program:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 | import numba import numpy as np from numba.typed import List # Required for list-of-lists return type # Ensure PH is defined globally or passed as an argument if needed outside the function # For this example, it's kept inside as a constant. # PH = 16 @numba.njit(cache=True) # Use njit (nopython=True) and enable caching def rref(matrix_in: numba.types.int64[:, :], graphlen: numba.types.int64): """ Computes a variation of Reduced Row Echelon Form (RREF) modulo PH, tracking the original rows contributing to each final row. Args: matrix_in: The input 2D NumPy array (int64). graphlen: An integer threshold affecting pivot normalization. Returns: A Numba Typed List where each element is a sorted list of original row indices that constitute the corresponding row in the transformed matrix. """ PH = 16 # Modulo base # Work on a copy to avoid modifying the input array matrix = matrix_in.copy() rows, cols = matrix.shape # Replace list of sets with a boolean matrix for Numba compatibility # used_for_row_matrix[i, j] is True if original row j contributes to current row i # Initialize as identity matrix: initially, row i is composed only of original row i used_for_row_matrix = np.eye(rows, dtype=np.bool_) extra = 0 # Tracks columns skipped due to being all zeros below pivot col = 0 # Current row being processed (also target pivot row) # Apply modulo initially and after operations matrix = matrix % PH # Main loop: process rows and columns # Loop while we have rows left (col < rows) and columns left (col + extra < cols) while col < rows and col + extra < cols: pivot_col_idx = col + extra # --- Pivot Selection --- # If the current pivot element matrix[col, pivot_col_idx] is zero, # find a row below it with a non-zero element in the same column to swap. if matrix[col, pivot_col_idx] == 0: # Find indices of rows *below* 'col' with non-zero elements in the pivot column # np.where returns a tuple of arrays; we need the first array for row indices potential_swap_rows = np.where(matrix[col + 1:, pivot_col_idx] != 0)[0] + (col + 1) if len(potential_swap_rows) == 0: # If no non-zero element found below in this column, # this column cannot have a pivot starting at row 'col'. # Move to the next column by incrementing 'extra'. extra += 1 continue # Skip the rest of the loop for this 'col' else: # Choose the *last* row below 'col' with a non-zero element # (Matches the intent of original code's use of [-1]) other = potential_swap_rows[-1] # Swap row 'col' with row 'other' in the matrix matrix[[col, other]] = matrix[[other, col]] # Swap corresponding rows in the tracking matrix used_for_row_matrix[[col, other]] = used_for_row_matrix[[other, col]] # Apply modulo after swap just in case (though values shouldn't change) # matrix[col] %= PH # Not strictly necessary here # matrix[other] %= PH # Not strictly necessary here # --- Pivot Normalization --- # Now matrix[col, pivot_col_idx] is guaranteed non-zero (it's the pivot) current_pivot_val = matrix[col, pivot_col_idx] # Apply the specific normalization logic based on graphlen and pivot value # This part deviates from standard RREF aiming for 1s. if pivot_col_idx < graphlen: # Original asserts imply pivot is 1 or -1 (mod PH) # If pivot is -1 (mod PH), multiply row by -1 (mod PH) to make it 1 if current_pivot_val == PH - 1: matrix[col] = (matrix[col] * (PH - 1)) % PH # If pivot is 1, multiplying by 1 changes nothing. else: # pivot_col_idx >= graphlen # Original asserts imply pivot is 2 or -2 (mod PH) # Original code: pivot //= 2; matrix[col] *= pivot; matrix[col] %= PH if current_pivot_val == 2: multiplier = 1 # 2 // 2 matrix[col] = (matrix[col] * multiplier) % PH # Pivot remains 2 elif current_pivot_val == PH - 2: # 14 = -2 mod 16 multiplier = 7 # 14 // 2 matrix[col] = (matrix[col] * multiplier) % PH # Pivot becomes 14*7 = 98 = 2 mod 16 # In both cases for pivot_col_idx >= graphlen, the pivot element becomes 2. # Ensure the row is correctly modulo PH after normalization matrix[col] %= PH # --- Elimination --- # Eliminate other non-zero entries in the pivot column (pivot_col_idx) # Find indices of all rows (including 'col') with non-zero in pivot column other_rows = np.where(matrix[:, pivot_col_idx] != 0)[0] for i in other_rows: if i == col: continue # Don't eliminate the pivot row itself # Update the tracking matrix: row 'i' now also depends on original rows of 'col' # Equivalent to: used_for_row[i] |= used_for_row[col] for k in range(rows): # Iterate through original row indices if used_for_row_matrix[col, k]: used_for_row_matrix[i, k] = True # Perform row operation R_i = R_i - factor * R_col (mod PH) # or the special subtraction loop based on original logic. factor = matrix[i, pivot_col_idx] # The value we want to eliminate in row i if col < graphlen: # Note: Original code condition depends on 'col', not 'pivot_col_idx' # Standard elimination: R_i = R_i - factor * R_col matrix[i] = (matrix[i] - matrix[col] * factor) % PH else: # col >= graphlen # Special elimination: Subtract R_col repeatedly until element is 0 # Since pivot element matrix[col, pivot_col_idx] is 2 in this case, # and factor must be even for the loop to terminate correctly in Z_16, # this subtracts R_col (factor / 2) times. # The original loop is preserved for exactness: while matrix[i, pivot_col_idx] != 0: matrix[i] = (matrix[i] - matrix[col]) % PH # Ensure modulo PH (already done in loop) # matrix[i] %= PH # Redundant # Move to the next row/pivot col += 1 # --- Prepare Return Value --- # Create a Numba typed list to store the results result = List() # Numba requires explicit typing for list elements if complex (like list-of-list) # We pre-allocate the outer list type. Numba infers inner list type (int). for i in range(rows): # Find original row indices that contributed to final row i original_indices = np.where(used_for_row_matrix[i])[0] # Convert to a standard Python list (Numba can handle lists of primitives) original_indices_list = list(original_indices) # Sort the list in place (Numba supports list.sort()) original_indices_list.sort() # Append the sorted list to the result list result.append(original_indices_list) # The function implicitly returns the modified matrix state via side effects # on the 'matrix' copy, but the explicit return value matches the original: # the tracking information about original rows. return result # Example Usage: if __name__ == '__main__': # Example matrix (ensure dtype is compatible, e.g., np.int64) mat = np.array([ [1, 2, 3, 1, 0, 0], [0, 1, 4, 0, 1, 0], [2, 5, 10, 0, 0, 1] ], dtype=np.int64) gl = 3 # Example graphlen print("Original Matrix:\n", mat) # Call the Numba function used_rows_info = rref(mat, gl) # The 'mat' variable itself is NOT modified because rref works on a copy. # If you wanted the modified matrix, you'd need rref to return it too. # For now, we just print the returned tracking info. print("\nUsed Rows Information (Numba Result):") # Convert Numba typed list back to standard list for printing if needed print(list(used_rows_info)) # Example with a column needing swap and skip mat2 = np.array([ [0, 1, 2], [0, 0, 3], [0, 2, 5] ], dtype=np.int64) gl2 = 1 print("\nOriginal Matrix 2:\n", mat2) used_rows_info2 = rref(mat2, gl2) print("\nUsed Rows Information 2 (Numba Result):") print(list(used_rows_info2)) # Example involving PH and graphlen logic mat3 = np.array([ [1, 15, 0], # 15 = -1 mod 16 [0, 2, 1], [0, 14, 3] # 14 = -2 mod 16 ], dtype=np.int64) gl3 = 1 # Pivot col 0 < gl3, Pivot col 1 >= gl3 print("\nOriginal Matrix 3:\n", mat3) used_rows_info3 = rref(mat3, gl3) print("\nUsed Rows Information 3 (Numba Result):") print(list(used_rows_info3)) arr = np.array([[1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 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, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -10], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -20], [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, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, -2, 0, 0, 0, 0, 0, 0, 0, 0, 0, -20], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -11], [0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -2, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -2, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -2, 0, 0, 0, 0, 0, 0, -30], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -2, 0, 0, 0, 0, 0, -20], [1, 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, 0, 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, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -11], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -14], [0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -10], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -2, 0, 0, 0, 0, -30], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -10], [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -10], [0, 0, 0, -1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -11], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -13], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -11], [0, 0, 0, 0, -1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -10], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, -2, 0, 0, 0, -20], [0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -10], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -11], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -13], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -13], [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, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 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, 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, 0, 0, 0, 0, 1, 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, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -11], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -2, 0, 0, -10], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -13], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -11], [0, 0, 1, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -9], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -2, 0, -20], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -2, -40], [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]) answer = rref(arr, 37) expected = [[0, 38], [0, 38], [0, 6, 28, 35, 38], [0, 6, 18, 21, 28, 35, 38], [0, 6, 28, 35, 38], [0, 6, 21, 28, 35, 38], [0, 5, 10, 23, 38], [0, 5, 10, 23, 38], [0, 5, 10, 23, 38], [0, 5, 9, 10, 23, 38], [0, 5, 9, 10, 13, 17, 23, 30, 38], [0, 5, 9, 10, 11, 23, 27, 38], [0, 5, 9, 10, 11, 23, 27, 38], [0, 5, 9, 10, 11, 23, 25, 27, 38], [0, 1, 5, 7, 8, 9, 10, 11, 12, 15, 16, 19, 23, 25, 26, 27, 34, 38], [0, 1, 5, 7, 8, 9, 10, 11, 12, 15, 16, 19, 23, 25, 26, 27, 34, 38], [0, 1, 5, 7, 8, 9, 10, 11, 12, 15, 16, 19, 23, 25, 26, 27, 34, 38], [0, 1, 5, 7, 8, 9, 10, 11, 12, 15, 16, 19, 23, 25, 26, 27, 34, 38], [0, 1, 5, 7, 8, 9, 10, 11, 12, 15, 16, 19, 23, 25, 26, 27, 34, 38], [0, 1, 5, 7, 8, 9, 10, 11, 12, 15, 16, 19, 23, 25, 26, 27, 34, 38], [0, 1, 5, 7, 8, 9, 10, 11, 12, 15, 16, 19, 23, 24, 25, 26, 27, 34, 38], [0, 1, 5, 7, 8, 9, 10, 11, 12, 15, 16, 19, 23, 25, 26, 27, 34, 38], [0, 1, 5, 7, 8, 9, 10, 11, 12, 15, 16, 19, 23, 25, 26, 27, 34, 38], [0, 1, 5, 7, 8, 9, 10, 11, 12, 15, 16, 19, 23, 25, 26, 27, 34, 38], [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 15, 16, 19, 20, 21, 23, 25, 26, 27, 28, 31, 34, 35, 36, 37, 38], [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 15, 16, 19, 20, 21, 23, 25, 26, 27, 28, 31, 34, 35, 36, 37, 38], [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 15, 16, 19, 20, 21, 23, 25, 26, 27, 28, 31, 34, 35, 36, 37, 38], [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 15, 16, 19, 20, 21, 23, 25, 26, 27, 28, 31, 34, 35, 36, 37, 38], [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 15, 16, 19, 20, 21, 23, 25, 26, 27, 28, 31, 34, 35, 36, 37, 38], [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 15, 16, 19, 20, 21, 23, 25, 26, 27, 28, 31, 34, 35, 36, 37, 38], [0, 5, 9, 10, 13, 17, 23, 30, 38], [0, 5, 9, 10, 13, 17, 23, 30, 38], [0, 5, 9, 10, 13, 17, 23, 30, 32, 38], [0, 5, 9, 10, 13, 17, 23, 30, 32, 33, 38], [0, 22, 29, 38], [0, 22, 29, 38], [0, 6, 28, 35, 38], [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 15, 16, 19, 20, 21, 23, 25, 26, 27, 28, 31, 34, 35, 36, 37, 38], [14, 18, 21, 28, 35]] assert answer == expected, f'Wrong answer; got {answer} instead of {expected}' print('All tests passed') |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 | Original Matrix: [[ 1 2 3 1 0 0] [ 0 1 4 0 1 0] [ 2 5 10 0 0 1]] Traceback (most recent call last): File "/usr/src/app/main.py", line 176, in <module> used_rows_info = rref(mat, gl) ^^^^^^^^^^^^^ File "/usr/local/lib/python3.12/dist-packages/numba/core/dispatcher.py", line 423, in _compile_for_args error_rewrite(e, 'typing') File "/usr/local/lib/python3.12/dist-packages/numba/core/dispatcher.py", line 364, in error_rewrite raise e.with_traceback(None) numba.core.errors.TypingError: Failed in nopython mode pipeline (step: nopython frontend) No implementation of function Function(<built-in function getitem>) found for signature:</p> <blockquote> <blockquote> <blockquote> <p>getitem(array(int64, 2d, C), list(int64)<iv=None>)</p> </blockquote> </blockquote> </blockquote> <p>There are 22 candidate implementations: - Of which 20 did not match due to: Overload of function 'getitem': File: <numerous>: Line N/A. With argument(s): '(array(int64, 2d, C), list(int64)<iv=None>)': No match. - Of which 2 did not match due to: Overload in function 'GetItemBuffer.generic': File: numba/core/typing/arraydecl.py: Line 211. With argument(s): '(array(int64, 2d, C), list(int64)<iv=None>)': Rejected as the implementation raised a specific error: NumbaTypeError: Unsupported array index type list(int64)<iv=None> in [List(int64, False)] raised from /usr/local/lib/python3.12/dist-packages/numba/core/typing/arraydecl.py:104 During: typing of intrinsic-call at /usr/src/app/main.py (67) File "main.py", line 67: def rref(matrix_in: numba.types.int64[:, :], graphlen: numba.types.int64): <source elided> # Swap row 'col' with row 'other' in the matrix matrix[[col, other]] = matrix[[other, col]] ^ |
Testing if the previous output contains the string All tests passed
: False
Testing if the previous output contains the string njit
: True
Testing if the previous output contains the string nopython
: True
Testing if the previous output contains the string import numba
: True
Testing if the previous output contains the string from numba
: True