exp-pairs-0.2.1.0: Linear programming over exponent pairs

Copyright (c) Andrew Lelechenko 2014-2020 GPL-3 andrew.lelechenko@gmail.com None Haskell2010

Math.ExpPairs

Description

Linear programming over exponent pairs

Package implements an algorithm to minimize the maximum of a list of rational objective functions over the set of exponent pairs. See full description in A. V. Lelechenko, Linear programming over exponent pairs. Acta Univ. Sapientiae, Inform. 5, No. 2, 271-287 (2013). http://www.acta.sapientia.ro/acta-info/C5-2/info52-7.pdf

A set of useful applications can be found in Math.ExpPairs.Ivic, Math.ExpPairs.Kratzel and Math.ExpPairs.MenzerNowak.

Synopsis

# Documentation

This function takes a list of rational forms and a list of constraints and returns an exponent pair, which satisfies all constraints and minimizes the maximum of all rational forms.

Container for the result of optimization.

Instances
 Source # Instance detailsDefined in Math.ExpPairs Methods Source # Instance detailsDefined in Math.ExpPairs Methods Source # Instance detailsDefined in Math.ExpPairs MethodsshowList :: [OptimizeResult] -> ShowS # Source # Instance detailsDefined in Math.ExpPairs Methodspretty :: OptimizeResult -> Doc ann #prettyList :: [OptimizeResult] -> Doc ann #

The minimal value of objective function.

The initial exponent pair, on which minimal value was achieved.

The sequence of processes, after which minimal value was achieved.

Wrap Rational into OptimizeResult.

Wrap RationalInf into OptimizeResult.

data LinearForm t Source #

Define an affine linear form of three variables: a*k + b*l + c*m. First argument of LinearForm stands for a, second for b and third for c. Linear forms form a monoid by addition.

Instances
 Source # Instance detailsDefined in Math.ExpPairs.LinearForm Methodsfmap :: (a -> b) -> LinearForm a -> LinearForm b #(<$) :: a -> LinearForm b -> LinearForm a # Source # Instance detailsDefined in Math.ExpPairs.LinearForm Methodsfold :: Monoid m => LinearForm m -> m #foldMap :: Monoid m => (a -> m) -> LinearForm a -> m #foldr :: (a -> b -> b) -> b -> LinearForm a -> b #foldr' :: (a -> b -> b) -> b -> LinearForm a -> b #foldl :: (b -> a -> b) -> b -> LinearForm a -> b #foldl' :: (b -> a -> b) -> b -> LinearForm a -> b #foldr1 :: (a -> a -> a) -> LinearForm a -> a #foldl1 :: (a -> a -> a) -> LinearForm a -> a #toList :: LinearForm a -> [a] #null :: LinearForm a -> Bool #length :: LinearForm a -> Int #elem :: Eq a => a -> LinearForm a -> Bool #maximum :: Ord a => LinearForm a -> a #minimum :: Ord a => LinearForm a -> a #sum :: Num a => LinearForm a -> a #product :: Num a => LinearForm a -> a # Source # Instance detailsDefined in Math.ExpPairs.LinearForm Methodstraverse :: Applicative f => (a -> f b) -> LinearForm a -> f (LinearForm b) #sequenceA :: Applicative f => LinearForm (f a) -> f (LinearForm a) #mapM :: Monad m => (a -> m b) -> LinearForm a -> m (LinearForm b) #sequence :: Monad m => LinearForm (m a) -> m (LinearForm a) # Eq t => Eq (LinearForm t) Source # Instance detailsDefined in Math.ExpPairs.LinearForm Methods(==) :: LinearForm t -> LinearForm t -> Bool #(/=) :: LinearForm t -> LinearForm t -> Bool # Num t => Num (LinearForm t) Source # Instance detailsDefined in Math.ExpPairs.LinearForm Methods(+) :: LinearForm t -> LinearForm t -> LinearForm t #(-) :: LinearForm t -> LinearForm t -> LinearForm t #(*) :: LinearForm t -> LinearForm t -> LinearForm t #negate :: LinearForm t -> LinearForm t #abs :: LinearForm t -> LinearForm t #signum :: LinearForm t -> LinearForm t # Show t => Show (LinearForm t) Source # Instance detailsDefined in Math.ExpPairs.LinearForm MethodsshowsPrec :: Int -> LinearForm t -> ShowS #show :: LinearForm t -> String #showList :: [LinearForm t] -> ShowS # Source # Instance detailsDefined in Math.ExpPairs.LinearForm Associated Typestype Rep (LinearForm t) :: Type -> Type # Methodsfrom :: LinearForm t -> Rep (LinearForm t) x #to :: Rep (LinearForm t) x -> LinearForm t # Num t => Semigroup (LinearForm t) Source # Instance detailsDefined in Math.ExpPairs.LinearForm Methods(<>) :: LinearForm t -> LinearForm t -> LinearForm t #sconcat :: NonEmpty (LinearForm t) -> LinearForm t #stimes :: Integral b => b -> LinearForm t -> LinearForm t # Num t => Monoid (LinearForm t) Source # Instance detailsDefined in Math.ExpPairs.LinearForm Methodsmappend :: LinearForm t -> LinearForm t -> LinearForm t #mconcat :: [LinearForm t] -> LinearForm t # NFData t => NFData (LinearForm t) Source # Instance detailsDefined in Math.ExpPairs.LinearForm Methodsrnf :: LinearForm t -> () # (Num t, Eq t, Pretty t) => Pretty (LinearForm t) Source # Instance detailsDefined in Math.ExpPairs.LinearForm Methodspretty :: LinearForm t -> Doc ann #prettyList :: [LinearForm t] -> Doc ann # type Rep (LinearForm t) Source # Instance detailsDefined in Math.ExpPairs.LinearForm type Rep (LinearForm t) = D1 (MetaData "LinearForm" "Math.ExpPairs.LinearForm" "exp-pairs-0.2.1.0-J4IGbuSTVwXCgBqjoU0P5n" False) (C1 (MetaCons "LinearForm" PrefixI False) (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 t) :*: (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 t) :*: S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 t)))) data RationalForm t Source # Define a rational form of two variables, equal to the ratio of two LinearForm. Constructors  (LinearForm t) :/: (LinearForm t) infix 5 Instances  Source # Instance detailsDefined in Math.ExpPairs.LinearForm Methodsfmap :: (a -> b) -> RationalForm a -> RationalForm b #(<$) :: a -> RationalForm b -> RationalForm a # Source # Instance detailsDefined in Math.ExpPairs.LinearForm Methodsfold :: Monoid m => RationalForm m -> m #foldMap :: Monoid m => (a -> m) -> RationalForm a -> m #foldr :: (a -> b -> b) -> b -> RationalForm a -> b #foldr' :: (a -> b -> b) -> b -> RationalForm a -> b #foldl :: (b -> a -> b) -> b -> RationalForm a -> b #foldl' :: (b -> a -> b) -> b -> RationalForm a -> b #foldr1 :: (a -> a -> a) -> RationalForm a -> a #foldl1 :: (a -> a -> a) -> RationalForm a -> a #toList :: RationalForm a -> [a] #null :: RationalForm a -> Bool #length :: RationalForm a -> Int #elem :: Eq a => a -> RationalForm a -> Bool #maximum :: Ord a => RationalForm a -> a #minimum :: Ord a => RationalForm a -> a #sum :: Num a => RationalForm a -> a #product :: Num a => RationalForm a -> a # Source # Instance detailsDefined in Math.ExpPairs.LinearForm Methodstraverse :: Applicative f => (a -> f b) -> RationalForm a -> f (RationalForm b) #sequenceA :: Applicative f => RationalForm (f a) -> f (RationalForm a) #mapM :: Monad m => (a -> m b) -> RationalForm a -> m (RationalForm b) #sequence :: Monad m => RationalForm (m a) -> m (RationalForm a) # Eq t => Eq (RationalForm t) Source # Instance detailsDefined in Math.ExpPairs.LinearForm Methods(==) :: RationalForm t -> RationalForm t -> Bool #(/=) :: RationalForm t -> RationalForm t -> Bool # Num t => Fractional (RationalForm t) Source # Instance detailsDefined in Math.ExpPairs.LinearForm Methods(/) :: RationalForm t -> RationalForm t -> RationalForm t # Num t => Num (RationalForm t) Source # Instance detailsDefined in Math.ExpPairs.LinearForm Methods(+) :: RationalForm t -> RationalForm t -> RationalForm t #(-) :: RationalForm t -> RationalForm t -> RationalForm t #(*) :: RationalForm t -> RationalForm t -> RationalForm t #abs :: RationalForm t -> RationalForm t # Show t => Show (RationalForm t) Source # Instance detailsDefined in Math.ExpPairs.LinearForm MethodsshowsPrec :: Int -> RationalForm t -> ShowS #show :: RationalForm t -> String #showList :: [RationalForm t] -> ShowS # Source # Instance detailsDefined in Math.ExpPairs.LinearForm Associated Typestype Rep (RationalForm t) :: Type -> Type # Methodsfrom :: RationalForm t -> Rep (RationalForm t) x #to :: Rep (RationalForm t) x -> RationalForm t # NFData t => NFData (RationalForm t) Source # Instance detailsDefined in Math.ExpPairs.LinearForm Methodsrnf :: RationalForm t -> () # (Num t, Eq t, Pretty t) => Pretty (RationalForm t) Source # Instance detailsDefined in Math.ExpPairs.LinearForm Methodspretty :: RationalForm t -> Doc ann #prettyList :: [RationalForm t] -> Doc ann # type Rep (RationalForm t) Source # Instance detailsDefined in Math.ExpPairs.LinearForm type Rep (RationalForm t) = D1 (MetaData "RationalForm" "Math.ExpPairs.LinearForm" "exp-pairs-0.2.1.0-J4IGbuSTVwXCgBqjoU0P5n" False) (C1 (MetaCons ":/:" (InfixI NotAssociative 5) False) (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (LinearForm t)) :*: S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (LinearForm t))))

data IneqType Source #

Constants to specify the strictness of Constraint.

Instances
 Source # Instance detailsDefined in Math.ExpPairs.LinearForm Methods Source # Instance detailsDefined in Math.ExpPairs.LinearForm MethodsenumFrom :: IneqType -> [IneqType] #enumFromTo :: IneqType -> IneqType -> [IneqType] # Source # Instance detailsDefined in Math.ExpPairs.LinearForm Methods Source # Instance detailsDefined in Math.ExpPairs.LinearForm Methods(<) :: IneqType -> IneqType -> Bool #(>) :: IneqType -> IneqType -> Bool # Source # Instance detailsDefined in Math.ExpPairs.LinearForm MethodsshowList :: [IneqType] -> ShowS # Source # Instance detailsDefined in Math.ExpPairs.LinearForm Associated Typestype Rep IneqType :: Type -> Type # Methodsto :: Rep IneqType x -> IneqType # Source # Instance detailsDefined in Math.ExpPairs.LinearForm Methodspretty :: IneqType -> Doc ann #prettyList :: [IneqType] -> Doc ann # type Rep IneqType Source # Instance detailsDefined in Math.ExpPairs.LinearForm type Rep IneqType = D1 (MetaData "IneqType" "Math.ExpPairs.LinearForm" "exp-pairs-0.2.1.0-J4IGbuSTVwXCgBqjoU0P5n" False) (C1 (MetaCons "Strict" PrefixI False) (U1 :: Type -> Type) :+: C1 (MetaCons "NonStrict" PrefixI False) (U1 :: Type -> Type))

data Constraint t Source #

A linear constraint of two variables.

Instances
 Source # Instance detailsDefined in Math.ExpPairs.LinearForm Methodsfmap :: (a -> b) -> Constraint a -> Constraint b #(<\$) :: a -> Constraint b -> Constraint a # Source # Instance detailsDefined in Math.ExpPairs.LinearForm Methodsfold :: Monoid m => Constraint m -> m #foldMap :: Monoid m => (a -> m) -> Constraint a -> m #foldr :: (a -> b -> b) -> b -> Constraint a -> b #foldr' :: (a -> b -> b) -> b -> Constraint a -> b #foldl :: (b -> a -> b) -> b -> Constraint a -> b #foldl' :: (b -> a -> b) -> b -> Constraint a -> b #foldr1 :: (a -> a -> a) -> Constraint a -> a #foldl1 :: (a -> a -> a) -> Constraint a -> a #toList :: Constraint a -> [a] #null :: Constraint a -> Bool #length :: Constraint a -> Int #elem :: Eq a => a -> Constraint a -> Bool #maximum :: Ord a => Constraint a -> a #minimum :: Ord a => Constraint a -> a #sum :: Num a => Constraint a -> a #product :: Num a => Constraint a -> a # Source # Instance detailsDefined in Math.ExpPairs.LinearForm Methodstraverse :: Applicative f => (a -> f b) -> Constraint a -> f (Constraint b) #sequenceA :: Applicative f => Constraint (f a) -> f (Constraint a) #mapM :: Monad m => (a -> m b) -> Constraint a -> m (Constraint b) #sequence :: Monad m => Constraint (m a) -> m (Constraint a) # Eq t => Eq (Constraint t) Source # Instance detailsDefined in Math.ExpPairs.LinearForm Methods(==) :: Constraint t -> Constraint t -> Bool #(/=) :: Constraint t -> Constraint t -> Bool # Show t => Show (Constraint t) Source # Instance detailsDefined in Math.ExpPairs.LinearForm MethodsshowsPrec :: Int -> Constraint t -> ShowS #show :: Constraint t -> String #showList :: [Constraint t] -> ShowS # Source # Instance detailsDefined in Math.ExpPairs.LinearForm Associated Typestype Rep (Constraint t) :: Type -> Type # Methodsfrom :: Constraint t -> Rep (Constraint t) x #to :: Rep (Constraint t) x -> Constraint t # NFData t => NFData (Constraint t) Source # Instance detailsDefined in Math.ExpPairs.LinearForm Methodsrnf :: Constraint t -> () # (Num t, Eq t, Pretty t) => Pretty (Constraint t) Source # Instance detailsDefined in Math.ExpPairs.LinearForm Methodspretty :: Constraint t -> Doc ann #prettyList :: [Constraint t] -> Doc ann # type Rep (Constraint t) Source # Instance detailsDefined in Math.ExpPairs.LinearForm type Rep (Constraint t) = D1 (MetaData "Constraint" "Math.ExpPairs.LinearForm" "exp-pairs-0.2.1.0-J4IGbuSTVwXCgBqjoU0P5n" False) (C1 (MetaCons "Constraint" PrefixI False) (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 (LinearForm t)) :*: S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 IneqType)))

Exponent pair built from rational fractions of Corput16, HuxW87b1 and Hux05

data Path Source #

Holds a list of Process and a matrix of projective transformation, which they define.

Instances
 Source # Instance detailsDefined in Math.ExpPairs.Process Methods(==) :: Path -> Path -> Bool #(/=) :: Path -> Path -> Bool # Source # Instance detailsDefined in Math.ExpPairs.Process Methodscompare :: Path -> Path -> Ordering #(<) :: Path -> Path -> Bool #(<=) :: Path -> Path -> Bool #(>) :: Path -> Path -> Bool #(>=) :: Path -> Path -> Bool #max :: Path -> Path -> Path #min :: Path -> Path -> Path # Source # Instance detailsDefined in Math.ExpPairs.Process Methods Source # Instance detailsDefined in Math.ExpPairs.Process MethodsshowsPrec :: Int -> Path -> ShowS #show :: Path -> String #showList :: [Path] -> ShowS # Source # Instance detailsDefined in Math.ExpPairs.Process Associated Typestype Rep Path :: Type -> Type # Methodsfrom :: Path -> Rep Path x #to :: Rep Path x -> Path # Source # Instance detailsDefined in Math.ExpPairs.Process Methods(<>) :: Path -> Path -> Path #stimes :: Integral b => b -> Path -> Path # Source # Instance detailsDefined in Math.ExpPairs.Process Methodsmappend :: Path -> Path -> Path #mconcat :: [Path] -> Path # Source # Instance detailsDefined in Math.ExpPairs.Process Methodspretty :: Path -> Doc ann #prettyList :: [Path] -> Doc ann # type Rep Path Source # Instance detailsDefined in Math.ExpPairs.Process type Rep Path = D1 (MetaData "Path" "Math.ExpPairs.Process" "exp-pairs-0.2.1.0-J4IGbuSTVwXCgBqjoU0P5n" False) (C1 (MetaCons "Path" PrefixI False) (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 ProcessMatrix) :*: S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 [Process])))

data RatioInf t Source #

Extend Ratio t with $$\pm \infty$$ positive and negative infinities.

Constructors

 InfMinus $$- \infty$$ Finite !(Ratio t) Finite value InfPlus $$+ \infty$$
Instances
 Eq t => Eq (RatioInf t) Source # Instance detailsDefined in Math.ExpPairs.RatioInf Methods(==) :: RatioInf t -> RatioInf t -> Bool #(/=) :: RatioInf t -> RatioInf t -> Bool # Integral t => Fractional (RatioInf t) Source # Instance detailsDefined in Math.ExpPairs.RatioInf Methods(/) :: RatioInf t -> RatioInf t -> RatioInf t #recip :: RatioInf t -> RatioInf t # Integral t => Num (RatioInf t) Source # Instance detailsDefined in Math.ExpPairs.RatioInf Methods(+) :: RatioInf t -> RatioInf t -> RatioInf t #(-) :: RatioInf t -> RatioInf t -> RatioInf t #(*) :: RatioInf t -> RatioInf t -> RatioInf t #negate :: RatioInf t -> RatioInf t #abs :: RatioInf t -> RatioInf t #signum :: RatioInf t -> RatioInf t # Integral t => Ord (RatioInf t) Source # Instance detailsDefined in Math.ExpPairs.RatioInf Methodscompare :: RatioInf t -> RatioInf t -> Ordering #(<) :: RatioInf t -> RatioInf t -> Bool #(<=) :: RatioInf t -> RatioInf t -> Bool #(>) :: RatioInf t -> RatioInf t -> Bool #(>=) :: RatioInf t -> RatioInf t -> Bool #max :: RatioInf t -> RatioInf t -> RatioInf t #min :: RatioInf t -> RatioInf t -> RatioInf t # Integral t => Real (RatioInf t) Source # Instance detailsDefined in Math.ExpPairs.RatioInf Methods Show t => Show (RatioInf t) Source # Instance detailsDefined in Math.ExpPairs.RatioInf MethodsshowsPrec :: Int -> RatioInf t -> ShowS #show :: RatioInf t -> String #showList :: [RatioInf t] -> ShowS # (Integral t, Pretty t) => Pretty (RatioInf t) Source # Instance detailsDefined in Math.ExpPairs.RatioInf Methodspretty :: RatioInf t -> Doc ann #prettyList :: [RatioInf t] -> Doc ann #

Arbitrary-precision rational numbers with positive and negative infinities.

pattern K :: (Eq a, Num a) => a -> LinearForm a Source #

For a given c returns linear form c * k

pattern L :: (Eq a, Num a) => a -> LinearForm a Source #

For a given c returns linear form c * l

pattern M :: (Eq a, Num a) => a -> LinearForm a Source #

For a given c returns linear form c * m

(>.) :: Num t => LinearForm t -> LinearForm t -> Constraint t infix 5 Source #

Build a constraint, which states that the value of the first linear form is greater than the value of the second one.

(>=.) :: Num t => LinearForm t -> LinearForm t -> Constraint t infix 5 Source #

Build a constraint, which states that the value of the first linear form is greater or equal to the value of the second one.

(<.) :: Num t => LinearForm t -> LinearForm t -> Constraint t infix 5 Source #

Build a constraint, which states that the value of the first linear form is less than the value of the second one.

(<=.) :: Num t => LinearForm t -> LinearForm t -> Constraint t infix 5 Source #

Build a constraint, which states that the value of the first linear form is less or equal to the value of the second one.

scaleLF :: (Num t, Eq t) => t -> LinearForm t -> LinearForm t Source #

Multiply a linear form by a given coefficient.