np-linear-0.3: src/Algebra/Linear.hs
{-# LANGUAGE NoImplicitPrelude,RebindableSyntax #-}
{-# LANGUAGE ScopedTypeVariables,FlexibleContexts #-}
module Algebra.Linear
(
Relation(..)
, satisfies
, solve
, dependencies
, equations
, inverseImage
, Matrix
, Vector
, matrixProduct
, matrixVector
, innerProduct
, identity
, matrixFromFunction
, affine
, permute
, rowSwap
, invert
, determinant
, adjoint
, diagonal
) where
import Auxiliary (δ,findAmong,headE,adorn)
import qualified Algebra.Field
import qualified Algebra.Lattice
import qualified Algebra.Module
import qualified Algebra.Ring
import NumericPrelude
import Control.Applicative ((<$>))
import Control.Arrow (first,second)
import Data.List
(
partition
, find
, transpose
, genericLength
, genericTake
, genericDrop
, genericReplicate
)
import qualified Data.Map as Map
import Data.Proxy (Proxy(Proxy))
import Data.Reflection (Reifies,reflect)
type Vector k
= [k]
type Matrix k
= [Vector k]
-- A relation among vectors of degree 'd' over field 'k'
data Relation k
= Relation { getRelation :: [k] }
deriving (Show)
satisfies :: (Algebra.Ring.C k,Eq k) => Vector k -> Relation k -> Bool
satisfies v (Relation r) = innerProduct v r == 0
-- | Calculate all dependencies among the given vectors of degree d.
dependencies :: (Algebra.Field.C k,Eq k) => Integer -> [Vector k] -> [Relation k]
dependencies d = map (Relation . genericDrop d) . filter (all (== zero) . genericTake d) . (\ (r,_,_) -> r) . reduce' . adorn
-- | Calculate the equations satisfied by the subspace spanned by the given vectors of degree d.
equations :: (Algebra.Field.C k,Eq k) => Integer -> [Vector k] -> [Relation k]
equations d vs = dependencies (genericLength vs + 1) . transpose . (:) (genericReplicate d zero) $ vs
-- | Solve the given equations, in the form of a basis of vectors of degree d.
solve :: (Algebra.Field.C k,Eq k) => Integer -> [Relation k] -> [Vector k]
solve d = map getRelation . equations d . map getRelation
inverseImage :: (Algebra.Field.C k,Eq k) => Matrix k -> Vector k -> Vector k
inverseImage a = solveUpperTriangular u . matrixVector b where
(u,b,_) = reduce' a
invert :: (Algebra.Field.C k,Eq k) => Matrix k -> Maybe (Matrix k)
invert m = fmap strip . process . (\ (r,_,_) -> r) . reduce' . adorn $ m where
n = length m
process x = go x where
go [v] = Just [v]
go (r@(pivot : r') : rest)
| pivot == 1 = do
m' <- go (map tail rest)
rowsToAdd <- sequence . zipWith3 f [0 ..] r' $ m'
return $ (1 : foldr (zipWith (+)) r' rowsToAdd) : map (0 :) m'
| otherwise = Nothing
f i c v
| v₀ == 0 = Nothing
| otherwise = Just $ map ((*) (negate c / v₀)) v
where
v₀ = v !! i
strip = map (drop n)
determinant :: (Algebra.Field.C k,Eq k,DebugDeterminant k) => Matrix k -> k
determinant x = case reduce x of (_,_,σ) -> σ
adjoint :: (Algebra.Lattice.C k,Algebra.Field.C k,Eq k,DebugDeterminant k) => Matrix k -> Maybe (Matrix k)
adjoint a = (abs (determinant a) *>) <$> invert a
diagonal :: Matrix k -> [k]
diagonal [] = []
diagonal ((d : _) : rest) = d : diagonal (map tail rest)
matrixProduct :: (Algebra.Ring.C k) => Matrix k -> Matrix k -> Matrix k
matrixProduct a b = map (($ transpose b) . map . innerProduct) a
matrixVector :: (Algebra.Ring.C k) => Matrix k -> Vector k -> Vector k
matrixVector a = map (\ [x] -> x) . matrixProduct a . map (: [])
innerProduct :: (Algebra.Ring.C k) => Vector k -> Vector k -> k
innerProduct a b = sum (zipWith (*) a b)
matrixFromFunction :: Int -> Int -> (Int -> Int -> k) -> Matrix k
matrixFromFunction m n f = [[f i j | j <- [1 .. n]] | i <- [1 .. m]]
identity :: (Algebra.Ring.C k) => Int -> Matrix k
identity n = matrixFromFunction n n δ
-- Triangular decomposition
solveUpperTriangular :: (Algebra.Field.C k,Eq k) => Matrix k -> Vector k -> Vector k
solveUpperTriangular u x = reverse $ solveLowerTriangular (reverse . map reverse $ u) (reverse x)
solveLowerTriangular :: (Algebra.Field.C k,Eq k) => Matrix k -> Vector k -> Vector k
solveLowerTriangular l x = go l x [] where
go [] [] q = q
go (lᵢ : l') (xᵢ : x') q = go l' x' (q ++ [qᵢ]) where
(lFirst,lᵢᵢ : _) = splitAt (length q) lᵢ
y = xᵢ - innerProduct q lFirst
qᵢ
| lᵢᵢ == 0 = error "Linear.solveLowerTriangular: zero on diagonal"
| otherwise = y / lᵢᵢ
class DebugDeterminant a where
reduce :: (Algebra.Field.C k,Eq k,DebugDeterminant k) => Matrix k -> (Matrix k,Matrix k,k)
reduce = reduce'
-- Compute the row echelon form of the matrix,
-- together with the basis transformation matrix,
-- and its determinant.
reduce' :: (Algebra.Field.C k,Eq k) => Matrix k -> (Matrix k,Matrix k,k)
reduce' [] = ([],[],1)
reduce' xs@([] : _) = (xs,identity (length xs),1)
reduce' vs = case nonZero of
[] -> (\ (x,u,_σ) -> (map (0 :) x,u,0)) $ reduce' (map tail vs)
(v@(v₀ : _),i) : [] -> let
subMatrix = map (tail . fst) startZero
(h,u,σ) = reduce' subMatrix
sign = if odd i then 1 else -1
in
( (map (/ v₀) v :) . map (0 :) $ h
, normalisation v₀ `matrixProduct` rowSwap n (1,i) `matrixProduct` shift u
,sign * v₀ * σ
)
(v@(v₀ : _),i) : rest -> let
(reduced,translates) = unzip . flip map rest $ \ (x@(x₀ : _),j) -> let
c = x₀ / v₀ in ((zipWith (\ vᵢ xᵢ -> xᵢ - c * vᵢ) v x,j),(j,c))
subMatrix = v : map fst reduced ++ map fst startZero
(h,u,σ) = reduce' subMatrix
permutation = i : map snd reduced ++ map snd startZero
in
( h
, u
`matrixProduct` permute permutation
`matrixProduct` affine n i (map (second negate) translates)
, permutationSign permutation * σ
)
where
(startZero,nonZero) = partition ((==) 0 . head . fst) . flip zip [1 ..] $ vs
normalisation v₀ = matrixFromFunction n n f where
f 1 1 = 1 / v₀
f i j = δ i j
shift u = (1 : replicate (n - 1) 0) : map (0 :) u
n = length vs
rowSwap :: (Algebra.Ring.C k) => Int -> (Int,Int) -> Matrix k
rowSwap n (k,l) = matrixFromFunction n n f where
f i j
| i == k && j == l = one
| i == l && j == k = one
| i == j && i /= k && i /= l = one
| otherwise = zero
affine :: (Algebra.Ring.C k) => Int -> Int -> [(Int,k)] -> Matrix k
affine n k ps = matrixFromFunction n n $ \ i j -> δ i j + c i j where
m = Map.fromList ps
c i j = case (Map.lookup i m,j == k) of
(Just cᵢ,True) -> cᵢ
_ -> zero
permute :: (Algebra.Ring.C k) => [Int] -> Matrix k
permute is = matrixFromFunction n n (\ i j -> δ (is !! (i - 1)) j) where
n = length is
permutationSign :: (Algebra.Ring.C k) => [Int] -> k
permutationSign [] = one
permutationSign (x : xs) = ε * permutationSign xs where
inversions = length $ filter (x >) xs
ε
| even inversions = one
| otherwise = negate one
-- Example
x :: Matrix Rational
x =
[
[0, 3,-6, 6,4,5 ]
, [3,-7, 8,-5,8,9 ]
, [3,-9,12,-9,6,15]
]
_M₁,_M₂,_M₃ :: Matrix Rational
_M₁ =
[
[0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,-108221942156800 % 524799,0 % 1,0 % 1,108221942156800 % 524799,0 % 1,1 % 1]
, [-169096784620000 % 453365147813277,-838720051715200 % 4987016625946047,6763871384800 % 151121715937759,216443884313600 % 4987016625946047,392304540318400 % 4987016625946047,27055485539200 % 1662338875315349,351721312009600 % 453365147813277,1975050444361600 % 4987016625946047,101458070772000 % 1662338875315349,5221708709065600 % 4987016625946047,1102511035722400 % 4987016625946047,1 % 1]
, [0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,-541109710784 % 95367421875,0 % 1,0 % 1,0 % 1,541109710784 % 95367421875,1 % 1]
, [0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,6763871384800 % 16663069252269,0 % 1,0 % 1,1 % 1]
, [0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,211370980775 % 536346624,0 % 1,0 % 1,0 % 1,1 % 1]
, [3381935692400 % 19061697322899,-3381935692400 % 19061697322899,-3381935692400 % 19061697322899,0 % 1,0 % 1,3381935692400 % 19061697322899,3381935692400 % 19061697322899,0 % 1,0 % 1,-3381935692400 % 19061697322899,0 % 1,1 % 1]
, [0 % 1,-211370980775 % 537394176,0 % 1,211370980775 % 537394176,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,-211370980775 % 537394176,0 % 1,1 % 1]
, [-3381935692400 % 36321901,0 % 1,3381935692400 % 36321901,0 % 1,0 % 1,0 % 1,-3381935692400 % 36321901,0 % 1,0 % 1,0 % 1,0 % 1,1 % 1]
, [-108221942156800 % 524799,108221942156800 % 524799,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,1 % 1]
, [108221942156800 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,1 % 1]
, [0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,1 % 1]
, [108221942156800 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,1 % 1]
]
_M₂ =
[
[0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,-108221942156800 % 524799,0 % 1,0 % 1,108221942156800 % 524799,0 % 1,1 % 1]
, [-169096784620000 % 453365147813277,-838720051715200 % 4987016625946047,6763871384800 % 151121715937759,216443884313600 % 4987016625946047,392304540318400 % 4987016625946047,27055485539200 % 1662338875315349,351721312009600 % 453365147813277,1975050444361600 % 4987016625946047,101458070772000 % 1662338875315349,5221708709065600 % 4987016625946047,1102511035722400 % 4987016625946047,1 % 1]
, [0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,-541109710784 % 95367421875,0 % 1,0 % 1,0 % 1,541109710784 % 95367421875,1 % 1]
, [0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,6763871384800 % 16663069252269,0 % 1,0 % 1,1 % 1]
, [0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,211370980775 % 536346624,0 % 1,0 % 1,0 % 1,1 % 1]
, [3381935692400 % 19061697322899,-3381935692400 % 19061697322899,-3381935692400 % 19061697322899,0 % 1,0 % 1,3381935692400 % 19061697322899,3381935692400 % 19061697322899,0 % 1,0 % 1,-3381935692400 % 19061697322899,0 % 1,1 % 1]
, [0 % 1,-211370980775 % 537394176,0 % 1,211370980775 % 537394176,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,-211370980775 % 537394176,0 % 1,1 % 1]
, [-3381935692400 % 36321901,0 % 1,3381935692400 % 36321901,0 % 1,0 % 1,0 % 1,-3381935692400 % 36321901,0 % 1,0 % 1,0 % 1,0 % 1,1 % 1]
, [-108221942156800 % 524799,108221942156800 % 524799,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,1 % 1]
, [108221942156800 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,1 % 1]
, [0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,1 % 1]
, [0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,108221942156800 % 1,0 % 1,0 % 1,0 % 1,0 % 1,1 % 1]
]
_M₃ =
[
[0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,-108221942156800 % 524799,0 % 1,0 % 1,108221942156800 % 524799,0 % 1,1 % 1]
, [-169096784620000 % 453365147813277,-838720051715200 % 4987016625946047,6763871384800 % 151121715937759,216443884313600 % 4987016625946047,392304540318400 % 4987016625946047,27055485539200 % 1662338875315349,351721312009600 % 453365147813277,1975050444361600 % 4987016625946047,101458070772000 % 1662338875315349,5221708709065600 % 4987016625946047,1102511035722400 % 4987016625946047,1 % 1]
, [0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,-541109710784 % 95367421875,0 % 1,0 % 1,0 % 1,541109710784 % 95367421875,1 % 1]
, [0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,6763871384800 % 16663069252269,0 % 1,0 % 1,1 % 1]
, [0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,211370980775 % 536346624,0 % 1,0 % 1,0 % 1,1 % 1]
, [3381935692400 % 19061697322899,-3381935692400 % 19061697322899,-3381935692400 % 19061697322899,0 % 1,0 % 1,3381935692400 % 19061697322899,3381935692400 % 19061697322899,0 % 1,0 % 1,-3381935692400 % 19061697322899,0 % 1,1 % 1]
, [0 % 1,-211370980775 % 537394176,0 % 1,211370980775 % 537394176,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,-211370980775 % 537394176,0 % 1,1 % 1]
, [-3381935692400 % 36321901,0 % 1,3381935692400 % 36321901,0 % 1,0 % 1,0 % 1,-3381935692400 % 36321901,0 % 1,0 % 1,0 % 1,0 % 1,1 % 1]
, [-108221942156800 % 524799,108221942156800 % 524799,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,1 % 1]
, [108221942156800 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,1 % 1]
, [0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,1 % 1]
, [54110971078400 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,54110971078400 % 1,0 % 1,0 % 1,0 % 1,0 % 1,1 % 1]
]
d₁,d₂,d₃ :: Rational
d₁ = 0 % 1
d₂ = 2399533449150898860018929580106057857312831592024080652407697547921113137254208406108697383229906184194039925435269120000000000000 % 10384619707704007440069688317960727557546629554588436333459508359228638653867
d₃ = -1199766724575449430009464790053028928656415796012040326203848773960556568627104203054348691614953092097019962717634560000000000000 % 10384619707704007440069688317960727557546629554588436333459508359228638653867
test1,test2,test3,test4,test5,test7,test8 :: Matrix Rational
test1 =
[[-169096784620000 % 453365147813277,-838720051715200 % 4987016625946047,6763871384800 % 151121715937759,216443884313600 % 4987016625946047,392304540318400 % 4987016625946047,27055485539200 % 1662338875315349,351721312009600 % 453365147813277,1975050444361600 % 4987016625946047,101458070772000 % 1662338875315349,5221708709065600 % 4987016625946047,1102511035722400 % 4987016625946047,1 % 1],[0 % 1,-135277427696 % 525510452511,-270554855392 % 1732881574809,4328877686272 % 209678670551889,7846090806368 % 209678670551889,5546374535536 % 29954095793127,135277427696 % 247554510687,39501008887232 % 209678670551889,676387138480 % 23297630061321,9604697366416 % 29954095793127,22050220714448 % 209678670551889,66973810188487 % 45384993625950],[0 % 1,16774401034304 % 399540911,270554855392 % 3301991,-4328877686272 % 399540911,-7846090806368 % 399540911,-1623329132352 % 399540911,-135277427696 % 471713,-39501008887232 % 399540911,-6087484246320 % 399540911,-104434174181312 % 399540911,-22050220714448 % 399540911,-64766190245461 % 259442150],[0 % 1,30302143803904 % 101277,-4328877686272 % 174933,-138524085960704 % 5772789,-251074905803776 % 5772789,-17315510745088 % 1924263,-225101639686144 % 524799,-1264032284391424 % 5772789,-21644388431360 % 641421,-3341893573801984 % 5772789,-705607062862336 % 5772789,-2417947450630819 % 4373325],[0 % 1,-536780833097728 % 11,12986633058816 % 1,138524085960704 % 11,251074905803776 % 11,51946532235264 % 11,225101639686144 % 1,1264032284391424 % 11,194799495882240 % 11,3341893573801984 % 11,705607062862336 % 11,7253842365012457 % 25],[0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,-108221942156800 % 524799,0 % 1,0 % 1,108221942156800 % 524799,0 % 1,1 % 1],[0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,-541109710784 % 95367421875,0 % 1,0 % 1,0 % 1,541109710784 % 95367421875,1 % 1],[0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,6763871384800 % 16663069252269,0 % 1,0 % 1,1 % 1],[0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,211370980775 % 536346624,0 % 1,0 % 1,0 % 1,1 % 1],[0 % 1,-211370980775 % 537394176,0 % 1,211370980775 % 537394176,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,-211370980775 % 537394176,0 % 1,1 % 1],[0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,1 % 1],[0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,108221942156800 % 1,0 % 1,0 % 1,0 % 1,0 % 1,1 % 1]]
test2 =
[[-135277427696 % 525510452511,-270554855392 % 1732881574809,4328877686272 % 209678670551889,7846090806368 % 209678670551889,5546374535536 % 29954095793127,135277427696 % 247554510687,39501008887232 % 209678670551889,676387138480 % 23297630061321,9604697366416 % 29954095793127,22050220714448 % 209678670551889,66973810188487 % 45384993625950],[0 % 1,6763871384800 % 119772219,-108221942156800 % 14492438499,-196152270159200 % 14492438499,54110971078400 % 2070348357,-3381935692400 % 17110317,-987525222180800 % 14492438499,-50729035386000 % 4830812833,-432887768627200 % 2070348357,-551255517861200 % 14492438499,-1124184870087 % 125475658],[0 % 1,-108221942156800 % 524799,0 % 1,0 % 1,108221942156800 % 524799,108221942156800 % 524799,0 % 1,0 % 1,-108221942156800 % 524799,0 % 1,1162300833 % 1],[0 % 1,16990844918617600 % 399,3463102149017600 % 399,6276872645094400 % 399,-1731551074508800 % 57,6926204298035200 % 57,31600807109785600 % 399,1623329132352000 % 133,13852408596070400 % 57,17640176571558400 % 399,197878620851139 % 19],[0 % 1,2325080788525 % 9746376192,77573149944425 % 214420276224,-6129758442475 % 107210138112,-8666210211775 % 30631468032,-2325080788525 % 2784678912,-15430081596575 % 53605069056,-1056854903875 % 23824475136,-211370980775 % 239308344,-34453469866325 % 214420276224,-66944106946759 % 29703241728],[0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,-108221942156800 % 524799,0 % 1,0 % 1,108221942156800 % 524799,0 % 1,1 % 1],[0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,-541109710784 % 95367421875,0 % 1,0 % 1,0 % 1,541109710784 % 95367421875,1 % 1],[0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,6763871384800 % 16663069252269,0 % 1,0 % 1,1 % 1],[0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,211370980775 % 536346624,0 % 1,0 % 1,0 % 1,1 % 1],[0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,1 % 1],[0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,108221942156800 % 1,0 % 1,0 % 1,0 % 1,0 % 1,1 % 1]]
test3 = [[6763871384800 % 119772219,-108221942156800 % 14492438499,-196152270159200 % 14492438499,54110971078400 % 2070348357,-3381935692400 % 17110317,-987525222180800 % 14492438499,-50729035386000 % 4830812833,-432887768627200 % 2070348357,-551255517861200 % 14492438499,-1124184870087 % 125475658],[0 % 1,-1731551074508800 % 63500679,-3138436322547200 % 63500679,6385094587251200 % 21166893,-270554855392000 % 524799,-15800403554892800 % 63500679,-270554855392000 % 7055631,-61578285087219200 % 63500679,-8820088285779200 % 63500679,724539378362069 % 641421],[0 % 1,1731551074508800 % 121,3138436322547200 % 121,-6060428760780800 % 121,270554855392000 % 1,15800403554892800 % 121,2434993698528000 % 121,48483430086246400 % 121,8820088285779200 % 121,188875843483779 % 11],[0 % 1,211370980775 % 537394176,0 % 1,-211370980775 % 537394176,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,-178053373 % 80352],[0 % 1,0 % 1,0 % 1,0 % 1,-108221942156800 % 524799,0 % 1,0 % 1,108221942156800 % 524799,0 % 1,1 % 1],[0 % 1,0 % 1,0 % 1,0 % 1,-541109710784 % 95367421875,0 % 1,0 % 1,0 % 1,541109710784 % 95367421875,1 % 1],[0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,6763871384800 % 16663069252269,0 % 1,0 % 1,1 % 1],[0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,211370980775 % 536346624,0 % 1,0 % 1,0 % 1,1 % 1],[0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,1 % 1],[0 % 1,0 % 1,0 % 1,0 % 1,108221942156800 % 1,0 % 1,0 % 1,0 % 1,0 % 1,1 % 1]]
test4 = [[-1731551074508800 % 63500679,-3138436322547200 % 63500679,6385094587251200 % 21166893,-270554855392000 % 524799,-15800403554892800 % 63500679,-270554855392000 % 7055631,-61578285087219200 % 63500679,-8820088285779200 % 63500679,724539378362069 % 641421],[0 % 1,0 % 1,108221942156800 % 1,0 % 1,0 % 1,0 % 1,-108221942156800 % 1,0 % 1,609975477158400 % 1],[0 % 1,-6129758442475 % 8598306816,34030727904775 % 8598306816,-11625403942625 % 1563328512,-15430081596575 % 4299153408,-1056854903875 % 1910734848,-120270088060975 % 8598306816,-34453469866325 % 17196613632,5634017560436093 % 400212099072],[0 % 1,0 % 1,0 % 1,-108221942156800 % 524799,0 % 1,0 % 1,108221942156800 % 524799,0 % 1,1 % 1],[0 % 1,0 % 1,0 % 1,-541109710784 % 95367421875,0 % 1,0 % 1,0 % 1,541109710784 % 95367421875,1 % 1],[0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,6763871384800 % 16663069252269,0 % 1,0 % 1,1 % 1],[0 % 1,0 % 1,0 % 1,0 % 1,211370980775 % 536346624,0 % 1,0 % 1,0 % 1,1 % 1],[0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,1 % 1],[0 % 1,0 % 1,0 % 1,108221942156800 % 1,0 % 1,0 % 1,0 % 1,0 % 1,1 % 1]]
test5 = [[-108221942156800 % 524799,0 % 1,0 % 1,108221942156800 % 524799,0 % 1,1 % 1],[0 % 1,0 % 1,0 % 1,-541109710784 % 95367421875,541109710784 % 95367421875,577984359097 % 577984375000],[0 % 1,0 % 1,0 % 1,108221942156800 % 1,0 % 1,524800 % 1],[0 % 1,0 % 1,6763871384800 % 16663069252269,0 % 1,0 % 1,1 % 1],[0 % 1,211370980775 % 536346624,0 % 1,0 % 1,0 % 1,1 % 1],[0 % 1,0 % 1,0 % 1,0 % 1,0 % 1,1 % 1]]
test7 = [[0 % 1,-541109710784 % 95367421875,541109710784 % 95367421875,577984359097 % 577984375000],[0 % 1,108221942156800 % 1,0 % 1,524800 % 1],[6763871384800 % 16663069252269,0 % 1,0 % 1,1 % 1],[0 % 1,0 % 1,0 % 1,1 % 1]]
test8 = [[-541109710784 % 95367421875,541109710784 % 95367421875,577984359097 % 577984375000],[108221942156800 % 1,0 % 1,524800 % 1],[0 % 1,0 % 1,1 % 1]]