Copyright	(c) Andrew Lelechenko 2014-2015
License	GPL-3
Maintainer	andrew.lelechenko@gmail.com
Stability	experimental
Portability	POSIX
Safe Haskell	None
Language	Haskell2010

Math.ExpPairs

Description

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

optimize :: [RationalForm Rational] -> [Constraint Rational] -> OptimizeResult
data OptimizeResult
optimalValue :: OptimizeResult -> RationalInf
optimalPair :: OptimizeResult -> InitPair
optimalPath :: OptimizeResult -> Path
simulateOptimize :: Rational -> OptimizeResult
simulateOptimize' :: RationalInf -> OptimizeResult
data LinearForm t
data RationalForm t = (LinearForm t) :/: (LinearForm t)
data IneqType
data Constraint t
type InitPair = InitPair' Rational
data Path
data RatioInf t
- = InfMinus
- | Finite !(Ratio t)
- | InfPlus
type RationalInf = RatioInf Integer
pattern K :: forall a. (Eq a, Num a) => a -> LinearForm a
pattern L :: forall a. (Eq a, Num a) => a -> LinearForm a
pattern M :: forall a. (Eq a, Num a) => a -> LinearForm a
(>.) :: Num t => LinearForm t -> LinearForm t -> Constraint t
(>=.) :: Num t => LinearForm t -> LinearForm t -> Constraint t
(<.) :: Num t => LinearForm t -> LinearForm t -> Constraint t
(<=.) :: Num t => LinearForm t -> LinearForm t -> Constraint t
scaleLF :: (Num t, Eq t) => t -> LinearForm t -> LinearForm t

Documentation

optimize :: [RationalForm Rational] -> [Constraint Rational] -> OptimizeResult #

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.

data OptimizeResult #

Container for the result of optimization.

Instances

Eq OptimizeResult #
Instance details Defined in Math.ExpPairs Methods (==) :: OptimizeResult -> OptimizeResult -> Bool # (/=) :: OptimizeResult -> OptimizeResult -> Bool #
Ord OptimizeResult #
Instance details Defined in Math.ExpPairs Methods compare :: OptimizeResult -> OptimizeResult -> Ordering # (<) :: OptimizeResult -> OptimizeResult -> Bool # (<=) :: OptimizeResult -> OptimizeResult -> Bool # (>) :: OptimizeResult -> OptimizeResult -> Bool # (>=) :: OptimizeResult -> OptimizeResult -> Bool # max :: OptimizeResult -> OptimizeResult -> OptimizeResult # min :: OptimizeResult -> OptimizeResult -> OptimizeResult #
Show OptimizeResult #
Instance details Defined in Math.ExpPairs Methods showsPrec :: Int -> OptimizeResult -> ShowS # show :: OptimizeResult -> String # showList :: [OptimizeResult] -> ShowS #
Pretty OptimizeResult #
Instance details Defined in Math.ExpPairs Methods pretty :: OptimizeResult -> Doc ann # prettyList :: [OptimizeResult] -> Doc ann #

optimalValue :: OptimizeResult -> RationalInf #

The minimal value of objective function.

optimalPair :: OptimizeResult -> InitPair #

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

optimalPath :: OptimizeResult -> Path #

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

simulateOptimize :: Rational -> OptimizeResult #

Wrap Rational into OptimizeResult.

simulateOptimize' :: RationalInf -> OptimizeResult #

Wrap RationalInf into OptimizeResult.

data LinearForm t #

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

Functor LinearForm #
Instance details Defined in Math.ExpPairs.LinearForm Methods fmap :: (a -> b) -> LinearForm a -> LinearForm b # (<$) :: a -> LinearForm b -> LinearForm a #
Foldable LinearForm #
Instance details Defined in Math.ExpPairs.LinearForm Methods fold :: 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 #
Eq t => Eq (LinearForm t) #
Instance details Defined in Math.ExpPairs.LinearForm Methods (==) :: LinearForm t -> LinearForm t -> Bool # (/=) :: LinearForm t -> LinearForm t -> Bool #
Num t => Num (LinearForm t) #
Instance details Defined 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 # fromInteger :: Integer -> LinearForm t #
Show t => Show (LinearForm t) #
Instance details Defined in Math.ExpPairs.LinearForm Methods showsPrec :: Int -> LinearForm t -> ShowS # show :: LinearForm t -> String # showList :: [LinearForm t] -> ShowS #
Generic (LinearForm t) #
Instance details Defined in Math.ExpPairs.LinearForm Associated Types type Rep (LinearForm t) :: * -> * # Methods from :: LinearForm t -> Rep (LinearForm t) x # to :: Rep (LinearForm t) x -> LinearForm t #
Num t => Semigroup (LinearForm t) #
Instance details Defined 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) #
Instance details Defined in Math.ExpPairs.LinearForm Methods mempty :: LinearForm t # mappend :: LinearForm t -> LinearForm t -> LinearForm t # mconcat :: [LinearForm t] -> LinearForm t #
NFData t => NFData (LinearForm t) #
Instance details Defined in Math.ExpPairs.LinearForm Methods rnf :: LinearForm t -> () #
(Num t, Eq t, Pretty t) => Pretty (LinearForm t) #
Instance details Defined in Math.ExpPairs.LinearForm Methods pretty :: LinearForm t -> Doc ann # prettyList :: [LinearForm t] -> Doc ann #
type Rep (LinearForm t) #
Instance details Defined in Math.ExpPairs.LinearForm type Rep (LinearForm t) = D1 (MetaData "LinearForm" "Math.ExpPairs.LinearForm" "exp-pairs-0.1.6.0-A57bvNSkfW36XePlDuMIT4" 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 #

Define a rational form of two variables, equal to the ratio of two LinearForm.

Constructors

(LinearForm t) :/: (LinearForm t) infix 5

Instances

Functor RationalForm #
Instance details Defined in Math.ExpPairs.LinearForm Methods fmap :: (a -> b) -> RationalForm a -> RationalForm b # (<$) :: a -> RationalForm b -> RationalForm a #
Foldable RationalForm #
Instance details Defined in Math.ExpPairs.LinearForm Methods fold :: 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 #
Eq t => Eq (RationalForm t) #
Instance details Defined in Math.ExpPairs.LinearForm Methods (==) :: RationalForm t -> RationalForm t -> Bool # (/=) :: RationalForm t -> RationalForm t -> Bool #
Num t => Fractional (RationalForm t) #
Instance details Defined in Math.ExpPairs.LinearForm Methods (/) :: RationalForm t -> RationalForm t -> RationalForm t # recip :: RationalForm t -> RationalForm t # fromRational :: Rational -> RationalForm t #
Num t => Num (RationalForm t) #
Instance details Defined in Math.ExpPairs.LinearForm Methods (+) :: RationalForm t -> RationalForm t -> RationalForm t # (-) :: RationalForm t -> RationalForm t -> RationalForm t # (*) :: RationalForm t -> RationalForm t -> RationalForm t # negate :: RationalForm t -> RationalForm t # abs :: RationalForm t -> RationalForm t # signum :: RationalForm t -> RationalForm t # fromInteger :: Integer -> RationalForm t #
Show t => Show (RationalForm t) #
Instance details Defined in Math.ExpPairs.LinearForm Methods showsPrec :: Int -> RationalForm t -> ShowS # show :: RationalForm t -> String # showList :: [RationalForm t] -> ShowS #
Generic (RationalForm t) #
Instance details Defined in Math.ExpPairs.LinearForm Associated Types type Rep (RationalForm t) :: * -> * # Methods from :: RationalForm t -> Rep (RationalForm t) x # to :: Rep (RationalForm t) x -> RationalForm t #
NFData t => NFData (RationalForm t) #
Instance details Defined in Math.ExpPairs.LinearForm Methods rnf :: RationalForm t -> () #
(Num t, Eq t, Pretty t) => Pretty (RationalForm t) #
Instance details Defined in Math.ExpPairs.LinearForm Methods pretty :: RationalForm t -> Doc ann # prettyList :: [RationalForm t] -> Doc ann #
type Rep (RationalForm t) #
Instance details Defined in Math.ExpPairs.LinearForm type Rep (RationalForm t) = D1 (MetaData "RationalForm" "Math.ExpPairs.LinearForm" "exp-pairs-0.1.6.0-A57bvNSkfW36XePlDuMIT4" 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 #

Constants to specify the strictness of Constraint.

Instances

Bounded IneqType #
Instance details Defined in Math.ExpPairs.LinearForm Methods minBound :: IneqType # maxBound :: IneqType #
Enum IneqType #
Instance details Defined in Math.ExpPairs.LinearForm Methods succ :: IneqType -> IneqType # pred :: IneqType -> IneqType # toEnum :: Int -> IneqType # fromEnum :: IneqType -> Int # enumFrom :: IneqType -> [IneqType] # enumFromThen :: IneqType -> IneqType -> [IneqType] # enumFromTo :: IneqType -> IneqType -> [IneqType] # enumFromThenTo :: IneqType -> IneqType -> IneqType -> [IneqType] #
Eq IneqType #
Instance details Defined in Math.ExpPairs.LinearForm Methods (==) :: IneqType -> IneqType -> Bool # (/=) :: IneqType -> IneqType -> Bool #
Ord IneqType #
Instance details Defined in Math.ExpPairs.LinearForm Methods compare :: IneqType -> IneqType -> Ordering # (<) :: IneqType -> IneqType -> Bool # (<=) :: IneqType -> IneqType -> Bool # (>) :: IneqType -> IneqType -> Bool # (>=) :: IneqType -> IneqType -> Bool # max :: IneqType -> IneqType -> IneqType # min :: IneqType -> IneqType -> IneqType #
Show IneqType #
Instance details Defined in Math.ExpPairs.LinearForm Methods showsPrec :: Int -> IneqType -> ShowS # show :: IneqType -> String # showList :: [IneqType] -> ShowS #
Generic IneqType #
Instance details Defined in Math.ExpPairs.LinearForm Associated Types type Rep IneqType :: * -> * # Methods from :: IneqType -> Rep IneqType x # to :: Rep IneqType x -> IneqType #
Pretty IneqType #
Instance details Defined in Math.ExpPairs.LinearForm Methods pretty :: IneqType -> Doc ann # prettyList :: [IneqType] -> Doc ann #
type Rep IneqType #
Instance details Defined in Math.ExpPairs.LinearForm type Rep IneqType = D1 (MetaData "IneqType" "Math.ExpPairs.LinearForm" "exp-pairs-0.1.6.0-A57bvNSkfW36XePlDuMIT4" False) (C1 (MetaCons "Strict" PrefixI False) (U1 :: * -> ) :+: C1 (MetaCons "NonStrict" PrefixI False) (U1 :: -> *))

data Constraint t #

A linear constraint of two variables.

Instances

Functor Constraint #
Instance details Defined in Math.ExpPairs.LinearForm Methods fmap :: (a -> b) -> Constraint a -> Constraint b # (<$) :: a -> Constraint b -> Constraint a #
Foldable Constraint #
Instance details Defined in Math.ExpPairs.LinearForm Methods fold :: 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 #
Eq t => Eq (Constraint t) #
Instance details Defined in Math.ExpPairs.LinearForm Methods (==) :: Constraint t -> Constraint t -> Bool # (/=) :: Constraint t -> Constraint t -> Bool #
Show t => Show (Constraint t) #
Instance details Defined in Math.ExpPairs.LinearForm Methods showsPrec :: Int -> Constraint t -> ShowS # show :: Constraint t -> String # showList :: [Constraint t] -> ShowS #
Generic (Constraint t) #
Instance details Defined in Math.ExpPairs.LinearForm Associated Types type Rep (Constraint t) :: * -> * # Methods from :: Constraint t -> Rep (Constraint t) x # to :: Rep (Constraint t) x -> Constraint t #
NFData t => NFData (Constraint t) #
Instance details Defined in Math.ExpPairs.LinearForm Methods rnf :: Constraint t -> () #
(Num t, Eq t, Pretty t) => Pretty (Constraint t) #
Instance details Defined in Math.ExpPairs.LinearForm Methods pretty :: Constraint t -> Doc ann # prettyList :: [Constraint t] -> Doc ann #
type Rep (Constraint t) #
Instance details Defined in Math.ExpPairs.LinearForm type Rep (Constraint t) = D1 (MetaData "Constraint" "Math.ExpPairs.LinearForm" "exp-pairs-0.1.6.0-A57bvNSkfW36XePlDuMIT4" 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)))

type InitPair = InitPair' Rational #

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

data Path #

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

Instances

Eq Path #
Instance details Defined in Math.ExpPairs.Process Methods (==) :: Path -> Path -> Bool # (/=) :: Path -> Path -> Bool #
Ord Path #
Instance details Defined in Math.ExpPairs.Process Methods compare :: Path -> Path -> Ordering # (<) :: Path -> Path -> Bool # (<=) :: Path -> Path -> Bool # (>) :: Path -> Path -> Bool # (>=) :: Path -> Path -> Bool # max :: Path -> Path -> Path # min :: Path -> Path -> Path #
Read Path #
Instance details Defined in Math.ExpPairs.Process Methods readsPrec :: Int -> ReadS Path # readList :: ReadS [Path] # readPrec :: ReadPrec Path # readListPrec :: ReadPrec [Path] #
Show Path #
Instance details Defined in Math.ExpPairs.Process Methods showsPrec :: Int -> Path -> ShowS # show :: Path -> String # showList :: [Path] -> ShowS #
Generic Path #
Instance details Defined in Math.ExpPairs.Process Associated Types type Rep Path :: * -> * # Methods from :: Path -> Rep Path x # to :: Rep Path x -> Path #
Semigroup Path #
Instance details Defined in Math.ExpPairs.Process Methods (<>) :: Path -> Path -> Path # sconcat :: NonEmpty Path -> Path # stimes :: Integral b => b -> Path -> Path #
Monoid Path #
Instance details Defined in Math.ExpPairs.Process Methods mempty :: Path # mappend :: Path -> Path -> Path # mconcat :: [Path] -> Path #
Pretty Path #
Instance details Defined in Math.ExpPairs.Process Methods pretty :: Path -> Doc ann # prettyList :: [Path] -> Doc ann #
type Rep Path #
Instance details Defined in Math.ExpPairs.Process type Rep Path = D1 (MetaData "Path" "Math.ExpPairs.Process" "exp-pairs-0.1.6.0-A57bvNSkfW36XePlDuMIT4" 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 #

Extends a rational type with positive and negative infinities.

Constructors

InfMinus	Negative infinity
Finite !(Ratio t)	Finite value
InfPlus	Positive infinity

Instances

Eq t => Eq (RatioInf t) #
Instance details Defined in Math.ExpPairs.RatioInf Methods (==) :: RatioInf t -> RatioInf t -> Bool # (/=) :: RatioInf t -> RatioInf t -> Bool #
Integral t => Fractional (RatioInf t) #
Instance details Defined in Math.ExpPairs.RatioInf Methods (/) :: RatioInf t -> RatioInf t -> RatioInf t # recip :: RatioInf t -> RatioInf t # fromRational :: Rational -> RatioInf t #
Integral t => Num (RatioInf t) #
Instance details Defined 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 # fromInteger :: Integer -> RatioInf t #
Integral t => Ord (RatioInf t) #
Instance details Defined in Math.ExpPairs.RatioInf Methods compare :: 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) #
Instance details Defined in Math.ExpPairs.RatioInf Methods toRational :: RatioInf t -> Rational #
Show t => Show (RatioInf t) #
Instance details Defined in Math.ExpPairs.RatioInf Methods showsPrec :: Int -> RatioInf t -> ShowS # show :: RatioInf t -> String # showList :: [RatioInf t] -> ShowS #
(Integral t, Pretty t) => Pretty (RatioInf t) #
Instance details Defined in Math.ExpPairs.RatioInf Methods pretty :: RatioInf t -> Doc ann # prettyList :: [RatioInf t] -> Doc ann #

type RationalInf = RatioInf Integer #

Arbitrary-precision rational numbers with positive and negative infinities.

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

For a given c returns linear form c * k

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

For a given c returns linear form c * l

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

For a given c returns linear form c * m

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

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 #

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 #

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 #

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 #

Multiply a linear form by a given coefficient.