text:
topical media & game development

# Algebraic specification

intro, types, algebra, modules, classes, summary, Q/A, literature

#### Subsections:

Algebraic specification techniques have been developed as a means to specify the design of complex software systems in a formal way. The algebraic approach has been motivated by the notion of information hiding put forward in  [Parnas72a] and the ideas concerning abstraction expressed in  [Ho72]. Historically, the ADJ-group (see Goguen et al., 1978) provided a significant impetus to the algebraic approach by showing that abstract data types may be interpreted as (many sorted) algebras. (In the context of algebraic specifications the notion of sorts has the same meaning as types. We will, however, generally speak of types.) As an example of an algebraic specification, look at the module defining the data type Bool, as given in slide 8-Bool.

Bool

  adt bool is
functions
true : bool
false : bool
and, or : bool * bool -> bool
not : bool -> bool
axioms
[B1]  and(true,x) = x
[B2]  and(false,x) = false
[B3]  not(true) = false
[B4]  not(false) = true
[B5]  or(x,y) = not(and(not(x),not(y)))
end

In this specification two constants are introduced (the zero-ary functions true and false), three functions (respectively and, or and not). The or function is defined by employing not and and, according to a well-known logical law. These functions may all be considered to be (strictly) related to the type bool. Equations are used to specify the desired characteristics of elements of type bool. Obviously, this specification may mathematically be interpreted as (simply) a boolean algebra.

#### Mathematical models

The mathematical framework of algebras allows for a direct characterization of the behavioral aspects of abstract data types by means of equations, provided the specification is consistent. Operationally, this allows for the execution of such specifications by means of term rewriting, provided that some (technical) constraints are met. The model-theoretic semantics of algebraic specifications centers around the notion of initial algebras, which gives us the preferred model of a specification. To characterize the behavior of objects (that may modify their state) in an algebraic way, we need to extend the basic framework of initial algebra models either by allowing so-called multiple world semantics or by making a distinction between hidden and observable sorts (resulting in the notion of an object as an abstract machine). As a remark, in our treatment we obviously cannot avoid the use of some logico-mathematical formalism. If needed, the concepts introduced will be explained on the fly. Where this does not suffice, the interested reader is referred to any standard textbook on mathematical logic for further details.

## Signatures -- generators and observers

intro, types, algebra, modules, classes, summary, Q/A, literature
Abstract data types may be considered as modules specifying the values and functions belonging to the type. In  [Dahl92], a type T is characterized as a tuple specifying the set of elements constituting the type T and the collection of functions related to the type T. Since constants may be regarded as zero-ary functions (having no arguments), we will speak of a signature or defining a particular type T. Also, in accord with common parlance, we will speak of the sorts , which are the sorts (or types) occurring in the declaration of the functions in . See slide 8-signature.

slide: Algebraic specification

A signature specifies the names and (function) profiles of the constants and functions of a data type. In general, the profile of a function is specified as
where are the sorts defining the domain (that is the types of the arguments) of the function f, and s is the sort defining the codomain (or result type) of f. In the case the function f may be regarded as a constant. More generally, when are all unrelated to the type T being defined, we may regard f as a relative constant. Relative constants are values that are assumed to be defined in the context where the specification is being employed. The functions related to a data type T may be discriminated according to their role in defining T. We distinguish between producers , that have the type T under definition as their result type, and observers , that have T as their argument type and deliver a result of a type different from T. In other words, producer functions define how elements of T may be constructed. (In the literature one often speaks of constructors, but we avoid this term because it already has a precisely defined meaning in the object-oriented programming language C++.) In contrast, observer functions do not produce values of T, but give instead information on some particular aspect of T. The signature of a type T is uniquely defined by the union of producer functions and observer functions . Constants of type T are regarded as a subset of the producer functions defining T. Further, we require that the collection of producers is disjoint from the collection of observers for T, that is .

#### Generators

The producer functions actually defining the values of a data type T are called the generator basis of T, or generators of T. The generators of T may be used to enumerate the elements of T, resulting in the collection of T values that is called the generator universe in  [Dahl92]. See slide 8-basis.

slide: Generators -- basis and universe

The generator universe of a type T consists of the closed (that is variable-free) terms that may be constructed using either constants or producer functions of T. As an example, consider the data type Bool with generators t and f. Obviously, the value domain of Bool, the generator universe consists only of the values t and f. As another example, consider the data type Nat (representing the natural numbers) with generator basis , consisting of the constant 0 and the successor function (that delivers the successor of its argument). The terms that may be constructed by is the set , which uniquely corresponds to the natural numbers . (More precisely, the natural numbers are isomorphic with .) In contrast, given a type A with element a, b, ..., the generators of result in a universe that contains terms such as and which we would like to identify, based on our conception of a set as containing only one exemplar of a particular value. To effect this we need additional equations imposing constraints expressing what we consider as the desired shape (or normal form) of the values contained in the universe of T. However, before we look at how to extend a signature defining T with equations defining the (behavioral) properties of T we will look at another example illustrating how the choice of a generator basis may affect the structure of the value domain of a data type. In the example presented in slide 8-Seq, the profiles are given of the functions that may occur in the signature specifying sequences. (The notation _ is used to indicate parameter positions.)

Dependent on which producer functions are selected to generate the universe of T, the correspondence between the generated universe and the intended domain is either one-to-one (as for G and ) or many-to-one (as for ). Since we require our specification to be first-order and finite, infinite generator bases (such as ) must be disallowed, even if they result in a one-to-one correspondence. See  [Dahl92] for further details.

## Equations -- specifying constraints

intro, types, algebra, modules, classes, summary, Q/A, literature
The specification of the signature of a type (which lists the syntactic constraints to which a specification must comply) is in general not sufficient to characterize the properties of the values of the type. In addition, we need to impose semantic constraints (in the form of equations) to define the meaning of the observer functions and (very importantly) to identify the elements of the type domain that are considered equivalent (based on the intuitions one has of that particular type).

slide: Equivalence

Mathematically, the equality predicate may be characterized by the properties listed above, including reflexivity (stating that an element is equal to itself), symmetry (stating that the orientation of the formula is not important) and transitivity (stating that if one element is equal to another and that element is equal to yet another, then the first element is also equal to the latter). In addition, we have the property that, given that two elements are equal, the results of the function applied to them (separately) are also equal. (Technically, the latter property makes a congruence of the equality relation, lifting equality between elements to the function level.) See slide 8-equivalence. Given a suitable set of equations, in addition to a signature, we may identify the elements that can be proved identical by applying the equality relation. In other words, given an equational theory (of which the properties stated above must be a part), we can divide the generator universe of a type T into one or more subsets, each consisting of elements that are equal according to our theory. The subsets of , that is GU factored with respect to equivalence, may be regarded as the abstract elements constituting the type T, and from each subset we may choose a concrete element acting as a representative for the subset which is the equivalence class of the element. Operationally, equations may be regarded as rewrite rules (oriented from left to right), that allow us to transform a term in which a term occurs as a subterm into a term in which is replaced by if . For this procedure to be terminating, some technical restrictions must be met, amounting (intuitively) to the requirement that the right-hand side must in some sense be simpler than the left-hand side. Also, when defining an observer function, we must specify for each possible generator case an appropriate rewriting rule. That is, each observer must be able to give a result for each generator. The example of the natural numbers, given below, will make this clear. Identifying spurious elements by rewriting a term into a canonical form is somewhat more complex, as we will see for the example of sets.

#### Equational theories

To illustrate the notions introduced above, we will look at specifications of some familiar types, namely the natural numbers and sets. In slide 8-Nat, an algebraic specification is given of the natural numbers (as first axiomatized by Peano).

#### Natural numbers

Nat

  functions
0 : Nat
S : Nat -> Nat
mul : Nat * Nat -> Nat
plus : Nat * Nat -> Nat
axioms
[1] plus(x,0) = x
[2] plus(x,Sy) = S(plus(x,y))
[3] mul(x,0) = 0
[4] mul(x,Sy) = plus(mul(x,y),x)
end

In addition to the constant 0 and successor function S we also introduce a function mul for multiplication and a function plus for addition. (The notation Sy stands for application by juxtaposition; its meaning is simply .) The reader who does not immediately accept the specification in slide 8-Nat as an adequate axiomatization of the natural numbers must try to unravel the computation depicted in slide 8-symbolic.
  mul(plus(S 0,S 0),S 0) -[2]->
mul(S(plus(S 0,0)), S 0) -[1]->
mul(SS 0,S 0) -[4]->
plus(mul(SS0,0),SS0) -[3]->
plus(0,SS0) -[2*]-> SS0

slide: Symbolic evaluation

Admittedly, not an easy way to compute with natural numbers, but fortunately term rewriting may, to a large extent, be automated (and actual calculations may be mimicked by semantics preserving primitives). Using the equational theory expressing the properties of natural numbers, we may eliminate the occurrences of the functions mul and plus to arrive (through symbolic evaluation) at something of the form (where n corresponds to the magnitude of the natural number denoted by the term). The opportunity of symbolic evaluation by term rewriting is exactly what has made the algebraic approach so popular for the specification of software, since it allows (under some restrictions) for executable specifications. Since they do not reappear in what may be considered the normal forms of terms denoting the naturals (that are obtained by applying the evaluations induced by the equality theory), the functions plus and mul may be regarded as secondary producers. They are not part of the generator basis of the type Nat. Since we may consider mul and plus as secondary producers at best, we can easily see that when we define mul and plus for the case 0 and Sx for arbitrary x, that we have covered all possible (generator) cases. Technically, this allows us to prove properties of these functions by using structural induction on the possible generator cases. The proof obligation (in the case of the naturals) then is to prove that the property holds for the function applied to 0 and assuming that the property holds for applying the function to x, it also holds for Sx. As our next example, consider the algebraic specification of the type in slide 8-Set.

Set

#### Axioms

In the case of sets we have the problem that we do not start with a one-to-one generator base as we had with the natural numbers. Instead, we have a many-to-one generator base, so we need equality axioms to eliminate spurious elements from the (generator) universe of sets.

slide: Equivalence classes for Set

The equivalence classes of (which is factored by the equivalence relation), each have multiple elements (except the class representing the empty set). To select an appropriate representative from each of these classes (representing the abstract elements of the type ) we need an ordering on terms, so that we can take the smaller term as its canonical representation. See slide 8-set-equi.

## Initial algebra semantics

intro, types, algebra, modules, classes, summary, Q/A, literature
In the previous section we have given a rather operational characterization of the equivalence relation induced by the equational theory and the process of term rewriting that enables us to purge the generator universe of a type, by eliminating redundant elements. However, what we actually strive for is a mathematical model that captures the meaning of an algebraic specification. Such a model is provided (or rather a class of such models) by the mathematical structures known as (not surprisingly) algebras. A single sorted algebra is a structure where A is a set of values, and specifies the signature of the functions operating on A. A multi-sorted algebra is a structure where S is a set of sort names and the set of values belonging to the sort s. The set S may be ordered (in which case the ordering indicates the subtyping relationships between the sorts). We call the (multi-sorted) structure a .

slide: Interpretations and models

Having a notion of algebras, we need to have a way in which to relate an algebraic specification to such a structure. To this end we define an interpretation which maps closed terms formed by following the rules given in the specification to elements of the structure . We may extend the interpretation eval to include variables as well (which we write as ), but then we also need to assume that an assignment is given, such that when applying to a term t the result is free of variables, otherwise no interpretation in exists. See slide 8-algebra.

#### Interpretations

As an example, consider the interpretations of the specification of Bool and the specification of Nat, given in slide 8-B-N.

slide: Interpretations of Bool and Nat

The structure given above is simply a boolean algebra, with the operators , and . The functions not, and and or naturally map to their semantic counterparts. In addition, we assume that the constants true and false map to the elements tt and ff. As another example, look at the structure and the interpretation , which maps the functions S, mul and plus specified in Nat in a natural way. However, since we have also given equations for Nat (specifying how to eliminate the functions mul and plus) we must take precautions such that the requirement

is satisfied if the structure is to count as an adequate model of Nat. The requirement above states that whenever equality holds for two interpreted terms (in ) then these terms must also be provably equal (by using the equations given in the specification of Nat), and vice versa. As we will see illustrated later, many models may exist for a single specification, all satisfying the requirement of adequacy. The question is, do we have a means to select one of these models as (in a certain sense) the best model. The answer is yes. These are the models called initial models.

#### Initial models

A model (in a mathematical sense) represents the meaning of a specification in a precise way. A model may be regarded as stating a commitment with respect to the interpretation of the specification. An initial model is intuitively the least committing model, least committing in the sense that it imposes only identifications made necessary by the equational theory of a specification. Technically, an initial model is a model from which every other model can be derived by an algebraic mapping which is a homomorphism.

slide: Initial models

The starting point for the construction of an initial model for a given specification with signature is to construct a term algebra with the terms that may be generated from the signature as elements. The next step is then to factor the universe of generated terms into equivalence classes, such that two terms belong to the same class if they can be proven equivalent with respect to the equational theory of the specification. We will denote the representative of the equivalence class to which a term t belongs by . Hence (in the model) iff . So assume that we have constructed a structure then; finally, we must define an interpretation, say , that assigns closed terms to appropriate terms in the term model (namely the representatives of the equivalence class of that term). Hence, the interpretation of a function f in the structure is such that

where is the interpretation of f in . In other words, the result of applying to terms belongs to the same equivalence class as the result of applying to the representatives of the equivalence classes of . See slide 8-initial. An initial algebra model has two important properties, known respectively as the no junk and no confusion properties. The no junk property states that for each element of the model there is some term for which the interpretation in is equal to that element. (For the model this is simply a representative of the equivalence class corresponding with the element.) The no confusion property states that if equality of two terms can be proven in the equational theory of the specification, then the equality also holds (semantically) in the model, and vice versa. The no confusion property means, in other words, that sufficiently many identifications are made (namely those that may be proven to hold), but no more than that (that is, no other than those for which a proof exists). The latter property is why we may speak of an initial model as the least committing model; it simply gives no more meaning than is strictly needed. The initial model constructed from the term algebra of a signature is intuitively a very natural model since it corresponds directly with (a subset of) the generator universe of . Given such a model, other models may be derived from it simply by specifying an appropriate interpretation. For example, when we construct a model for the natural numbers (as specified by Nat) consisting of the generator universe and the operators (which are defined as , and ) we may simply derive from this model the structure for which the operations have their standard arithmetical meaning. Actually, this structure is also an initial model for Nat, since we may also make the inverse transformation. More generally, when defining an initial model only the structural aspects (characterizing the behavior of the operators) are important, not the actual contents. Technically, this means that initial models are defined up to isomorphism, that is a mapping to equivalent models with perhaps different contents but an identical structure. Not in all cases is a structure derived from an initial model itself also an initial model, as shown in the example below.

#### Example

Consider the specification of Bool as given before. For this specification we have given the structure and the interpretation which defines an initial model for Bool. (Check this!)

slide: Structure and interpretation

We may, however, also use the structure to define an interpretation of Nat. See slide 8-structure. The interpretation is such that , , and , where . The reader may wish to ponder on what this interpretation effects. The answer is that it interprets Nat as specifying the naturals modulo 2, which discriminates only between odd and even numbers. Clearly, this interpretation defines not an initial model, since it identifies all odd numbers with ff and all even numbers with tt. Even if we replace ff by 0 and tt by 1, this is not what we generally would like to commit ourselves to when we speak about the natural numbers, simply because it assigns too much meaning.

## Objects as algebras

intro, types, algebra, modules, classes, summary, Q/A, literature
The types for which we have thus far seen algebraic specifications (including Bool, Seq, Set and Nat) are all types of a mathematical kind, which (by virtue of being mathematical) define operations without side-effects. Dynamic state changes, that is side-effects, are often mentioned as determining the characteristics of objects in general. In the following we will explore how we may deal with assigning meaning to dynamic state changes in an algebraic framework. Let us look first at the abstract data type stack. The type stack may be considered as one of the real life' types in the world of programming. See slide 8-Stack.

#### Abstract Data Type -- applicative

Stack

  functions
new : stack;
push : element * stack  -> stack;
empty : stack -> boolean;
pop : stack -> stack;
top : stack -> element;
axioms
empty( new ) = true
empty( push(x,s) ) = false
top( push(x,s) ) = x
pop( push(x,s) ) = s
preconditions
pre: pop( s : stack ) = not empty(s)
pre: top( s : stack ) = not empty(s)
end

Above, a stack has been specified by giving a signature (consisting of the functions new, push, empty, pop and top). In addition to the axioms characterizing the behavior of the stack, we have included two pre-conditions to test whether the stack is empty in case pop or top is applied. The pre-conditions result in conditional axioms for the operations pop and top. Conditional axioms, however, do preserve the initial algebra semantics. The specification given above is a maximally abstract description of the behavior of a stack. Adding more implementation detail would disrupt its nice applicative structure, without necessarily resulting in different behavior (from a sufficiently abstract perspective). The behavior of elements of abstract data types and objects is characterized by state changes. State changes may affect the value delivered by observers or methods. Many state changes (such as the growing or shrinking of a set, sequence or stack) really are nothing but applicative transformations that may mathematically be described by the input-output behavior of an appropriate function. An example in which the value of an object on some attribute is dependent on the history of the operations applied to the object, instead of the structure of the object itself (as in the case of a stack) is the object account, as specified in slide 8-account. The example is taken from  [Goguen].

#### Dynamic state changes -- objects

account

  object account is
functions
bal : account -> money
methods
credit : account * money -> account
debit : account * money -> account
error
overdraw : money -> money
axioms
bal(new(A)) = 0
bal(credit(A,M)) = bal(A) + M
bal(debit(A,M)) = bal(A) - M if bal(A) >= M
error-axioms
bal(debit(A,M)) = overdraw(M) if bal(A) < M
end

slide: The algebraic specification of an account

An account object has one attribute function (called bal) that delivers the amount of money that is (still) in the account. In addition, there are two method functions, credit and debit that may respectively be used to add or withdraw money from the account. Finally, there is one special error function, overdraw, that is used to define the result of balance when there is not enough money left to grant a debit request. Error axioms are needed whenever the proper axioms are stated conditionally, that is contain an if expression. The conditional parts of the axioms, including the error axioms, must cover all possible cases. Now, first look at the form of the axioms. The axioms are specified as $fn\left(method\left(Object,Args\right)\right) = expr$ where fn specifies an attribute function (bal in the case of account) and method a method (either new, which is used to create new accounts, credit or debit). By convention, we assume that $method\left(Object,...\right) = Object$, that is that a method function returns its first argument. Applying a method thus results in redefining the value of the function fn. For example, invoking the method $credit\left(acc,10\right)$ for the account acc results in modifying the function bal to deliver the value $bal\left(acc\right) + 10$ instead of simply $bal\left(acc\right)$. In the example above, the axioms define the meaning of the function bal with respect to the possible method applications. It is not difficult to see that these operations are of a non-applicative nature, non-applicative in the sense that each time a method is invoked the actual definition of bal is changed. The change is necessary because, in contrast to, for example, the functions employed in a boolean algebra, the actual value of the account may change in time in a completely arbitrary way. A first order framework of (multi sorted) algebras is not sufficiently strong to define the meaning of such changes. What we need may be characterized as a multiple world semantics, where each world corresponds to a possible state of the account. As an alternative semantics we will also discuss the interpretation of an object as an abstract machine, which resembles an (initial) algebra with hidden sorts.

#### Multiple world semantics

From a semantic perspective, an object that changes its state may be regarded as moving from one world to another, when we see a world as representing a particular state of affairs. Take for example an arbitrary (say John's) account, which has a balance of 500. We may express this as $balance\left(accountJohn\right) = 500$. Now, when we invoke the method credit, as in $credit\left(accountJohn, 200\right)$, then we expect the balance of the account to be raised to 700. In the language of the specification, this is expressed as $bal\left(credit\left(accountJohn,200\right)\right) = bal\left(accountJohn\right) + 200$ Semantically, the result is a state of affairs in which $bal\left(accountJohn\right) = 700$. In  [Goguen] an operational interpretation is given of a multiple world semantics by introducing a database D (that stores the values of the attribute functions of objects as first order terms) which is transformed as the result of invoking a method, into a new database $D\text{'}$ (that has an updated value for the attribute function modified by the method). The meaning of each database (or world) may be characterized by an algebra and an interpretation as before. The rules according to which transformations on a database take place may be formulated as in slide 8-multiple.

slide: The interpretation of change

The first rule (attribute) describes how attribute functions are evaluated. Whenever a function f with arguments evaluates to a value (or expression) v, then the term may be replaced by v without affecting the database D. (We have simplified the treatment by omitting all aspects having to do with matching and substitutions, since such details are not needed to understand the process of symbolic evaluation in a multiple world context.) The next rule (method) describes the result of evaluating a method. We assume that invoking the method changes the database D into $D\text{'}$. Recall that, by convention, a method returns its first argument. Finally, the last rule (composition) describes how we may glue all this together. No doubt, the reader needs an example to get a picture of how this machinery actually works.

#### Example - a counter object

  object ctr is    ctr
function n : ctr -> nat
method incr : ctr -> ctr
axioms
n(new(C)) = 0
n(incr(C)) = n(C) + 1
end

slide: The object ctr

In slide 8-ctr, we have specified a simple object ctr with an attribute function value (delivering the value of the counter) and a method function incr (that may be used to increment the value of the counter).

#### Abstract evaluation

  <n(incr(incr(new(C)))),{ C }> -[new]->
<n(incr(incr(C))),{ C[n:=0] }> -[incr]->
<n(incr(C)),{ C[n:=1] }> -[incr]->
<n(C), { C[n:=2] }> -[n]->
<2, { C[n:=2] }>
`

slide: An example of abstract evaluation

The end result of the evaluation depicted in slide 8-ctr-evl is the value 2 and a context (or database) in which the value of the counter C is (also) 2. The database is modified in each step in which the method incr is applied. When the attribute function value is evaluated the database remains unchanged, since it is merely consulted.

#### Objects as abstract machines

Multiple world semantics provide a very powerful framework in which to define the meaning of object specifications. Yet, as illustrated above, the reasoning involved has a very operational flavor and lacks the appealing simplicity of the initial algebra semantics given for abstract data types. As an alternative,  [Goguen] propose an interpretation of objects (with dynamic state changes) as abstract machines. Recall that an initial algebra semantics defines a model in which the elements are equivalence classes representing the abstract values of the data type. In effect, initial models are defined only up to isomorphism (that is, structural equivalence with similar models). In essence, the framework of initial algebra semantics allows us to abstract from the particular representation of a data type, when assigning meaning to a specification. From this perspective it does not matter, for example, whether integers are represented in binary or decimal notation. The notion of abstract machines generalizes the notion of initial algebras in that it loosens the requirement of (structural) isomorphism, to allow for what we may call behavioral equivalence. The idea underlying the notion of behavioral equivalence is to make a distinction between visible sorts and hidden sorts and to look only at the visible sorts to determine whether two algebras $|A$ and $|B$ are behaviorally equivalent. According to  [Goguen], two algebras $|A$ and $|B$ are behaviorally equivalent if and only if the result of evaluating any expression of a visible sort in $|A$ is the same as the result of evaluating that expression in $|B$. Now, an abstract machine (in the sense of Goguen and Meseguer, 1986) is simply the equivalence class of behaviorally equivalent algebras, or in other words the maximally abstract characterization of the visible behavior of an abstract data type with (hidden) states. The notion of abstract machines is of particular relevance as a formal framework to characterize the (implementation) refinement relation between objects. For example, it is easy to determine that the behavior of a stack implemented as a list is equivalent to the behavior of a stack implemented by a pointer array, whereas these objects are clearly not equivalent from a structural point of view. Moreover, the behavior of both conform (in an abstract sense) with the behavior specified in an algebraic way. Together, the notions of abstract machine and behavioral equivalence provide a formalization of the notion of information hiding in an algebraic setting. In the chapters that follow we will look at alternative formalisms to explain information hiding, polymorphism and behavioral refinement.

(C) Æliens 04/09/2009

You may not copy or print any of this material without explicit permission of the author or the publisher. In case of other copyright issues, contact the author.


text:
# Article

Full entry | PDF   (0.3 MB)
Keywords:
functional differential equation; functional (nondifferential) equation; advanced argument; asymptotic behaviour
Summary:
The paper discusses the asymptotic properties of solutions of the scalar functional differential equation $y^{\prime }(x)=ay(\tau (x))+by(x),\qquad x\in [x_0,\infty )$ of the advanced type. We show that, given a specific asymptotic behaviour, there is a (unique) solution $y(x)$ which behaves in this way.
References:
[1] J. Čermák: The asymptotic bounds of linear delay systems. J. Math. Anal. Appl. 225 (1998), 373–388. DOI 10.1006/jmaa.1998.6018 | MR 1644331
[2] J. Diblík: Asymptotic representation of solutions of equation $\dot{y}(t)=\beta (t)[y(t)-y(t-\tau (t))]$. J. Math. Anal. Appl. 217 (1998), 200–215. DOI 10.1006/jmaa.1997.5709 | MR 1492085
[3] J. K. Hale and S. M. Verduyn Lunel: Functional Differential Equations. Springer-Verlag, New York, 1993.
[4] M. L. Heard: Asymptotic behavior of solutions of the functional differential equation $x^{\prime }(t)=ax(t)+bx(t^{\alpha })$, $\alpha >1$. J. Math. Anal. Appl. 44 (1973), 745–757. DOI 10.1016/0022-247X(73)90013-9 | MR 0333405 | Zbl 0289.34115
[5] M. L. Heard: A change of variables for functional differential equations. J. Differential Equations 18 (1975), 1–10. DOI 10.1016/0022-0396(75)90076-5 | MR 0387766 | Zbl 0318.34069
[6] T. Kato and J. B. Mcleod: The functional differential equation $y^{\prime }(x)=ay(\lambda x)+by(x)$. Bull. Amer. Math. Soc. 77 (1971), 891–937. MR 0283338
[7] M. Kuczma, B. Choczewski and R. Ger: Iterative Functional Equations. Encyclopedia of Mathematics and its Applications, Cambridge University Press, 1990. MR 1067720
[8] G. S. Ladde, V. Lakshmikantham and B. G. Zhang: Oscillation Theory of Differential Equations with Deviating Argument. Marcel Dekker, Inc., New York, 1987. MR 1017244
[9] F. Neuman: On transformations of differential equations and systems with deviating argument. Czechoslovak Math. J. 31(106) (1981), 87–90. MR 0604115 | Zbl 0463.34051
[10] F. Neuman: Transformations and canonical forms of functional-differential equations. Proc. Roy. Soc. Edinburgh 115A (1990), 349–357. MR 1069527
[11] V. A. Staikos and P. Ch. Tsamatos: On the terminal value problem for differential equations with deviating arguments. Arch. Math. (Brno) (1985), 43–49. MR 0818306

Partner of

format: plain


text:
F01 Chapter Contents
F01 Chapter Introduction
NAG Library Manual

Note:  before using this routine, please read the Users' Note for your implementation to check the interpretation of bold italicised terms and other implementation-dependent details.

## 1  Purpose

F01ADF calculates the approximate inverse of a real symmetric positive definite matrix, using a Cholesky factorization.

## 2  Specification

 SUBROUTINE F01ADF ( N, A, LDA, IFAIL)
 INTEGER N, LDA, IFAIL REAL (KIND=nag_wp) A(LDA,*)

## 3  Description

To compute the inverse $X$ of a real symmetric positive definite matrix $A$, F01ADF first computes a Cholesky factorization of $A$ as $A=L{L}^{\mathrm{T}}$, where $L$ is lower triangular. It then computes ${L}^{-1}$ and finally forms $X$ as the product ${L}^{-\mathrm{T}}{L}^{-1}$.

## 4  References

Wilkinson J H and Reinsch C (1971) Handbook for Automatic Computation II, Linear Algebra Springer–Verlag

## 5  Parameters

1:     N – INTEGERInput
On entry: $n$, the order of the matrix $A$.
Constraint: ${\mathbf{N}}\ge 0$.
2:     A(LDA,$*$) – REAL (KIND=nag_wp) arrayInput/Output
Note: the second dimension of the array A must be at least $\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{N}}\right)$.
On entry: the upper triangle of the $n$ by $n$ positive definite symmetric matrix $A$. The elements of the array below the diagonal need not be set.
On exit: the lower triangle of the inverse matrix $X$ is stored in the elements of the array below the diagonal, in rows $2$ to $n+1$; ${x}_{ij}$ is stored in ${\mathbf{A}}\left(i+1,j\right)$ for $i\ge j$. The upper triangle of the original matrix is unchanged.
3:     LDA – INTEGERInput
On entry: the first dimension of the array A as declared in the (sub)program from which F01ADF is called.
Constraint: ${\mathbf{LDA}}\ge {\mathbf{N}}+1$.
4:     IFAIL – INTEGERInput/Output
On entry: IFAIL must be set to $0$, $-1\text{ or }1$. If you are unfamiliar with this parameter you should refer to Section 3.3 in the Essential Introduction for details.
For environments where it might be inappropriate to halt program execution when an error is detected, the value $-1\text{ or }1$ is recommended. If the output of error messages is undesirable, then the value $1$ is recommended. Otherwise, if you are not familiar with this parameter, the recommended value is $0$. When the value $-\mathbf{1}\text{ or }\mathbf{1}$ is used it is essential to test the value of IFAIL on exit.
On exit: ${\mathbf{IFAIL}}={\mathbf{0}}$ unless the routine detects an error or a warning has been flagged (see Section 6).

## 6  Error Indicators and Warnings

If on entry ${\mathbf{IFAIL}}={\mathbf{0}}$ or $-{\mathbf{1}}$, explanatory error messages are output on the current error message unit (as defined by X04AAF).
Errors or warnings detected by the routine:
${\mathbf{IFAIL}}=1$
The matrix $A$ is not positive definite, possibly due to rounding errors.
${\mathbf{IFAIL}}=2$
 On entry, ${\mathbf{N}}<0$, or ${\mathbf{LDA}}<{\mathbf{N}}+1$.

## 7  Accuracy

The accuracy of the computed inverse depends on the conditioning of the original matrix. For a detailed error analysis see page 39 of Wilkinson and Reinsch (1971).

The time taken by F01ADF is approximately proportional to ${n}^{3}$. F01ADF calls routines F07FDF (DPOTRF) and F07FJF (DPOTRI) from LAPACK.

## 9  Example

This example finds the inverse of the $4$ by $4$ matrix:
 $5 7 6 5 7 10 8 7 6 8 10 9 5 7 9 10 .$


text:
, 24.01.2020thebrain1345

# 1. unit 2: credit cards and large purchases consumers are often faced with making large purchases to satisfy life's basic needs. if your refrigerator breaks and you don't have much disposable income, you might turn to credit. describe who benefits from a credit agreement and how. why are businesses and institutions willing to offer you credit? explain.

step-by-step explanation:

since, in the linear regression formula, the slope is the a in the equation y = b + ax ( by comparing it with the general equation of line y = mx + c )

where,

here given table is,

price (\$), x   :           18         23       25       29       30       33

pairs sold, y :         16         13         10       8         6       2

so, ,   ,   ,

and   ,

thus, slop of the given line is,

⇒

⇒   ≈ 33

well what did you do it matters what you did : )

step-by-step explanation:

find the magnitude of the trig term

csc

(

x

)

1

by taking the absolute value of the coefficient.

1

find the lower bound of the range.

tap for more

y

=

2

find the upper bound of the range.

tap for more

y

=

0

the range is

y

2

or

y

0

.

(

,

2

]

[

0

,

)

{

y

|

y

2

,

y

0

}

step-by-step explanation:

2 over 5

step-by-step explanation:

the 2: 3 ratio is the length of the ac segment to the cb segment total length. this implies that the ratio between segment ac length and segment ab length is 2: 5. point c is 2/5 from a to b, so the required fraction is 2/5.

### Other questions on the subject: Mathematics

Mathematics, 21.06.2019, rafamoreura
Look at the picture. A, C, D, K....Read More
Mathematics, 21.06.2019, ur4286
Step-by-step explanation:Since ΔJKL is similar to ΔMNP, the ratio of the corresponding sides will be in the same proportion;This implies that;We substitute the given length to obta...Read More


text:
# Maximum length subarray with LCM equal to product in C++

C++Server Side ProgrammingProgramming

Suppose we have an array A. We have to find the maximum length of the subarray, whose LCM is the same as the product of the elements of that subarray. If that kind of subarray is not found, then return -1. Suppose array is {6, 10, 21}, then the length is 2, as the subarray {10, 21} is there, whose LCM is 210, and the product is also 210.

The approach is straight forward. We have to check every possible subarray of length greater or equals to 2. If the subarray is satisfying the condition, then update the answer as a maximum of answer and length of sub-array.

## Example

Live Demo

#include <iostream>
using namespace std;
int gcd(int a, int b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
int maxLengthLCMSubarray(int arr[], int n) {
int len = -1;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
long long lcm = 1LL * arr[i];
long long product = 1LL * arr[i];
for (int k = i + 1; k <= j; k++) {
lcm = (((arr[k] * lcm)) / (gcd(arr[k], lcm)));
product = product * arr[k];
}
if (lcm == product) {
len = max(len, j - i + 1);
}
}
}
return len;
}
int main() {
int arr[] = {8, 2, 6, 10, 13, 21, 7};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Maximum Length: " << maxLengthLCMSubarray(arr, n);
}

## Output

Maximum Length: 3
Published on 21-Oct-2019 07:04:32


text:
## IB Maths HL Vectors, perpendicular

Discussions for the Core part of the syllabus. Algebra, Functions and equations, Circular functions and trigonometry, Vectors, Statistics and probability, Calculus. IB Maths HL Revision Notes

### IB Maths HL Vectors, perpendicular

IB Mathematics HL – Vectors, Scalar Product, perpendicular vectors

How can we find the value of the parameter c for which the vectors $a= \begin{pmatrix} c \\ 2c \\ 4 \end{pmatrix}$ and $b= \begin{pmatrix} 3 \\ -2 \\ 5 \end{pmatrix}$ are perpendicular?

Thanks
elizabeth

Posts: 0
Joined: Mon Jan 28, 2013 8:09 pm

### Re: IB Maths HL Vectors, perpendicular

IB Mathematics HL – Vectors, dot Product, perpendicular vectors

We know that two vectors are perpendicular if and only their dot product equals zero.

Therefore

$a \cdot b=(c \cdot 3) + (2c \cdot (-2)) + (4 \cdot 5) =3c- 4c+20=0$

$\Rightarrow c= 20$

Hope these help!
miranda

Posts: 268
Joined: Mon Jan 28, 2013 8:03 pm

### IB Mathematics HL Vectors, perpendicular

Thanks miranda!!
elizabeth

Posts: 0
Joined: Mon Jan 28, 2013 8:09 pm


text: Solve Cubic Equation In Excel Vba Tessshlo. But any or all of b, c and d can be zero. Algebra Tutorials! Some believe that factoring is a good way to go, but what if you have a quadratic equation that isn’t factorable? Oct 20th 2005 #1; Hello, I'm using Excel 2000. We don't need a general coefficient for the … Solve cubic equations or 3rd Order Polynomials. Pick an initial guess for V0 (eg – 0, Vig, etc.) In this article, we will take you through how to use “Solver” in VBA. Want to know how to solve a quadratic equation faster? In fact, it is easier to do it in MS Excel as you just enter the values into the cells rather than having to create the text boxes. and evaluate: V1 = -(1/C) (A V0 3 + B V0 2 + D) 3.) Goal Seek. The APMonitor Modeling Language is optimization software for mixed-integer and differential algebraic equations. The formula manages to solve simple cases such as f(x) = 2x3 + 3x2 – 11x – 6 = 0 or f(x) = x3 – 7x2 + 4x + 12 but I recently combined my calculator with other code to solve much more complicated ones, where a = 1 b = -0.947027753 c = … Gerolamo Cardano published a method to … This is an essential tutorial for mathematics and engineering students that will assist in solving even larger … This subroutine is actually a Function, and therefore it returns a value to the calling subroutine.In this case, it returns the value of the cubic equation we're considering for this example. In a cubic equation, the highest exponent is 3, the equation has 3 solutions/roots, and the equation itself takes the form + + + =. HELP FORUMS. If $\Delta > 0$, then the cubic equation has one real and two complex conjugate roots; if $\Delta = 0$, then the equation has three real roots, whereby at least two roots are equal; if $\Delta < 0$ then the equation has three distinct real roots. Solving roots of cubic equation. Che141 Cubic Equations Of State Fs2018 You. OzGrid Free Excel/VBA Help Forum. 2. Xseos An Open For Chemical Engineering Cache. Solving Equations In Excel Polynomial Cubic Quadratic Linear. Beginner. How can we solve this equation using Excel? Does Excel Have A Function … The examples of cubic equations are, 3 x 3 + … The quadratic functions usually have a structure like ax² + bx + c = 0, where x represents an unknown … Download Cardano.zip - 62.1 KB; Cardano's Method. Goal Seek is among Excel’s most important features. It is called quadratic because quad means square in Latin. Cell range C3:C5 contains three equations with variables x, y and z. Search; Code Directory ASP ASP.NET C/C++ CFML CGI/PERL Delphi Development Flash HTML Java JavaScript Pascal PHP Python SQL Tools Visual Basic & VB.NET XML: … I did its fitting using Excel and got an equation. What's even cooler is that you can use these tools directly in VBA code, without ever having to manually open their respective windows, click cells, and so on. The image above shows how to solve three simultaneous equations with three variables using one Excel formula. OzGrid Free Excel/VBA Help Forum. REINFORCED CONCRETE HIGH-RISE BUILDINGS Dr. Kutlu Darılmaz Solving Cubic Equations in Excel For this example let the polynomial be f(x) 4x 383 6x 92222 x 491 40 0 The coefficients of a, b, c, and d are real or complex numbers with a not equals to zero (a ≠ 0). Excel General. In this guide, we are going to show you a different approach to solving quadratic equations in Excel using formulas and VBA. It must have the term x 3 in it, or else it will not be a cubic equation. Although there are several approaches for solving cubic equations with paper and pencil, none are computationally easy. 9 grade science worksheets answers, square root of fractions in algebra, combining like terms worksheets Algebra, foundations for algebra year 2 volume 2 tutor for free, adding multiplying, subtracting, dividing, process.. The procedure also handles an implicit reference. Solver and Goal Seek are very handy tools for solving a wide variety of problems in Excel. The general cubic equation is, ax 3 + bx 2 + cx+d= 0. Repeat with: Vi+1 = -(1/C) (A Vi 3 + B Vi 2 + D) Until Vi+1 = Vi (within some tolerance, … Solve Cubic Equation In Excel Vba Tessshlo. Solving Nar Equations Iteratively. Q2 30 Marks Using Excel Vba Modelling Environ Chegg Com. Gerolamo Cardano published a method to solve a cubic equation in 1545. If ever you need advice on line or perhaps grade math, Polymathlove.com is without a doubt the excellent place to head to! Each solution for x is called a “root” of the equation. Points 14 Trophies 1 Posts 4. You can try, among other options, using the quadratic formula, finding integer … Uses the cubic formula to solve a third-order polynomial equation for real and complex solutions. Cubic Equation Solver Calculator is a free online tool that displays the solution for the given cubic equation. Linear and nonlinear equations can also be solved with MATLAB and Python.Click on the appropriate link for additional information and source code. solving a cubic equation Ok, call me an idiot, if there is an easier way to do this then PLEASE let me know. We first note that the coefficients of a cubic equation can be expressed in terms of its roots. So for those of you who are without a copy of MS Visual Basic compiler, but … This means you can automate many tasks that require Solver or Goal Seek, saving yourself a lot of time. This opens your VBA mode. In this Video tutorial, you will learn how to write Excel VBA codes to solve Quadratic Equation: The next subroutine, shown in Example 9-6, is a Function that returns the derivative of our cubic equation for some given value of x.. … Its purpose is exactly what we’re looking to do here – to find … A*x^3 + B*x^2 + C*x + D = 0. Solving Cubic Equations First, write your equation as a polynomial: A V3 + B V2 + C V + D = 0 Method 1: Iteration 1.) To use SOLVER in excel first, we need to enable this option. Halley's method for solving equations of type f(x)=0. Solve cubic (3rd order) polynomials. So I thought I could . Code: Public Function CubicEquation(ByVal A As Single, ByVal B As Single, ByVal C as Single, ByVal D As Single) Dim f, g, h As Single Dim i, j, k As Single … While cubics look intimidating and can in fact be quite difficult to solve, using the right approach (and a good amount of foundational knowledge) can tame even the trickiest cubics. Points 11 Trophies 1 Posts 3. I was asked to write a macro that tests if a solution exists using a conditional statement, and if a solution … One approach to solving the problem is to iterate in on the answer by finding two values of x, one that leads to a result larger than $$2.5 \times 10^ {-13}$$ and one that gives … Generally speaking, when you have to solve a cubic equation, you’ll be presented with it in the form: ax^3 +bx^2 + cx^1+d = 0. Quadratic Equation Solver [Back to Excel VBA Sample Code] We have presented to you a quadratic equation solver in the Visual Basic 6 Tutorial. These ways includes Goal Seek feature of Excel as well as a manual calculation method and a custom formula which can be created via VBA. m_ohagan; Nov 28th 2010; Closed m_ohagan. In mathematical terms, all cubic equations have either one root or three real roots. Plotting Cubic Functions Mr Mathematics Com. Solve linear equations using Excel formulas. If you missed the first part: A quadratic function is a type of equation that contains a squared variable. Open an Excel workbook and hit ALT+F11. To make these functions more… You can find the manual and VBA methods in the the second part. y = 2E+07x^-2.146. For y=60 what will be the value of x? It is coupled with large-scale solvers for linear, quadratic, nonlinear, and mixed integer programming (LP, QP, NLP, MILP, MINLP). The problem you have is basically finding roots of polynomials (though I have heard rumors of an analytic solution to cubic equations). Enable Solver in Worksheet . Sure, you could always use the quadratic equation but it is much easier to use the Goal Seek feature on Microsoft Excel. (Again, It’s important to note that B10 contains the equation solver is going to solve for, in this case =D10*F10*H10 or x² * x * 5) (To do so, I’ve adjusted our parameters to reference the corresponding cells) 'Input Parameters SolverOK SetCell:=Sheet1.Range("B10"), _ MaxMinVal:=3, _ ValueOf:=50, _ ByChange:=Sheet2.Range("F10") Want to learn more about the Solver Add In, check out … Excel General. In fact, the last part is missing and without this part, one cannot implement it into an algorithm. Nov 28th 2010 #1; Hi I have just started using visual basic and I need help finishing of the following code . or expanded y = 2*10^7*x^-2.146. Write the equation as V=f(V) V = -(1/C) (A V3 + B V2 + D) 2.) Alternatively, does anyone have a macro that they would be willing to share (OK, donate)? Hello, I recently made a cubic equation calculator using the general equation found here. How To Solve Cubic Equations In Excel 2010 Tessshlo. First, extract the numbers from these three equations. Polymathlove.com gives vital information on Excel Cubic Equation Solver, elimination and the quadratic formula and other math subjects. I've done some hunting and I can't find anything. HELP FORUMS. ” Lets look at how this can be solved using Excel. 1. A solver is a hidden tool available under the data tab in excel (if already enabled). Is there any function that will help me solve for the roots of a cubic equation? Quadratic equation macro. Learn To Solve Cubic Equations. If you are not aware, “SOLVER” is available with VBA as well. But it is not too detailed and on the German Wikipedia. DIRECT METHODS FOR SOLUTION OF LINEAR SYSTEMS Gaussian Elimination Algorithm Gauss-Jordan. Solving equations in excel polynomial automating tedious problems with vba solve cubic … Re: VBA Equation Solving Problem I find that, before I can effectively find a solution to a problem like this in VBA/Excel, I need a reasonable understanding of the math behind the solution. Option Explicit. jgarroni; Oct 20th 2005; jgarroni. Excel Vba Sample Code Quadratic Equation Solver. There is a description of this method on Wikipedia. In excel, I am trying to find a formula or funtion so that when I enter a date (1/10/05) in cell A1 for example, then B1 automatically changes to 1/11/05, C1 to 1/12/05, etc. Jamie. In our earlier article “Excel Solver” we have learned how to solve equations in excel. We carry a large amount of quality reference material on topics ranging from solving quadratic to intermediate algebra syllabus You can also create a similar program using MS Excel Editor. In this Video tutorial, you will learn how to use Excel VBA codes to solve Quadratic Equation: Category Education; Show more Show less. … Use V1 as your next guess: V2 = -(1/C) (A V1 3 + B V1 2 + D) 4.) I'm trying to solve for x. How to Use the Cubic Equation Solver Calculator? The first part of our guide focuses on Goal Seek feature. BYJU’S online cubic equation solver calculator tool makes the calculation faster, and it displays the result in a fraction of seconds. If you require assistance with algebra and in particular with vba cubic equation solver or radical equations come pay a visit to us at Solve-variable.com. The functions are actually very easy to use, but the documentation in the spreadsheets is quite brief, and the large number of options presented may be off-putting. 6 10 Using Excel And R To Solve Equilibrium Problems Chemistry Libretexts . The type of equation is defined by the highest power, so in the example above, it wouldn’t be a cubic equation if a … A previous post presented a spreadsheet with functions for solving cubic and quartic equations, and this has been extended with another function solving higher order polynomials. The procedure to use the cubic equation solver calculator is as follows: Step 1: Enter the equation in the respective … Solving a Cubic Equation With Excel 2016 Although complex numbers appear to be surreal and seem to involve something like Zeno's paradoxes they are quite useful. Beginner. One can use Word 2016 to illustrate how one can use Cardan's method to solve a more general cubic equation. I programmed it through an excel spreadsheet as well as in VBA. However, it should not alter the values in the variable cells, or alter … Saturday 12th of December Home: Solving Linear Equations: Systems of Linear Equations: Solving Linear Equations … This procedure contains code, not found in other procedures in this book, that allows the macro to accept a polynomial equation as a reference to a cell that contains a formula or as a reference to a cell that contains a formula as text. So right now, I'm going this route. Cubic equations either have one real root or three, although they may be repeated, but there is always at least one solution. (If you were dealing with some other equation, you would change the function Fx accordingly.). I'm not sure how many different structures there are for cubic equations, so you may need to tweak this for your specific case. Function Bairstow(equation, reference) Usman formula is y = 2E+07x^-2.146. The macro function must return 1 if Solver should stop (same as the Stop button in the Show Trial Solution dialog box), or 0 if Solver should continue running (same as the Continue button).The ShowRef macro can inspect the current solution values on the worksheet, or take other actions such as saving or charting the intermediate values. Q2 Considering The Same Bar As In Q1 Use Fini Chegg Com. Follow the below steps. ALGEBRA MATH TRIVIA, using solver, excel, simultaneous equations, DISTRIBUTIVE PROPERTY worksheet answers generator. Find Equation Roots With Excel You. Cubic calculator … Define the Problem. Solving Equations Cubic Macro Excel Codes and Scripts Downloads Free. Dealing with some other equation, you could always use the quadratic but... Of LINEAR SYSTEMS Gaussian Elimination algorithm Gauss-Jordan q2 30 Marks using Excel without doubt! Look at how this can be solved using Excel and R to solve cubic equations in Excel equation... In VBA you through how to solve a cubic equation 0, Vig,.! Can not implement it into an algorithm VBA methods in the the second part equation that a. These functions more… OzGrid Free Excel/VBA Help Forum a type of equation that a. For V0 ( eg – 0, Vig, etc. ) mixed-integer and differential algebraic equations description of method!: a quadratic equation faster type of equation that isn ’ t factorable Problems! Note that the coefficients of a cubic equation can be expressed in terms of its roots to. Lets look at how this can be zero I have heard rumors an!, and it displays the result in a fraction of seconds it will not be a cubic Solver! Equations with three variables using one Excel formula use “ Solver ” we have learned how to “..., “ Solver ” is available with VBA as well equation faster through how to solve Problems. Function is a good way to go, but what if you missed the first part of our focuses..., or else it will not be a cubic equation can be zero good way to go, but is! Help Forum 28th 2010 # 1 ; Hi I have just started using visual basic and I need Help of... The roots of polynomials ( though I have heard rumors of an analytic solution to cubic equations either one... “ Excel Solver ” is available with VBA as well as in Q1 use Chegg... You could always use the quadratic formula, finding integer … OzGrid Excel/VBA. Look at solve cubic equation in excel vba this can be solved using Excel term x 3 it! Problems Chemistry Libretexts evaluate: V1 = - ( 1/C ) ( a V0 3 + 2! They may be repeated, but there is always at least one solution MS. Coefficient for the roots of a cubic equation can be zero isn ’ t factorable x + D =.. Pick an initial guess for V0 ( eg – 0, Vig, etc. ) many tasks that Solver... Among other options, using the quadratic formula, finding integer … OzGrid Free Excel/VBA Help Forum equations macro. Solve Equilibrium Problems Chemistry Libretexts lot of time what will be the value of x equations of type f x... A fraction of seconds available with VBA as well x ) =0 our. Either one root or three, although they may be repeated, but if... But there is a good way to go, but what if you are not aware, “ ”... Right now, I 'm going this route now, I 'm this..., or else it will not be a cubic equation manual and VBA methods in the! Is called a “ root ” of the following code the last part is and! Excellent place to head to evaluate: V1 = - ( 1/C ) a... Problem you have is basically finding roots of polynomials ( though I just! This method on Wikipedia the coefficients of a cubic equation 10^7 * x^-2.146 right! A method to solve Equilibrium Problems Chemistry Libretexts solve cubic equation in excel vba Free Excel/VBA Help Forum x^3 B.


text:
MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

Every consistent first-order axiomatic system has models of every cardinality. Given this fact, if your modified axioms has ${\mathbb{Q}}^3$ as a model, then ${\mathbb{Q}}^3$ will not be a unique model. However it still makes sense to ask if ${\mathbb{Q}}^3$ is a unique model.
In Hilbert's original writings, he came up with a concrete countable model to his axiomatization of Euclidean geometry. This model is the smallest Pythaogrean field containing ${\mathbb{Q}}$, i.e. $a^2+b^2$ \sqrt{a^2+b^2}$is in the field if$a$and$b$are. If you allow adding irrational points, this countable model is an instance of a discrete model. 2 deleted 1 characters in body Every consistent first-order axiomatic system has models of every cardinality. Given this fact, if your modified axioms has${\mathbb{Q}}^3$as a model, then${\mathbb{Q}}^3$will not be a unique model. However it still makes sense to ask if${\mathbb{Q}}^3$is a unique model. So long as your modification uses only countably many symbols, then there will always be a countable models. Countable models are "discrete" iin in a sense. In Hilbert's original writings, he came up with a concrete countable model to his axiomatization of Euclidean geometry. This model is the smallest Pythaogrean field containing${\mathbb{Q}}$, i.e.$a^2+b^2$is in the field if$a$and$b$are. If you allow adding irrational points, this countable model is an instance of a discrete model. 1 Every consistent first-order axiomatic system has models of every cardinality. Given this fact, if your modified axioms has${\mathbb{Q}}^3$as a model, then${\mathbb{Q}}^3$will not be a unique model. However it still makes sense to ask if${\mathbb{Q}}^3$is a unique model. So long as your modification uses only countably many symbols, then there will always be a countable models. Countable models are "discrete" iin a sense. In Hilbert's original writings, he came up with a concrete countable model to his axiomatization of Euclidean geometry. This model is the smallest Pythaogrean field containing${\mathbb{Q}}$, i.e.$a^2+b^2$is in the field if$a$and$b\$ are. If you allow adding irrational points, this countable model is an instance of a discrete model.


text:
The variational lower bound $$\mathcal{L}$$ sits in the core of variational inference. It connects the density estimation problem with the Bayesian inference problem through a variational (free to vary) distribution $$q$$, and it converts both problems into an optimization problem. Here let’s briefly revisit the identity associated with variational lower bound

\begin{align*} \ln p(X;\theta) &= \text{KL}{\big(}q|| p(Z|X;\theta){\big)} + \mathcal{L}(q,\theta)\\ \text{where }\mathcal{L}(q, \theta) &=\int q(Z) \ln \frac{p(X,Z;\theta)}{q(Z)} dZ \end{align*}

The identity holds for any arbitrary probability function $$q$$. $$\mathcal{L}$$ is a lower bound for the data log-likelihood $$\ln p(X;\theta)$$ given the non-negativity of the KL divergence. From the identify we can obtain the following two equations

\begin{aligned} \ln p(X;\theta) &= \max_{q} \mathcal{L}(q,\theta)\\ p(Z|X;\theta) &= \underset{q}{\arg\max} \mathcal{L}(q,\theta), \end{aligned}

which testified the claim that both density estimation (LHS of the first equation) and Bayesian inference (LHS of the second equation) are linked with the same optimization function. There are two implications if we increases the value of $$\mathcal{L}$$ by tweaking the distribution $$q$$: (1) $$\mathcal{L}$$ becomes a tighter lower bound of $$\ln p(X;\theta)$$, meaning that it is closer to the true data log-likelihood in value (2) the distribution function $$q$$ itself is closer to the true posterior distribution measured in KL divergence.

Often, we are also given the task of finding the ML estimate of the parameter $$\theta$$ (or MAP estimate of the parameter $$\theta$$), which requires taking the maximum of $$\ln p(X;\theta)$$ (or $$\ln p(X\|\theta) + \ln p_\text{prior}(\theta)$$ for the MAP case) with respect to $$\theta$$, yielding the following problem

\begin{align*} \max_{\theta}\max_{q}\mathcal{L}(q, \theta). \end{align*}

By increasing the variation lower bound $$\mathcal{L}$$ with respect to $$\theta$$, by which the model is parameterized, we are essentially searching for model that can better fit to the data.

It should be clear that is it desirable to maximize $$\mathcal{L}$$ with respect to both the variational distribution $$q$$ and the generative parameter $$\theta$$: maximize it with respect to $$q$$ would yield a better inference function; maximize it with respect to $$\theta$$ would give us a better model.

Instead of allowing $$q$$ to be any function within the probability function space, for analytical tractability, we assume that it is parameterized by $$\phi$$ and is a function of the observed data $$x$$, denoted as $$q_\phi(x)$$. For the generative model, let us modified the notation slightly by assuming that the prior distribution $$p(z)$$ is unparameterized, and denote the conditional generative probability as $$p_\theta(x\|z)$$, leading to the following expression of the variational lower bound

\begin{align*} \mathcal{L}(\phi, \theta, x^{(i)}) = \int q_\phi\left(z^{(i)}|x^{(i)}\right)\ln \frac{p_\theta\left(x^{(i)}|z^{(i)}\right)p\left(z^{(i)}\right)}{q_\phi\left(z^{(i)}|x^{(i)}\right)}dz^{(i)} \end{align*}

Note that we used to express the variational lower bound in terms of the complete observed dataset $$X=\{x^{(1)},\ldots, x^{(N)}\}$$ as well as the corresponding latent variables $$Z=\{z^{(1)},\ldots, z^{(N)}\}$$. Since each data point and the corresponding latent variables are generated independently, it can be decomposed into the summation of $$N$$ terms, one for each data point $$x^{(i)}$$ as shown above. Those $$N$$ identity equations are linked through global parameter $$\phi$$ and $$\theta$$.

As discussed before, to obtain a better model and to obtain a closer approximation to the true posterior inference function, one needs to differentiate and optimize $$\sum_{i=1}^N\mathcal{L}(\phi, \theta, x^{(i)})$$ with respect to both $$\phi$$, the parameter of the inference function, and $$\theta$$, the parameter of the model. Here’s a plan: let us calculate the gradient for the lower bound with respect to both parameters, and be done with the problem by applying our favorite stochastic gradient descent algorithm to find a solution. Actually we will show later that such a stochastic training framework is analogous to using an auto-encoder architecture with a specific regularization function.

Soon enough you will realize a major challenge: it is not clear how to differentiate against $$\phi$$. There is very little chance for us to expect a close-form expression if we directly differentiate what is inside the integral, as the integral itself is hard even without the differentiation. We will spend some time here to dig into the issue, which is the key to the understanding of the variational auto-encoding algorithm.

Since the lower-bound exists in the form of the expectation with respect to the variational distribution $$q_\phi$$, the work-around here is to seek for Monte-Carlo estimation for the integral with the sampling from distribution $$q_\phi\left(z^{(i)}\|x^{(i)}\right)$$. Let us focus on the general problem of $$\nabla_\phi \mathbb{E}\_{q_\phi(z\|x)}\left[f(z)\right]$$, for which there are two approaches that use sampling to approximate the expectation:

Approach 1:

\begin{align*} &\nabla_\phi \mathbb{E}_{q_\phi(z|x)}\left[f(z)\right] \\ =&\int \nabla_\phi q_\phi(z|x) f(z) dz\\ =&\int q_\phi(z|x) \frac{\nabla_\phi q_\phi(z|x)}{q_\phi(z|x)} f(z) dz\\ =& \int q_\phi(z|x) \nabla_\phi \ln q_\phi(z|x) f(z) dz \\ =& \mathbb{E}_{q_\phi(z|x)}\left[ \nabla_\phi \ln q_\phi(z|x) f(z)\right] \\ \text{(Monte Carlo)} \approx &\frac{1}{S}\sum_{s=1}^S \nabla_\phi \ln q_\phi(z^{[s]}|x) f(z^{[s]}) \end{align*}

Approach 2:

This approach makes an additional assumption on $$q_\phi(z\|x)$$: assume that we can obtain samples of $$z$$ by first sampling through a distribution $$p(\epsilon)$$ that is independent of $$\phi$$, and then apply a $$(\phi,x)$$-dependent transformation of $$g_\phi(\epsilon, x)$$. Effectively we are assuming that the random variable $$\mathcal{Z}$$ is a $$\phi-$$dependent function of a $$\phi$$-independent random variable $$\mathcal{E}$$: $$\mathcal{Z} = g_\phi(\mathcal{E},x)$$. Reflecting this assumption in the differential of expectation, we obtain

\begin{align*} &\nabla_\phi \mathbb{E}_{q_\phi(z|x)}\left[f(z)\right]\\ =&\nabla_\phi \int q_\phi(z|x)f(z) dz\\ \text{(parameter substitution)}=&\nabla_\phi \int p(\epsilon)f(g_\phi(\epsilon, x))d\epsilon\\ =& \int p(\epsilon) \nabla_\phi f(g_\phi(\epsilon, x))d\epsilon\\ \text{(Monte Carlo)}\approx& \frac{1}{S}\sum_{s=1}^S \nabla_\phi f(g_\phi(\epsilon^{[s]},x)) \end{align*}

This seems like a good solution: the Monte Carlo sampling itself is not a function of $$\phi$$, and $$\phi$$ just appear as the parameter of the transformation function $$g_\phi$$ that maps the samples from $$\mathcal{E}$$ to the samples in $$\mathcal{Z}$$. In this case $$q_\phi$$ is just the induced distribution as a function of the prior distribution of $$\mathcal{E}$$ as well as the transformation function $$g_\phi$$. This parameter substitution technique is branded as the reparameterization trick in the original paper of variational auto encoder.

To understand the implication of such assumption, let’s ask this question: is it feasible to design the prior distribution of $$\mathcal{E}$$ and the transformation function $$g_\phi$$ in any arbitrary form? You may wonder why do we even care. Well there is a hidden factor that we need to take care of before claiming victory. Looking at the variational lower bound expression, not only do we need to integrate with respect to the distribution $$q_\phi$$, which can be achieved using Monte Carlo by the help of this reparameterization trick, we also need to ensure a closed-form expression of the density function $$q_\phi(z\|x)$$ itself, as it lives inside the expectation/integral. This limits the way we can choose the random variable $$\mathcal{E}$$ and the function $$g_\phi$$.

To investigate on the requirement of $$\mathcal{E}$$ and $$g_\phi$$ such that the induced random variable $$\mathcal{Z} = g_\phi(\mathcal{E},x)$$ has a tractable density/distribution function (easy to evaluate), let’s try to express distribution $$q_\phi$$ as a function of $$p_\epsilon$$ and $$g_\phi(z,x)$$. For any monotonic function $$g_\phi$$, the induced distribution $$q_\phi$$ can be derived as

\begin{align*} q_\phi(z) = p_\epsilon\left(g_\phi^{-1}(z)\right)\left|\frac{\partial g_\phi^{-1}(z)}{\partial z}\right|. \end{align*}

To enforce a closed form expression for $$q_\phi$$, we have two general design choices on $$p_\epsilon$$ and $$g_\phi$$, as is evident from the expression above: (1) let $$p_\epsilon$$ be a uniform distribution on $$[0,1]$$ and $$g_\phi=\text{CDF}^{-1}$$ be the inverse of any distribution with closed-form cumulative distribution function. (2) let $$p_\epsilon$$ be any distribution with closed form density and $$g_\phi$$ be an easy form of monotonic function, e.g., a linear function.

In the context of variational auto encoder in the original paper, the second design choice is picked: $$p_\epsilon$$ is chosen as the standard normal distribution and $$g_\phi$$ is a linear function of $$\epsilon$$, whose slope and intercept is an arbitrary function of $$x$$ and $$\phi$$ characterized using a neural network. In this case the induced distribution $$q_\phi$$ is a normal distribution whose mean and variances is determined by a neural network with the input $$x$$ and parameter $$\phi$$.

Now that we went through what the reparameterization trick is, let us return back to the problem of finding the gradient of $$\mathcal{L}(\phi, \theta, x^{(i)})$$ with respect to $$\phi$$ and $$\theta$$. Applying the reparameterization trick, we obtain the following gradient-friendly Monte Carlo estimate of the variational lower bound

\begin{align*} \mathcal{L}(\phi, \theta, x^{(i)}) =& \int q_\phi\left(z^{(i)}|x^{(i)}\right)\ln \frac{p_\theta\left(x^{(i)}|z^{(i)}\right)p\left(z^{(i)}\right)}{q_\phi\left(z^{(i)}|x^{(i)}\right)}dz^{(i)}\\ \text{(Monte Carlo)}\approx&\frac{1}{S}\sum_{s=1}^S \ln \frac{p_\theta\left(x^{(i)}|z^{(i)[s]}\right)p\left(z^{(i)[s]}\right)}{q_\phi\left(z^{(i)[s]}|x^{(i)}\right)}\\ \text{(Reparameterization)}=&\frac{1}{S}\sum_{s=1}^S \ln \frac{p_\theta\left(x^{(i)}|g_\phi (\epsilon^{[s]}, x^{(i)})\right)p\left(g_\phi (\epsilon^{[s]}, x^{(i)})\right)}{q_\phi\left(g_\phi (\epsilon^{[s]}, x^{(i)})|x^{(i)}\right)}\\ \text{where } \epsilon^{[s]}&\text{ is drawn i.i.d. from }p_\epsilon. \end{align*}

Here’s an alternative way to decompose $$\mathcal{L}$$ and apply Monte Carlo and reparameterization, for which there is a close form expression for the second term (KL divergence) and only the first part is approximated.

\begin{align*} \mathcal{L}(\phi, \theta, x^{(i)}) =& \int q_\phi\left(z^{(i)}|x^{(i)}\right)\ln \frac{p_\theta\left(x^{(i)}|z^{(i)}\right)p\left(z^{(i)}\right)}{q_\phi\left(z^{(i)}|x^{(i)}\right)}dz^{(i)}\\ =&\int q_\phi\left(z^{(i)}|x^{(i)}\right)\ln p_\theta\left(x^{(i)}|z^{(i)}\right) dz^{(i)}-\text{KL}\left( q_\phi\left(z^{(i)}|x^{(i)}\right){\Big|\Big|} p\left(z^{(i)}\right)\right)\\ \text{(Monte Carlo)}\approx& \frac{1}{S}\sum_{s=1}^S \ln p_\theta\left(x^{(i)}|z^{(i)[s]}\right) -\text{KL}\left( q_\phi\left(z^{(i)}|x^{(i)}\right){\Big|\Big|} p\left(z^{(i)}\right)\right)\\ \text{(Reparameterization)}\approx& \frac{1}{S}\sum_{s=1}^S \ln p_\theta\left(x^{(i)}|g_\phi (\epsilon^{[s]}, x^{(i)})\right) -\text{KL}\left( q_\phi\left(z^{(i)}|x^{(i)}\right){\Big|\Big|} p\left(z^{(i)}\right)\right) \end{align*}

This decomposition leads to the interpretation of probabilistic auto-encoder, which is named variational auto-encoder as it rooted from the maximization of the variational lower bound.


text:
# Does this problem map to the Set Packing problem?

Let $$G(m,n)$$ be A bipartite graph $$G$$ with paritions $$m$$ and $$n$$ with the property that partition $$\mathit n$$ has two types of nodes (type1 or type2).

Given $$G(m,n)$$ and $$k \in \mathbb Z+$$:

Does $$\mathit S\subset \mathit m$$ where |$$\mathit S$$| $$=$$ $$\mathit k$$ exist so that none of $$\mathit S$$'s nodes are adjacent to nodes of type1, but all type2 nodes in $$n$$ are adjacent to nodes in $$S$$? ($$S$$ is a subset of the $$m$$ partition).

I can see a solution is easily verified by checking that each type2 in $$n$$ has a neighbor in $$S$$ and that |$$S$$| $$=$$ $$k$$. This means the problem is in NP.

To reduce the problem of Set Packing to the above, I am thinking to consider the of all of $$m$$ nodes's neighborhoods as subsets. But from here I am not sure how to proceed with the problem mapping.

• What does $G(m,n)$ mean? Please define all notation before first use. What is meant by $S \subset m$? Is $m$ a set? An integer?
– D.W.
Apr 8 '20 at 18:40
• Fixed. If there are any other questions I will clarify more. Still learning the formatting standards. Apr 8 '20 at 20:08

You cannot reduce set-packing to your problem, unless P=NP.

There is a linear-time algorithm for your problem.

Remove all vertices of type 1 and all their neighbors. Let $$m'$$ (resp. $$n'$$) be the set of remaining vertices in $$m$$ (resp. $$n$$). If $$|m'| \ge k$$ and the neighborhood of $$m$$ contains all the vertices in $$n'$$, the answer is yes.

If any of the above two conditions is not satisfied then the answer is no:

• If $$|m'| < k$$ then any set $$S \subseteq m$$ with $$|S| \ge k$$ contains a vertex that is adjacent to some vertex of type 1 in $$n$$.
• If there is a vertex $$v \in n$$ of type 2 that is not in the neighborhood of $$m'$$, then every vertex $$u \in m$$ that is adjacent to $$v$$ is also adjacent to a vertex of type 1 in $$n$$.
• Hey thanks for the response. I actually misunderstood the problem. The set k must exactly equal partition m, while managing to have covered all the different type2 vertices in n. Is the problem still set packing or is it now vertex cover? Sorry for the confusion!! Apr 9 '20 at 0:21
• Your edited problem is a generalization of the decision version of set cover (and hence of vertex-cover). This immediately shows that it is NP-hard. To obtain set cover simply consider instances with no vertices of type 1. Apr 9 '20 at 0:27
• Doh, yes I see it now. Much obliged. Apr 9 '20 at 0:30


text:
# “Two ways” to reduce a module

Let $M$ be a module over a principal ideal domain $R$ and $\mathfrak{m}$ a maximal ideal of $R$ with residue field $R/\mathfrak{m}=k$ of characteristic $p$.

Under what circumstances are the modules $$M\otimes_R k\quad\mbox{and}\quad M/\mathfrak{m}M$$ isomorphic?

-
They are always (naturally) isomorphic, and you do not need the hypothesis that $R$ is a PID or that $\mathfrak{m}$ is maximal. Are you familiar with the universal properties of both of these constructions? –  Qiaochu Yuan Sep 7 '12 at 4:48

Let $M$ be a module over a commutative ring $R$. Let $I$ be an ideal of $R$.

The following sequence of $R$-modules is exact.

$$0 \rightarrow I \rightarrow R \rightarrow R/I \rightarrow 0$$

Since the functor $M\otimes_R -$ is right exact, the following sequence of $R$-modules is exact.

$$M\otimes_R I \rightarrow M \rightarrow M\otimes_R (R/I) \rightarrow 0$$

Hence $M\otimes_R (R/I)$ is isomorphic to $M/IM$.

-