Math.ExpPairs

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.

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

Methods

(==) :: OptimizeResult -> OptimizeResult -> Bool

(/=) :: OptimizeResult -> OptimizeResult -> Bool

Ord OptimizeResult

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

Methods

showsPrec :: Int -> OptimizeResult -> ShowS

show :: OptimizeResult -> String

showList :: [OptimizeResult] -> ShowS

Pretty OptimizeResult

Methods

pretty :: OptimizeResult -> Doc

prettyList :: [OptimizeResult] -> Doc

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

Methods

fmap :: (a -> b) -> LinearForm a -> LinearForm b

(<$) :: a -> LinearForm b -> LinearForm a

Foldable 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)

Methods

(==) :: LinearForm t -> LinearForm t -> Bool

(/=) :: LinearForm t -> LinearForm t -> Bool

Num t => Num (LinearForm t)

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)

Methods

showsPrec :: Int -> LinearForm t -> ShowS

show :: LinearForm t -> String

showList :: [LinearForm t] -> ShowS

Generic (LinearForm t)

Associated Types

type Rep (LinearForm t) :: * -> *

Methods

from :: LinearForm t -> Rep (LinearForm t) x

to :: Rep (LinearForm t) x -> LinearForm t

Num t => Monoid (LinearForm t)

Methods

mempty :: LinearForm t

mappend :: LinearForm t -> LinearForm t -> LinearForm t

mconcat :: [LinearForm t] -> LinearForm t

NFData t => NFData (LinearForm t)

Methods

rnf :: LinearForm t -> ()

(Num t, Eq t, Pretty t) => Pretty (LinearForm t)

Methods

pretty :: LinearForm t -> Doc

prettyList :: [LinearForm t] -> Doc

type Rep (LinearForm t)

type Rep (LinearForm t) = D1 (MetaData "LinearForm" "Math.ExpPairs.LinearForm" "exp-pairs-0.1.5.2-50yifXeMqwmGLdyksjZUeY" False) (C1 (MetaCons "LinearForm" PrefixI False) ((:*:) (S1 (MetaSel (Nothing Symbol) NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 t)) ((:*:) (S1 (MetaSel (Nothing Symbol) NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 t)) (S1 (MetaSel (Nothing 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

Methods

fmap :: (a -> b) -> RationalForm a -> RationalForm b

(<$) :: a -> RationalForm b -> RationalForm a

Foldable RationalForm

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)

Methods

(==) :: RationalForm t -> RationalForm t -> Bool

(/=) :: RationalForm t -> RationalForm t -> Bool

Num t => Fractional (RationalForm t)

Methods

(/) :: RationalForm t -> RationalForm t -> RationalForm t

recip :: RationalForm t -> RationalForm t

fromRational :: Rational -> RationalForm t

Num t => Num (RationalForm t)

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)

Methods

showsPrec :: Int -> RationalForm t -> ShowS

show :: RationalForm t -> String

showList :: [RationalForm t] -> ShowS

Generic (RationalForm t)

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)

Methods

rnf :: RationalForm t -> ()

(Num t, Eq t, Pretty t) => Pretty (RationalForm t)

Methods

pretty :: RationalForm t -> Doc

prettyList :: [RationalForm t] -> Doc

type Rep (RationalForm t)

type Rep (RationalForm t) = D1 (MetaData "RationalForm" "Math.ExpPairs.LinearForm" "exp-pairs-0.1.5.2-50yifXeMqwmGLdyksjZUeY" False) (C1 (MetaCons ":/:" (InfixI NotAssociative 5) False) ((:*:) (S1 (MetaSel (Nothing Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (LinearForm t))) (S1 (MetaSel (Nothing Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (LinearForm t)))))

data IneqType

Constants to specify the strictness of Constraint.

Instances

Bounded IneqType

Methods

minBound :: IneqType

maxBound :: IneqType

Enum IneqType

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

Methods

(==) :: IneqType -> IneqType -> Bool

(/=) :: IneqType -> IneqType -> Bool

Ord IneqType

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

Methods

showsPrec :: Int -> IneqType -> ShowS

show :: IneqType -> String

showList :: [IneqType] -> ShowS

Generic IneqType

Associated Types

type Rep IneqType :: * -> *

Methods

from :: IneqType -> Rep IneqType x

to :: Rep IneqType x -> IneqType

Pretty IneqType

Methods

pretty :: IneqType -> Doc

prettyList :: [IneqType] -> Doc

type Rep IneqType

type Rep IneqType = D1 (MetaData "IneqType" "Math.ExpPairs.LinearForm" "exp-pairs-0.1.5.2-50yifXeMqwmGLdyksjZUeY" 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

Methods

fmap :: (a -> b) -> Constraint a -> Constraint b

(<$) :: a -> Constraint b -> Constraint a

Foldable Constraint

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)

Methods

(==) :: Constraint t -> Constraint t -> Bool

(/=) :: Constraint t -> Constraint t -> Bool

Show t => Show (Constraint t)

Methods

showsPrec :: Int -> Constraint t -> ShowS

show :: Constraint t -> String

showList :: [Constraint t] -> ShowS

Generic (Constraint t)

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)

Methods

rnf :: Constraint t -> ()

(Num t, Eq t, Pretty t) => Pretty (Constraint t)

Methods

pretty :: Constraint t -> Doc

prettyList :: [Constraint t] -> Doc

type Rep (Constraint t)

type Rep (Constraint t) = D1 (MetaData "Constraint" "Math.ExpPairs.LinearForm" "exp-pairs-0.1.5.2-50yifXeMqwmGLdyksjZUeY" False) (C1 (MetaCons "Constraint" PrefixI False) ((:*:) (S1 (MetaSel (Nothing Symbol) NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 (LinearForm t))) (S1 (MetaSel (Nothing 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

Methods

(==) :: Path -> Path -> Bool

(/=) :: Path -> Path -> Bool

Ord Path

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

Methods

readsPrec :: Int -> ReadS Path

readList :: ReadS [Path]

readPrec :: ReadPrec Path

readListPrec :: ReadPrec [Path]

Show Path

Methods

showsPrec :: Int -> Path -> ShowS

show :: Path -> String

showList :: [Path] -> ShowS

Generic Path

Associated Types

type Rep Path :: * -> *

Methods

from :: Path -> Rep Path x

to :: Rep Path x -> Path

Monoid Path

Methods

mempty :: Path

mappend :: Path -> Path -> Path

mconcat :: [Path] -> Path

Pretty Path

Methods

pretty :: Path -> Doc

prettyList :: [Path] -> Doc

type Rep Path

type Rep Path = D1 (MetaData "Path" "Math.ExpPairs.Process" "exp-pairs-0.1.5.2-50yifXeMqwmGLdyksjZUeY" False) (C1 (MetaCons "Path" PrefixI False) ((:*:) (S1 (MetaSel (Nothing Symbol) NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 ProcessMatrix)) (S1 (MetaSel (Nothing 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)

Methods

(==) :: RatioInf t -> RatioInf t -> Bool

(/=) :: RatioInf t -> RatioInf t -> Bool

Integral t => Fractional (RatioInf t)

Methods

(/) :: RatioInf t -> RatioInf t -> RatioInf t

recip :: RatioInf t -> RatioInf t

fromRational :: Rational -> RatioInf t

Integral t => Num (RatioInf t)

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)

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)

Methods

toRational :: RatioInf t -> Rational

Show t => Show (RatioInf t)

Methods

showsPrec :: Int -> RatioInf t -> ShowS

show :: RatioInf t -> String

showList :: [RatioInf t] -> ShowS

(Integral t, Pretty t) => Pretty (RatioInf t)

Methods

pretty :: RatioInf t -> Doc

prettyList :: [RatioInf t] -> Doc

type RationalInf = RatioInf Integer

Arbitrary-precision rational numbers with positive and negative infinities.

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

For a given c returns linear form c * k

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

For a given c returns linear form c * l

pattern M :: forall a. (Num a, Eq 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.