text:
## STACK Documentation

Documentation home | Category index | Parent | Site map

# Introduction to Maxima for STACK users

Maxima is a system for the manipulation of symbolic and numerical expressions, including differentiation, integration, Taylor series, Laplace transforms, ordinary differential equations, systems of linear equations, polynomials, and sets, lists, vectors, matrices, and tensors.

To write more than very simple questions you will need to use some Maxima commands. This documentation does not provide a detailed tutorial on Maxima. A very good introduction is given in Minimal Maxima, which this document assumes you have read.

STACK then modifies Maxima in a number of ways.

## Types of object

Maxima is a very weakly typed language. However, in STACK we need the following "types" of expression:

1. equations, i.e. an expression in which the top operation is an equality sign;
2. inequalities, for example $$x<1\mbox{, or }x\leq 1$$;
3. sets, for example, $$\{1,2,3\}$$;
4. lists, for example, $$[1,2,3]$$. In Maxima ordered lists are entered using square brackets, for example as p:[1,1,2,x^2]. An element is accessed using the syntax p[1].
5. matrices. The basic syntax for a matrix is p:matrix([1,2],[3,4]). Each row is a list. Elements are accessed as p[1,2], etc.
6. logical expression. This is a tree of other expressions connected by the logical and and or. This is useful for expressing solutions to equations, such as x=1 or x=2. Note, the support for these expressions is unique to STACK.
7. expressions.

Expressions come last, since they are just counted as being not the others! STACK defines predicate functions to test for each of these types.

## Numbers

Numbers are important in assessment, and there is more specific and detailed documentation on how numbers are treated: Numbers in STACK.

## Alias

STACK defines the following function alias names

simplify := fullratsimp
int := integrate

The absolute value function in Maxima is entered as abs(). STACK also permits you to enter using | symbols, i.e.|x|. This is an alias for abs. Note that abs(x) will be displayed by STACK as $$|x|$$.

STACK also redefined a small number of functions

• The plot command plot2d is not used in STACK questions. Use plot instead, which is documented here. This ensures your image files are available on the server.
• The random number command random is not used in STACK questions. Use the command rand instead, which is documented here. This ensures pseudorandom numbers are generated and a student gets the same version each time they login.

# Parts of Maxima expressions

### op(x) - the top operator

It is often very useful to take apart a Maxima expression. To help with this Maxima has a number of commands, including op(ex), args(ex) and part(ex,n). Maxima has specific documentation on this.

In particular, op(ex) returns the main operator of the expression ex. This command has some problems for STACK.

1. calling op(ex) on an atom (see Maxima's documentation on the predicate atom(ex)) such as numbers or variable names, cause op(ex) to throw an error.
2. op(ex) sometimes returns a string, sometimes not.
3. the unary minus causes problems. E.g. in -1/(1+x) the operation is not "/", as you might expect, but it is "-" instead!

To overcome these problems STACK has a command

stack_op(ex)

This always returns a string. For an atom this is empty, i.e. "". It also sorts out some unary minus problems.

### get_ops(ex) - all operators

This function returns a set of all operators in an expression. Useful if you want to find if multiplication is used anywhere in an expression.

# Maxima commands defined by STACK

It is very useful when authoring questions to be able to test out Maxima code in the same environment which STACK uses Maxima. That is to say, with the settings and STACK specific functions loaded. To do this see STACK-Maxima sandbox.

STACK creates a range of additional functions and restricts those available, many of which are described within this documentaion. See also Predicate functions.

Command Description
factorlist(ex) Returns a list of factors of ex without multiplicities
zip_with(f,a,b) This function applies the binary function $$f$$ to two lists $$a$$ and $$b$$ returning a list. An example is given in adding matrices to show working.
coeff_list(ex,v) This function takes an expression ex and returns a list of coefficients of v
coeff_list_nz(ex,v) This function takes an expression ex and returns a list of nonzero coefficients of v
divthru(ex) Takes an algebraic fraction, e.g. $$(x^4-1)/(x+2)$$ and divides through by the denominator, to leave a polynomial and a proper fraction. Useful in feedback, or steps of a calculation.
stack_strip_percent(ex,var) Removes any variable beginning with the % character from ex and replace them with variables from var. Useful for use with solve, ode2 etc. Solve and ode2.
exdowncase(ex) Takes the expression ex and substitutes all variables for their lower case version (cf sdowncase(ex) in Maxima). This is very useful if you don't care if a student uses the wrong case, just apply this function to their answer before using an answer test. Note, of course, that exdowncase(X)-x=0.
stack_reset_vars Resets constants, e.g. $$i$$, as abstract symbols, see Numbers.
safe_op(ex) Returns the operation of the expression as a string. Atoms return an empty string (rather than throwing an error as does op).
comp_square(ex,v) Returns a quadratic ex in the variable v in completed square form.
degree(ex,v) Returns the degree of the expanded form of ex in the variable v. See also Maxima's hipow command.
unary_minus_sort(ex) Tidies up the way unary minus is represented within expressions when simp:false. See also simplification.
texboldatoms(ex) Displays all non-numeric atoms in bold. Useful for vector questions.
exdowncase(ex) This function makes a substitution of all variables for their lower case equivalents.

## Assignment

In Maxima the assignment of a value to a variable is very unusual.

Input Result
a:1 Assignment of the value $$1$$ to $$a$$.
a=1 An equation, yet to be solved.
f(x):=x^2 Definition of a function.

In STACK simple assignments are of the more conventional form key : value, for example,

n : rand(3)+2;
p : (x-1)^n;

Of course, these assignments can make use of Maxima's functions to manipulate expressions.

p : expand( (x-3)*(x-4) );

Another common task is that of substitution. This can be performed with Maxima's subst command. This is quite useful, for example if we define $$p$$ as follows, in the then we can use this in response processing to determine if the student's answer is odd.

p : ans1 + subst(-x,x,ans1);

All sorts of properties can be checked for in this way. For example, interpolates. Another example is a stationary point of $$f(x)$$ at $$x=a$$, which can be checked for using

p : subst(a,x,diff(ans1,x));

Here we have assumed a is some point given to the student, ans1 is the answer and that $$p$$ will be used in the response processing tree.

You can use Maxima's looping structures within Question variables, although the syntax requires this to be of the form key = value. In this case, the key will be assigned the value DONE at the end of the process, unless another value is returned. For example

n : 1;
dum1 : for a:-3 thru 26 step 7 do n:n+a;

Note, you must use Maxima's syntax a:-3 here for assignment of $$-3$$ to the variable a. The assignment to the dummy variable dum1 is to ensure every command is of the form key : value. Please look at Maxima's documentation for the command do.

It is also possible to define functions within the Question Variables for use within a question. This is not recommended, and has not been widely tested. For example

dum1 : f(x) := x^2;
n : f(4);

## Logarithms

STACK loads the contributed Maxima package log10. This defines logarithms to base $$10$$ automatically. STACK also creates two aliases

1. ln is an alias for $$\log$$, which are natural logarithms
2. lg is an alias for $$\log10$$, which are logarithms to base $$10$$. It is not possible to redefine the command log to be to the base $$10$$.

## Functions

It is sometimes useful for the teacher to define functions as part of a STACK question. This can be done in the normal way in Maxima using the notation.

 f(x):=x^2;

Using Maxima's define() command is forbidden. An alternative is to define f as an "unnamed function" using the lambda command.

 f:lambda([x],x^2);

Here we are giving a name to an "unnamed function" which seems perverse. Unnamed functions are extremely useful in many situations.

For example, a piecewise function can be defined by either of these two commands

 f(x):=if (x<0) then 6*x-2 else -2*exp(-3*x);
f:lambda([x],if (x<0) then 6*x-2 else -2*exp(-3*x));

You can then plot this using

@plot(f(x),[x,-1,1])@

# Maxima "gocha"s!

• See the section above on assignment.
• Maxima does not have a degree command for polynomials. We define one via the hipow command.
• Matrix multiplication is the dot, e.g. A.B. The star A*B gives element-wise multiplication.


text:
# American Institute of Mathematical Sciences

March  2014, 13(2): 645-655. doi: 10.3934/cpaa.2014.13.645

## Boundedness of solutions for a class of impact oscillators with time-denpendent polynomial potentials

 1 School of Mathematical Sciences, Ocean University of China, Qingdao 266100, China, China

Received  January 2013 Revised  July 2013 Published  October 2013

In this paper, we consider the boundedness of solutions for a class of impact oscillators with time dependent polynomial potentials, \begin{eqnarray} \ddot{x}+x^{2n+1}+\sum_{i=0}^{2n}p_{i}(t)x^{i}=0, \quad for\ x(t)> 0,\\ x(t)\geq 0,\\ \dot{x}(t_{0}^{+})=-\dot{x}(t_{0}^{-}), \quad if\ x(t_{0})=0, \end{eqnarray} where $n\in N^+$, $p_i(t+1)=p_i(t)$ and $p_i(t)\in C^5(R/Z).$
Citation: Daxiong Piao, Xiang Sun. Boundedness of solutions for a class of impact oscillators with time-denpendent polynomial potentials. Communications on Pure & Applied Analysis, 2014, 13 (2) : 645-655. doi: 10.3934/cpaa.2014.13.645
##### References:

show all references

##### References:
 [1] Yanmin Niu, Xiong Li. An application of Moser's twist theorem to superlinear impulsive differential equations. Discrete & Continuous Dynamical Systems, 2019, 39 (1) : 431-445. doi: 10.3934/dcds.2019017 [2] Huiping Jin. Boundedness in a class of duffing equations with oscillating potentials via the twist theorem. Communications on Pure & Applied Analysis, 2011, 10 (1) : 179-192. doi: 10.3934/cpaa.2011.10.179 [3] Holger Teismann. The Schrödinger equation with singular time-dependent potentials. Discrete & Continuous Dynamical Systems, 2000, 6 (3) : 705-722. doi: 10.3934/dcds.2000.6.705 [4] Nicola Guglielmi, László Hatvani. On small oscillations of mechanical systems with time-dependent kinetic and potential energy. Discrete & Continuous Dynamical Systems, 2008, 20 (4) : 911-926. doi: 10.3934/dcds.2008.20.911 [5] Božzidar Jovanović. Symmetries of line bundles and Noether theorem for time-dependent nonholonomic systems. Journal of Geometric Mechanics, 2018, 10 (2) : 173-187. doi: 10.3934/jgm.2018006 [6] Alessandro Fortunati, Stephen Wiggins. Normal forms à la Moser for aperiodically time-dependent Hamiltonians in the vicinity of a hyperbolic equilibrium. Discrete & Continuous Dynamical Systems - S, 2016, 9 (4) : 1109-1118. doi: 10.3934/dcdss.2016044 [7] Florian Wagener. A parametrised version of Moser's modifying terms theorem. Discrete & Continuous Dynamical Systems - S, 2010, 3 (4) : 719-768. doi: 10.3934/dcdss.2010.3.719 [8] Yavar Kian, Alexander Tetlow. Hölder-stable recovery of time-dependent electromagnetic potentials appearing in a dynamical anisotropic Schrödinger equation. Inverse Problems & Imaging, 2020, 14 (5) : 819-839. doi: 10.3934/ipi.2020038 [9] Masahiro Ikeda, Ziheng Tu, Kyouhei Wakasa. Small data blow-up of semi-linear wave equation with scattering dissipation and time-dependent mass. Evolution Equations & Control Theory, 2021  doi: 10.3934/eect.2021011 [10] Haixia Li. Lifespan of solutions to a parabolic type Kirchhoff equation with time-dependent nonlinearity. Evolution Equations & Control Theory, 2020  doi: 10.3934/eect.2020088 [11] Nikolaos S. Papageorgiou, Vicenţiu D. Rădulescu. Periodic solutions for time-dependent subdifferential evolution inclusions. Evolution Equations & Control Theory, 2017, 6 (2) : 277-297. doi: 10.3934/eect.2017015 [12] Paul Deuring. Spatial asymptotics of mild solutions to the time-dependent Oseen system. Communications on Pure & Applied Analysis, 2021, 20 (5) : 1833-1849. doi: 10.3934/cpaa.2021044 [13] Qiwei Wu, Liping Luan. Large-time behavior of solutions to unipolar Euler-Poisson equations with time-dependent damping. Communications on Pure & Applied Analysis, 2021, 20 (3) : 995-1023. doi: 10.3934/cpaa.2021003 [14] Takeshi Fukao, Masahiro Kubo. Time-dependent obstacle problem in thermohydraulics. Conference Publications, 2009, 2009 (Special) : 240-249. doi: 10.3934/proc.2009.2009.240 [15] Giuseppe Maria Coclite, Mauro Garavello, Laura V. Spinolo. Optimal strategies for a time-dependent harvesting problem. Discrete & Continuous Dynamical Systems - S, 2018, 11 (5) : 865-900. doi: 10.3934/dcdss.2018053 [16] Francesco Di Plinio, Gregory S. Duane, Roger Temam. Time-dependent attractor for the Oscillon equation. Discrete & Continuous Dynamical Systems, 2011, 29 (1) : 141-167. doi: 10.3934/dcds.2011.29.141 [17] Morteza Fotouhi, Mohsen Yousefnezhad. Homogenization of a locally periodic time-dependent domain. Communications on Pure & Applied Analysis, 2020, 19 (3) : 1669-1695. doi: 10.3934/cpaa.2020061 [18] G. Dal Maso, Antonio DeSimone, M. G. Mora, M. Morini. Time-dependent systems of generalized Young measures. Networks & Heterogeneous Media, 2007, 2 (1) : 1-36. doi: 10.3934/nhm.2007.2.1 [19] Jin Takahashi, Eiji Yanagida. Time-dependent singularities in the heat equation. Communications on Pure & Applied Analysis, 2015, 14 (3) : 969-979. doi: 10.3934/cpaa.2015.14.969 [20] Hristo Genev, George Venkov. Soliton and blow-up solutions to the time-dependent Schrödinger-Hartree equation. Discrete & Continuous Dynamical Systems - S, 2012, 5 (5) : 903-923. doi: 10.3934/dcdss.2012.5.903

2020 Impact Factor: 1.916

format: plain


text:
# Why I Don't Like Akka Actors

Published on 04 March 2013

We recently rewrote Myna’s back-end service. The architecture changed dramatically, and is now both faster and easier to extend. One of the significant architectural changes was removing all Akka actors. After heavily using them in the first version of the back-end, I have come to prefer other methods of managing concurrency. Since Akka’s actors are so prominent within the Scala community I thought it might be of interest to describe why we made this change.

## Actors are Coarse Abstractions

Actors are presented as a universal primitive for concurrency. That is, in the orthodox actor world view they are all you need for any concurrent program. There is an appealing conceptual simplicity to this approach, and the idea of finding an uber-abstraction has been successful in other contexts. For example, Scala’s unification of Java’s primitive and object types, or Python representing all values as mutable dictionaries as generally considered positive points by their respective language communities.

Problems arise when in the quest for simplicity important distinctions are hidden. In programming languages this usually comes up when discussing performance. The distinction between primitive and object types really matters if you care about speed. Scala gets away with this for the most part through clever compilation in both the Scala compiler and Hotspot, but writing high performance code can still be something of a dark art1.

Concurrent programming involves at least three distinct concerns: concurrency, mutual exclusion, and synchronisation. With actors the first two always come combined, and you’re left to hand-roll your own synchronisation through custom message protocols. It’s an unhappy state of affairs if you want to do something as simple as separating control of concurrency and mutual exclusion. This is not an esoteric concern – it is exactly what a ConcurrentHashMap provides, for example. If you’re really seeking performance then you probably want to use lock-free algorithms. Again, these don’t fit into the actor model. Basically the actor model is forcing us to give up a lot of tools so we can fit within its rigid conception of a concurrent program.

## Actors do not Compose

Composition is a desireable property of abstractions. Functions compose. If I create some functions (say, plus and minus) you can create another function (say multiply) that uses my functions. In particular I don’t have to anticipate your usage ahead of time to allow you to use my functions.

Actors don’t compose. By default actors hard-code the receiver of any messages they send. If I create an actor A that sends a message to actor B, and you want to change the receiver to actor C you are basically out of luck. If you’re lucky I anticipated this in advance and made it configurable, but more likely you have to change the source. Lack of composition makes it difficult to create big systems out of small ones.

## Akka’s Actors are not Usefully Typed

Akka’s actors give you static typing within a single actor, but the communication between actors – the complex bits that are most likely to go wrong – are not typed in any useful manner. I could live with the above two issues, but this one really gets me.

The type system is the reason we use Scala. Types allow us to guarantee certain properties of our programs. If you’ve never used a modern statically typed programming language you might be surprised just how far you can push this. We try to push it reasonably far, so we can guarantee that, for example, Myna’s API generates useful error messages (this is important because the API is the UI for many users). In return for this awesome power we put up with a bit of extra complexity compared to a dynamically typed language.

Akka supports a number of features, such as become and transparent distribution, that make statically typing messages difficult. We still have some inconvenience over dynamically typed languages but we lose the benefits of static typing. This is the wrong tradeoff for me.

Other languages, like Concurrent ML and Haskell, have demonstrated it’s possible to have great concurrent and distributed programming abstractions in a statically typed language. I expect the same in Scala.

## So What Does Myna Use?

So given the above, what does Myna use? We use Akka’s Futures, which I think are fantastic. We use plain-old locks for some simple cases where we want mutual exclusion, and we use a few of the utilities in java.util.concurrent. It’s quite simple and it’s quite fast: 2.5ms average response time, and well over 650 requests/s on a single core machine.

1. Python basically does nothing about this issue, which is why it’s so slow. In fact the decision to make everything a mutable dictionary is one big reason it’s so hard to optimise Python. PyPy, a JIT compiler for Python, has consumed 10 years and several million currency units and is still not widely deployed.


text:
# Serokell at ICFPC 2021: Rust, TypeScript, and Brain Wall

Article by Team TBD
July 30th, 2021

On July 9-12, the team TBD took part in the ICFP Contest. It was 50% Serokell: Vlad, Ilona, and Jonn joined forces with Julie, Sergey, and Pavel. In the end, we managed to get 35th place out of 160.

## What is ICFPC?

ICFPC is an annual programming contest with a long history. Each year, individuals and teams of unlimited size compete to solve a single problem in 72 hours, with no constraints on the technologies they can use. In addition to the full leaderboard, the contest has Lightning Division – a separate leaderboard for the submissions made in the first 24 hours.

The nature of the problem can’t be predicted in advance. Each year the contest has a new group of organizers (usually it’s the computer science department of this or that university; sometimes it’s organized by firms). The organizers try to play off the past contest themes but also to add something completely new.

In 2014, the problem was to write an AI that plays the game of Pacman, both for Pacman and for ghosts. The twist was that Pacman had to run on the fantasy LISP machine specified in the problem description. And the AI for ghosts ran on the fantasy 8-bit microprocessors. It was not enough to write the AI, we had to implement two compilers as well.

In 2020, the problem statement didn’t have any words in any of the human languages. It was presented as a sequence of messages from space, where aliens show their notation for arithmetic, then for boolean algebra, then for combinatorial calculus, then describe the communication protocol, and finally give a program that, in human terms, is a thin client for the galactic network. The participants deciphered the messages, implemented an emulator to run this “browser”, and discovered, well, spoilers.

This year’s task was inspired by an important real-world application. It’s a 2D geometry problem where we are given a stick figure and a polygonal hole, and our goal is to arrange the figure to fit into the hole. All coordinates are integers, and sticks are allowed to stretch a little. In addition, the closer the figure fits the hole’s boundaries, the fewer “dislikes” it gets. Dislikes contribute to the overall team standings.

For more details, see the full problem spec.

At the beginning of the contest, we were given 59 problem instances, ranging from trivial to somewhat intricate.

Problem 1.
Problem 32.
Problem 53.

Three updates to the problem, scheduled for 24, 36, and 48 hours after the start, introduced the system of bonuses. Each problem has one or more spots inside the hole. If the stick figure touches such a spot, this unlocks a bonus in another specified problem instance. The bonuses allow you to bend the rules, for example, make one stick infinitely stretchable or break one stick into two. Some bonus spots are impossible to reach without using another bonus in the first place. So bonus chains potentially can be long or even circular.

At first, these possible bonus chains were neatly organized.

But as updates kept adding more bonus types and more problem instances, they got maybe a little bit too messy.

In addition to the bonus system, the updates included more problem instances, bringing the total number to 132. The new problem instances ranged from somewhat intricate to hellish.

Problem 122.

## Our solution

We chose the stack of Rust and TypeScript before the contest, and some of the team practiced a bit beforehand.

We chose this stack because Rust’s automatic safety allows for writing performant code with minimum runtime overhead. Typing JavaScript is crucial to catch errors caused by sleep deprivation and high-velocity coding, and we’ve been using web browsers as the “UI framework” for a while, given their flexibility and high standardisation.

Regarding our solution: it had several components, discussed in detail later. Please note that while some pieces of work didn’t end up in the final submission, it doesn’t mean that we aren’t absolutely grateful for these contributions.

### Visualiser

The visualiser was intended from the very beginning as a full-fledged interactive tool. The main purpose of interactivity was to get a sense of the task. What is it like? What are the main obstacles? How can it be approached? We expected to get some ideas for solvers from interacting with it.

The second goal was the Lightning Submission 24 hours into the contest. We hoped that even if we had no decent automated solver by that time, we would have solved at least some problems manually – as we eventually did. This gave us 70th place in the Lightning Division.

We used the Web as our UI toolkit. The visualizer had client-server architecture. Non-trivial logic was implemented in the Rust server. Canvas rendering and user controls were done in vanilla TypeScript. For communication, we used typed JSON messages, with type definitions manually kept in sync between Rust and TypeScript.

The visualiser ended up with a bunch of features.

1. A set of constraint highlightings: the sticks crossing the boundary were dashed, too short and too long edges were color-coded, the Goldilocks zones for edge lengths were shown as circles, etc.
2. Instruments to select several vertices and then move or rotate them.
3. The option to show solutions statistics, load a solution from a file, or submit it right from the UI.
Purple edges are too short, red ones are too long, and dashed ones cross the hole boundary (gray line). The circles show the minimum and maximum allowed edge lengths.

### Shakers

Twenty hours into the contest, we didn’t have any good ideas for a fully automated solver. On the other hand, producing the solutions manually in the UI was too cumbersome.

The UI was already organized around selecting multiple vertices and applying a transformation to them. So we thought: “what if we make transformations more complex?” And the generic shaker was born. By the end of the contest, we had implemented ten different shakers.

What a shaker does is: it takes a subset of vertices and, well, shakes it into a new position. Shakers that work on a subset of vertices won’t yield correct figures, but they are nonetheless helpful to produce human-made solutions quickly. Some of our best final solutions were obtained this way.

#### Daiquiri and mojito shakers

The idea for these shakers came from manual solving in visualiser. After a couple of moves, there was a long string of tweaking all the vertices to meet the constraints. The purpose was to automate the search of a good solution nearby, to shake the vertices a little into a better position.

The first version, called “daiquiri”, does not optimise for dislikes or bonuses, it does not even consider boundaries – it only cares for edge length constraints. The algorithm gets selected vertices, then goes through their random permutation. For each vertex, it iterates through adjacent edges, and if the edge is too long or too short, moves the edge one step horizontally or vertically towards a better length.

The upgraded version of the same shaker, called “mojito”, takes boundaries into account – if the vertex was in the hole, it should stay in the hole. It does not check if the edge is in the hole, so it still produces invalid solutions sometimes.

Mojito was a helpful tool for manual solving. For example, problem 78 was solved by a combination of manual changes and mojito.

First, the crab is mostly out of the hole:

It was manually turned upside down and crammed into the hole. A lot of red and purple sticks do not satisfy the constraints:

After mojito, all edges satisfy the length condition, although some got out of the hole.

Now some parts can be moved and mojito-ed to obtain a better score.

#### Greedy and threshold shakers

Turning an invalid pose into a valid one is not trivial. It’s much easier to start with a valid pose and see how far we can improve it without breaking validity. And that was the idea behind greedy shaker. Besides preserving validity, it is guaranteed not to increase dislikes.

The algorithm is simple: first, we move each vertex to its best scoring valid position, and keep doing it until the score can no longer be improved. Then, we randomly move some vertices to new valid positions, even if it doesn’t change the score. This second step shakes up “internal” vertices, hopefully creating more space for “corner” vertices to move. Rinse and repeat.

The next validity preserving shaker implemented the threshold acceptance algorithm (a simpler version of simulated annealing) – i.e.: randomly move vertices to new valid positions, even if doing so increases dislikes, based on a threshold function.

Because we hadn’t implemented any higher-level pose transformations, the threshold shaker, being limited to moving vertices one by one, didn’t seem very useful at the time. Thus, almost no time was spent tuning the threshold function, which may have resulted in some wasted iterations.

Yet it was still capable of finding improved solutions.

### Solvers

With more than one hundred problem instances, it didn’t look like we could get by with manually creating solutions in the visualizer. We made several attempts at fully automated solvers.

#### A solver code-named “rail”

The purpose of this algorithm is to produce any solutions that satisfy all the constraints. It does not attempt to explicitly minimize dislikes. Instead, it produces a stream of random solutions and picks the best one.

A single run of the algorithm looks like this. We place vertices one by one. We never move a vertex after it’s placed. And we only place a vertex if all its edges to already placed vertices satisfy geometric constraints. When all vertices are placed, we evaluate the result and see if it’s an improvement over anything found so far. When the next vertex can’t be placed at all, we are in a dead end, and the process restarts from the beginning.

There are two choices that govern this process.

First, when placing a vertex, which location among the ones satisfying the constraints do we choose? We just pick a random one for simplicity.

Second, in what order do we place the vertices? Here, we take the heuristic commonly used in backtracking algorithms and constraint solving. At each step, we pick a vertex that has the smallest set of allowed locations. Informally, if the vertex has two allowed locations, we’ll guess correctly with a probability of 50%, and if the vertex has 100 possible locations, the chances are 1%, so it’s better to take a 50% chance. In practice, this means that the most demanding constraints are explored and satisfied first. For example, if we already placed two vertices of a rigid triangle, we will place the third one immediately. This, in turn, allows quickly propagating other constraints and determining if the solution is viable.

#### Sergey’s multishaker solver

Even though “rail” got us out of the bottom of the score sheet and put us into the middle of the field, many solutions had room for improvement.

The process of manually applying different shakers in the visualizer to escape local minima served as an inspiration.

Sergey figured that we should work with what we have and composed several shakers into an automatic solver, dubbed multishaker. The idea behind multishaker was to use mojito to try and transform the initial figure into a valid pose to which greedy and threshold shakers could then be applied.

As the first step, all out-of-bounds vertices and edges were moved inside the hole, followed by mojito shaking the pose. This was done repeatedly until a valid pose was obtained. In most cases the process converged quickly, though sometimes it didn’t converge at all.

It also tended to work better the fewer vertices had to be moved into the hole. This is because we moved them one by one without regard to edge constraints. Consider problem 126.

In this extreme case, the initial pose was being destroyed completely and the task of satisfying edge constraints was left entirely to mojito, even though the initial pose was already valid with respect to edge lengths! The quick and dirty fix was to shift the entire initial pose first so that its center of mass would coincide with the hole’s center of mass.

Once a valid pose had been obtained, multishaker would alternate between greedy and threshold shaker in an infinite loop. Whenever an improved solution was found it was submitted automatically.

This bumped us from ~60th place to 36th.

### An attempt to make use of bonuses

If we ignore bonuses, all problem instances are independent, and of all solutions for each problem instance, we are only interested in one that minimizes the number of dislikes.

Things get more complicated if we take bonuses into consideration. Now, there are three dimensions to evaluate a solution on: number of dislikes (the fewer, the better), which bonus spots does it grab (the more, the better), and which bonuses does it rely upon to be valid (the fewer, the better). All solutions below the Pareto frontier can be discarded as inferior, but it still leaves us with more than one candidate for each problem instance.

That is, if we manage to come up with the candidates in the first place. We made changes to the rail solver to take into account which bonus spots the solution grabs and also to make use of the SUPERFLEX bonus which allowed one edge to stretch without limit. This was the easiest bonus to support in the solver.

Running this modified solver on all problems, we amassed a collection of candidates.

As a final ingredient, we needed a global optimizer that will choose candidate solutions for all problem instances together. This would allow sacrificing dislikes in one problem instance in order to grab a bonus that will save more dislikes in another problem instance.

Unfortunately, we failed to do this before the contest deadline. So all this bonus work was in vain. And it temporarily tanked our standings because we were submitting non-optimal solutions. Luckily, we had a fallback plan.

### Ilona’s submission decider

Closer to the end of the contest, we realized that we needed a failsafe in case our attempts to globally optimize for bonuses went nowhere: a ‘big red button’ that would resubmit our historical best for each problem. Submitting poses that use bonuses naturally led to non-optimal scores until the bonus cycle was complete, especially with our imperfect solvers. So it was crucial to have a fallback plan.

The infrastructure part of the team completed this entry point with hours to spare.

In the end, it:

• Skipped poses that used any bonuses. The reasoning behind this was that bonuses formed chains. If the pose that unlocked the bonus used in this high-scoring solution would be overwritten because some other score was higher (lower), we didn’t want to get stuck with an invalidated pose.
• Did not bother resubmitting for problems where the high score was already achieved to avoid clogging up the submission pipeline.

The last few minutes were tense, as the decider and the solvers running on the last few select problems were fighting for submission cooldown, but we managed to pull everything through – including the clutch last-minute manual submission for #90 that brought us from 36 to 35!

## What we could have done better

### Solution DB

In order to pick the best solution for each problem instance in the end, problems of this kind naturally call for a solution database that can be populated by different solvers running on different machines.

This year, we decided to cut corners and piggyback on the contest infrastructure. The contest website provides the submission history, so we thought we could use it as a poor man’s substitute for the solution database. This approach kind of worked, but all in all we consider it a failed experiment.

The system enforced a 5-minute delay between submissions for the same problem instance. Let’s say we run a solver, and it finds a solution in 10 seconds and submits it. Then it keeps running and in another 10 seconds finds an improvement. It has to wait 290 seconds before it can submit this improvement. We can’t stop it before that because otherwise the improvement will be lost.

Another inconvenience is that the contest system provided an API for submitting solutions but not for accessing the submission history. In order to access the history programmatically, we had to scrape HTML pages intended for humans.

And to ensure availability and to avoid unnecessarily burdening the contest server, we ended up creating a local solution cache anyway.

It would have been better if we had set up a proper DB from the beginning.

### Programming language

The choice of the right language caused heated debates after the end of the contest.

• Should we reconcile with the steep learning curve, sad compilation times, and usize as i32 as usize ceremony for the sake of performance, reliability, and handy type hints – and stick with Rust?
• Should we trade performance and static typing for coding productivity and better libraries – and switch to Python?
• Should we chase performance and productivity both and get into a double trouble of prototyping in Python and rewriting in C++, and gluing them into one monstrosity, as we did in some previous contests?
• Should we opt for a shiny fancy language that will attract more participants?
• Should we descend into the chaos of polyglot development – and let everyone choose their own language?
• Should we kill all the dispute by choosing some esoteric language no one has heard of – say, Zig? (No, Pharo. Or Gleam? Are we getting into a new heated debate?)

We genuinely don’t know what we will use next year (though, of course, it will be Rust).

### GUI toolkit

We chose Web UI because it’s cross-platform, has great debugging tools, and can be as low- or high- level as needed.

However, the client-server separation and the HTTP model mean that even a tiny UI feature takes annoyingly many steps to implement:

• Define request and response types (both in Rust and in TypeScript).
• Update elements on the static HTML pages.
• Update the TypeScript code, possibly in multiple places.
• Add a route in the Rust web server.
• Add actual feature implementation in Rust.

Can we keep the benefits while somehow mitigating the drawbacks? We don’t know yet.

## Our awesome team members

Here’s everyone that participated in the contest in the team TBD this year. We would like to thank all of them for the time well spent and their input! Vlad, Jonn, Julie, Sergey and Ilona also contributed to help this article happen.

• Vlad. Advocating for Rust, unproductively obsessing over everything, computational geometry, “rail” solver, an attempt to use bonuses.
• Ilona. UI features, contest Web UI scraping, and the fallback submitter.
• Pavel. Algorithms, spring shaker, and work on a spring-like solution.
• Jonn. Contributing to the visualiser, solver operations, community management and outreach.
• Sergey. Greedy and threshold shakers, the multishaker solver.
• Julie. Visualiser. Some of the shakers. Keeping our rules implementation up to date with changing requirements (bonuses).

## And that’s it

In the end, we got 35th place.

If you want to browse our source code, here’s the repository.

By the way, some of the more active people on the contest Discord made a Discord server called Intermediate Competitive but Friendly Programming Club, where multi-team practice will be organized. You are welcome to join.

See you next year! 👋

More from Serokell


text:
# data

• Wenzhao Lian and Vinayak Rao and Brian Eriksson and Lawrence Carin

### Modeling Correlated Arrival Events with Latent Semi-Markov Processes (pdf)

The analysis and characterization of correlated point process data has wide applications, ranging from biomedical research to network analysis. In this work, we model such data as generated by a latent collection of continuous-time binary semi-Markov processes, corresponding to external events appearing and disappearing. A continuous-time modeling framework is more appropriate for multichannel point process data than a binning approach requiring time discretization, and we show connections between our model and recent ideas from the discrete-time literature. We describe an efficient MCMC algorithm for posterior inference, and apply our ideas to both synthetic data and a real-world biometrics application.

• Sergey Bartunov and Dmitry Vetrov

### Variational Inference for Sequential Distance Dependent Chinese Restaurant Process (pdf)

Recently proposed distance dependent Chinese Restaurant Process (ddCRP) generalizes extensively used Chinese Restaurant Process (CRP) by accounting for dependencies between data points. Its posterior is intractable and so far only MCMC methods were used for inference. Because of very different nature of ddCRP no prior developments in variational methods for Bayesian nonparametrics are appliable. In this paper we propose novel variational inference for important sequential case of ddCRP (seqddCRP) by revealing its connection with Laplacian of random graph constructed by the process. We develop efficient algorithm for optimizing variational lower bound and demonstrate its efficiency comparing to Gibbs sampler. We also apply our variational approximation to CRP-equivalent seqddCRP-mixture model, where it could be considered as alternative to one based on truncated stick-breaking representation. This allowed us to achieve significantly better variational lower bound than variational approximation based on truncated stick breaking for Dirichlet process.

• Taiji Suzuki

### Stochastic Dual Coordinate Ascent with Alternating Direction Method of Multipliers (pdf)

We propose a new stochastic dual coordinate ascent technique that can be applied to a wide range of regularized learning problems. Our method is based on alternating direction method of multipliers (ADMM) to deal with complex regularization functions such as structured regularizations. Although the original ADMM is a batch method, the proposed method offers a stochastic update rule where each iteration requires only one or few sample observations. Moreover, our method can naturally afford mini-batch update and it gives speed up of convergence. We show that, under mild assumptions, our method converges exponentially. The numerical experiments show that our method actually performs efficiently.

• Yarin Gal and Zoubin Ghahramani

### Pitfalls in the use of Parallel Inference for the Dirichlet Process (pdf)

Recent work done by Lovell, Adams, and Mansingka (2012) and Williamson, Dubey, and Xing (2013) has suggested an alternative parametrisation for the Dirichlet process in order to derive non-approximate parallel MCMC inference for it  work which has been picked-up and implemented in several different fields. In this paper we show that the approach suggested is impractical due to an extremely unbalanced distribution of the data. We characterise the requirements of efficient parallel inference for the Dirichlet process and show that the proposed inference fails most of these requirements (while approximate approaches often satisfy most of them). We present both theoretical and experimental evidence, analysing the load balance for the inference and showing that it is independent of the size of the dataset and the number of nodes available in the parallel implementation. We end with suggestions of alternative paths of research for efficient non-approximate parallel inference for the Dirichlet process.

• Nan Du and Yingyu Liang and Maria Balcan and Le Song

### Influence Function Learning in Information Diffusion Networks (pdf)

Can we learn the influence of a set of people in a social network from cascades of information diffusion? This question is often addressed by a two-stage approach: first learn a diffusion model, and then calculate the influence based on the learned model. Thus, the success of this approach relies heavily on the correctness of the diffusion model which is hard to verify for real world data. In this paper, we exploit the insight that the influence functions in many diffusion models are coverage functions, and propose a novel parameterization of such functions using a convex combination of random basis functions. Moreover, we propose an efficient maximum likelihood based algorithm to learn such functions directly from cascade data, and hence bypass the need to specify a particular diffusion model in advance. We provide both theoretical and empirical analysis for our approach, showing that the proposed approach can provably learn the influence function with low sample complexity, be robust to the unknown diffusion models, and significantly outperform existing approaches in both synthetic and real world data.

• Uri Shalit and Gal Chechik

### Coordinate-descent for learning orthogonal matrices through Givens rotations (pdf)

Optimizing over the set of orthogonal matrices is a central component in problems like sparse-PCA or tensor decomposition. Unfortunately, such optimization is hard since simple operations on orthogonal matrices easily break orthogonality, and correcting orthogonality usually costs a large amount of computation. Here we propose a framework for optimizing orthogonal matrices, that is the parallel of coordinate-descent in Euclidean spaces. It is based on {\em Givens-rotations

• Qinxun Bai and Henry Lam and Stan Sclaroff

### A Bayesian Framework for Online Classifier Ensemble (pdf)

We propose a Bayesian framework for recursively estimating the classifier weights in online learning of a classifier ensemble. In contrast with past methods, such as stochastic gradient descent or online boosting, our framework estimates the weights in terms of evolving posterior distributions. For a specified class of loss functions, we show that it is possible to formulate a suitably defined likelihood function and hence use the posterior distribution as an approximation to the global empirical loss minimizer. If the stream of training data is sampled from a stationary process, we can also show that our framework admits a superior rate of convergence to the expected loss minimizer than is possible with standard stochastic gradient descent. In experiments with real-world datasets, our formulation often performs better than online boosting algorithms.

• Rajhans Samdani and Kai-Wei Chang and Dan Roth

### A Discriminative Latent Variable Model for Online Clustering (pdf)

This paper presents a latent variable structured prediction model for discriminative supervised clustering of items called the Latent Left-linking Model (L3M). We present an online clustering algorithm for L3M based on a feature-based item similarity function. We provide a learning framework for estimating the similarity function and present a fast stochastic gradient-based learning technique. In our experiments on coreference resolution and document clustering, L3 M outperforms several existing online as well as batch supervised clustering techniques.

• Felix Yu and Sanjiv Kumar and Yunchao Gong and Shih-Fu Chang

Binary embedding of high-dimensional data requires long codes to preserve the discriminative power of the input space. Traditional binary coding methods often suffer from very high computation and storage costs in such a scenario. To address this problem, we propose Circulant Binary Embedding (CBE) which generates binary codes by projecting the data with a circulant matrix. The circulant structure enables the use of Fast Fourier Transformation to speed up the computation. Compared to methods that use unstructured matrices, the proposed method improves the time complexity from $\mathcal{O • Justin Solomon and Raif Rustamov and Guibas Leonidas and Adrian Butscher ### Wasserstein Propagation for Semi-Supervised Learning (pdf) Probability distributions and histograms are natural representations for product ratings, traffic measurements, and other data considered in many machine learning applications. Thus, this paper introduces a technique for graph-based semi-supervised learning of histograms, derived from the theory of optimal transportation. Our method has several properties making it suitable for this application; in particular, its behavior can be characterized by the moments and shapes of the histograms at the labeled nodes. In addition, it can be used for histograms on non-standard domains like circles, revealing a strategy for manifold-valued semi-supervised learning. We also extend this technique to related problems such as smoothing distributions on graph nodes. • Hsiang-Fu Yu and Prateek Jain and Purushottam Kar and Inderjit Dhillon ### Large-scale Multi-label Learning with Missing Labels (pdf) The multi-label classification problem has generated significant interest in recent years. However, existing approaches do not adequately address two key challenges: (a) scaling up to problems with a large number (say millions) of labels, and (b) handling data with missing labels. In this paper, we directly address both these problems by studying the multi-label problem in a generic empirical risk minimization (ERM) framework. Our framework, despite being simple, is surprisingly able to encompass several recent label-compression based methods which can be derived as special cases of our method. To optimize the ERM problem, we develop techniques that exploit the structure of specific loss functions - such as the squared loss function - to obtain efficient algorithms. We further show that our learning framework admits excess risk bounds even in the presence of missing labels. Our bounds are tight and demonstrate better generalization performance for low-rank promoting trace-norm regularization when compared to (rank insensitive) Frobenius norm regularization. Finally, we present extensive empirical results on a variety of benchmark datasets and show that our methods perform significantly better than existing label compression based methods and can scale up to very large datasets such as a Wikipedia dataset that has more than 200,000 labels. • Stanislav Minsker and Sanvesh Srivastava and Lizhen Lin and David Dunson ### Scalable and Robust Bayesian Inference via the Median Posterior (pdf) Many Bayesian learning methods for massive data benefit from working with small subsets of observations. In particular, significant progress has been made in scalable Bayesian learning via stochastic approximation. However, Bayesian learning methods in distributed computing environments are often problem- or distribution-specific and use ad hoc techniques. We propose a novel general approach to Bayesian inference that is scalable and robust to corruption in the data. Our technique is based on the idea of splitting the data into several non-overlapping subgroups, evaluating the posterior distribution given each independent subgroup, and then combining the results. The main novelty is the proposed aggregation step which is based on finding the geometric median of posterior distributions. We present both theoretical and numerical results illustrating the advantages of our approach. • Roni Mittelman and Benjamin Kuipers and Silvio Savarese and Honglak Lee ### Structured Recurrent Temporal Restricted Boltzmann Machines (pdf) The Recurrent temporal restricted Boltzmann machine (RTRBM) is a probabilistic model for temporal data, that has been shown to effectively capture both short and long-term dependencies in time-series. The topology of the RTRBM graphical model, however, assumes full connectivity between all the pairs of visible and hidden units, therefore ignoring the dependency structure between the different observations. Learning this structure has the potential to not only improve the prediction performance, but it can also reveal important patterns in the data. For example, given an econometric dataset, we could identify interesting dependencies between different market sectors; given a meteorological dataset, we could identify regional weather patterns. In this work we propose a new class of RTRBM, which explicitly uses a dependency graph to model the structure in the problem and to define the energy function. We refer to the new model as the structured RTRBM (SRTRBM). Our technique is related to methods such as graphical lasso, which are used to learn the topology of Gaussian graphical models. We also develop a spike-and-slab version of the RTRBM, and combine it with our method to learn structure in datasets with real valued observations. Our experimental results using synthetic and real datasets, demonstrate that the SRTRBM can improve the prediction performance of the RTRBM, particularly when the number of visible units is large and the size of the training set is small. It also reveals the structure underlying our benchmark datasets. • Uri Heinemann and Amir Globerson ### Inferning with High Girth Graphical Models (pdf) Unsupervised learning of graphical models is an important task in many domains. Although maximum likelihood learning is computationally hard, there do exist consistent learning algorithms (e.g., psuedo-likelihood and its variants). However, inference in the learned models is still hard, and thus they are not directly usable. In other words, given a probabilistic query they are not guaranteed to provide an answer that is close to the true one. In the current paper, we provide a learning algorithm that is guaranteed to provide approximately correct probabilistic inference. We focus on a particular class of models, namely high girth graphs in the correlation decay regime. It is well known that approximate inference (e.g, using loopy BP) in such models yields marginals that are close to the true ones. Motivated by this, we propose an algorithm that always returns models of this type, and hence in the models it returns inference is approximately correct. We derive finite sample results guaranteeing that beyond a certain sample size, the resulting models will answer probabilistic queries with a high level of accuracy. Results on synthetic data show that the models we learn indeed outperform those obtained by other algorithms, which do not return high girth graphs. • Alekh Agarwal and Sham Kakade and Nikos Karampatziakis and Le Song and Gregory Valiant ### Least Squares Revisited: Scalable Approaches for Multi-class Prediction (pdf) This work provides simple algorithms for multi-class (and multi-label) prediction in settings where both the number of examples$n$and the data dimension$d\$ are relatively large. These robust and parameter free algorithms are essentially iterative least-squares updates and very versatile both in theory and in practice. On the theoretical front, we present several variants with convergence guarantees. Owing to their effective use of second-order structure, these algorithms are substantially better than first-order methods in many practical scenarios. On the empirical side, we show how to scale our approach to high dimensional datasets, achieving dramatic computational speedups over popular optimization packages such as Liblinear and Vowpal Wabbit on standard datasets (MNIST and CIFAR-10), while attaining state-of-the-art accuracies.

2013-2014 ICML | International Conference on Machine Learning


text:
# Functional Derivative fail

1. Jan 16, 2012

### Elwin.Martin

Alright, so I feel kind of dumb...but:

I have been working on some QFT material, specifically derivation of Feynman rules for some more simple models ($\phi^{4}$ for example), and I have been seriously failing with functional derivatives. Every time I try to use the definition I mess up somewhere. Usually, my best bet is to sort of treat it like a regular derivative and use some intuition, but that's not really legitimate.

Oh, the Δ here is the Feynman propagator, I'm not sure what the standard is for notation so I suppose I should mention that.

Take for example $\frac{1}{i}\frac{\delta}{\delta J(z)} exp\left[-\frac{i}{2}\int J(x)\Delta_{F}(x-y)J(y)dxdy\right]$

So what I'm supposed to get is
$- \int \Delta (z-x)_{F} J(x) dx \ exp \left[-\frac{i}{2} \int J(x) \Delta_{F}(x-y)J(y)dx dy \right]$

And I can rationalize it as that we have an exponential and we treat exponential derivatives as we do traditionally, but then I get confused with where my factor of 1/2 went from the exponent...clearly, the i's cancel, but where did the two go? I have a feeling it has to do with the repeat of the J's in the J Δ J but I'm not sure.

Ugh. . .this has wasted so very much of my time.

Not to mention, I've yet to convince myself that we ARE allowed to treat an exponential the same way, though I think I might have an idea how to show it, I'm not sure how common identities like product rule would be proved with functionals.

If someone could give me something to read over or something that would be awesome. I've looked for a while and not found much help. I found a paper by Feynman on Operator Calculus that had an Appendix relating to functionals but that didn't really help ^^;...

2. Jan 17, 2012

### tom.stoer

$$\frac{\partial}{\partial x_i}\text{exp}\left[-\frac{1}{2}\,x_m\,A_{mn}\,x_n\right]$$

with a symmetric matrix A and a sum over indices m,n

3. Jan 17, 2012

### Elwin.Martin

Okay, so the 1/2 gets absorbed in quadratic terms for m=n and then absorbed in the symmetry otherwise.

And for my case we treat the JΔJ term likewise. . .Wait that looks familiar .-. I lose.

Like the form $\int exp \left[ \frac{-1}{2} \int \phi (x) A \phi (x)dx\right]$

with A being a differential operator we get (det A)-1/2 .-. I'm an idiot, I've seen this before and forgot. I thought that the discrete problem you typed looked familiar.

Thank you!


text:
## Problem with hyperfootnotes

Dear users:

I'm using the "revtex4" style to type a math document, together with the hyperref package. While I can get hyperlinks to equations and references, I haven't been able to get hyperlinks to footnotes. I put the \usepackage{hyperref} as the last line of the preamble, as indicated in many manuals, but it didn't work.

Nevertheless, when I change the style from revtex4 to "article" I do get the footnotes hyperlinked, so it seems to be a conflict between the style revtex4 and the package hyperref.

In case it may help, this is the preamble of my doc:

\documentclass[letterpaper,amsmath,amssymb,nofootinbib]{revtex4}
\usepackage{latexsym}
\usepackage{amsmath, amsthm,amssymb}
\usepackage{amsfonts,dsfont}
\usepackage{graphicx}
\usepackage{empheq}

\numberwithin{equation}{section}

\usepackage[pdftex, pdfstartview = {FitH}]{hyperref}

\begin{document}

Any help, advice or tips on this issue would be greatly appreciated.

Thank you very much in advance!


text:
## Focus Control Scores

Discussions on extending SharpCap using the built in Python scripting functionality
HappySkies
Posts: 4
Joined: Sat Apr 27, 2019 9:29 pm

### Focus Control Scores

I see that I can access focus controls, but I'm trying to get the Scores both "Now" and "Best". Can someone show me how I can get the results of the scores once you change the focus position? Attached is a picture of what I'm talking about. Thanks in advance for your help!
Attachments
Sharp Cap Focus Scores
SharpCapFocus.png (14.87 KiB) Viewed 391 times

Posts: 3281
Joined: Sat Feb 11, 2017 3:52 pm
Location: Vale of the White Horse, UK
Contact:

### Re: Focus Control Scores

Hi,

Sorry to say that this is currently not possible to achieve via scripting at the moment, and having had a look at the code it's not a simple change to make either.

Cheers, Robin

Posts: 3281
Joined: Sat Feb 11, 2017 3:52 pm
Location: Vale of the White Horse, UK
Contact:

### Re: Focus Control Scores

Actually, not quite as hard as I imagined. Watch out for the next update to 3.2 and then try

Code: Select all

print SharpCap.Transforms.SelectedTransform.FrameTransform.CurrentScore

cheers, Robin

HappySkies
Posts: 4
Joined: Sat Apr 27, 2019 9:29 pm

### Re: Focus Control Scores

Wow, thank you so much! This is really awesome. Looking forward to the next update.

### Who is online

Users browsing this forum: No registered users and 0 guests


text:
# Generating functions with all non-zero coefficients equal to one

Inspired by this question, I have been wondering if there are any useful generating functions with all non-zero coefficients equal to one. Obviously, the trivial generating function $\frac{1}{1-x}$ has significant applications, as do monomial symmetric functions but for the purposes of this question, we should ignore them. As Graham has commented, indicator functions also fall into this category. The best formulation I can think of for why these should be ignored is that they are most interesting for the purpose of taking products of generating functions, rather than being directly used for computation.

More specifically, such a generating function would (in my mind) have to be multi-variate, enumerate some object of interest and facilitate computations related to that object in a situation where direct computation is not straightforward. As an example of what I would consider cheating, by specializing many variables to one, the generating function in the aforementioned question allows for computing joint distributions of entries in a reduced word with great ease. However, to compute the generating function, it seems to me one would have to enumerate all such words anyways, hence no labor is saved. Were this not the case, this function would be an excellent example.

What would be an example of such a generating function where computation is assisted without being embedded in constructing the generating function? Even if the generating function serves as a useful book keeping device, that would be okay.

Please comment below with any suggested improvements for what should define a "useful" generating function. Explanations for why such a function cannot exist are welcome as well.

Edit 1: Added Graham's comment on indicator functions.

-
I was actually thinking of a similar question the other day, although I was approaching it from the viewpoint of whether there is some nice $\mathcal{S}$- (or $\mathcal{A}$-) regular language for which there is a finite complete set of ($\mathbb{N}$-valued) invariants; the values of these invariants would of course be the exponents of the variables in each monomial. On the other hand, I suppose I may be restricting myself too much by asking for a regular language as this necessarily forces the associated generating function to be rational... –  ARupinski Jul 23 '13 at 1:23
You probably mean to say that all coefficients are equal to zero or one. In which case, in $n$ variables, you can identify your generating function with the indicator function of (any) subset of lattice points in ${\mathbb N}^n$. So your question is, in this sense, universal. Can you narrow it? –  Graham Denham Jul 23 '13 at 2:06

## 1 Answer

Although you say you're not interested in examples with indicator functions, I think there are some examples with indicator functions of polytopes that fit your criteria. I'm writing this answer because I don't think they have the same flavor which you are trying to rule out.

To every lattice point one may associate a Laurent monomial and therefore to every polytope we may associate the sum of all such monomials corresponding to lattice points inside the polytope. This (possibly huge) Laurent polynomial is very important, for example, when one cares about weighted enumeration of lattice points inside polytopes and other facts.

Brion's formula allows one to write this Laurent polynomial as the sum of generating functions of the lattice points of the vertex cones of the polytope. Even though generating functions for cones feel easier than computing this indicator function for the polytope itself, it is not apriori obvious that this makes the computation faster.

However Barvinok's theorem uses Brion's formula together with a decomposition of cones into unimodular cones to conclude that this computation can be done in polynomial time. You can read Barvinok's "A polynomial time algorithm for counting integral points in polyhedra when the dimensionis fixed", Math. Oper. Res. 19 (1994), 769–779.

This is in my opinion one of the nicest results that uses generating functions with 0/1 coefficients in addition to some geometric fact to help compute a combinatorial function very fast. There are of course applications in Ehrhart theory etc.

-


text:
# Regarding the Cartier divisor of zero and Hartshorne II 7.7

I cannot quite understand Hatshorne's wording in the Cartier divisor of zero, which is given as follows.

I would like to have some further explanation over the definition and ananalogy in terms of Weil divisor. Base on this definition, I cannot quite follow the proof of one of the statements in Proposition 7.7. Which is:

Explicitly, I cannot understand why the given $$f$$ will satisfy the desired property. Namely, why the divisor of zero of $$f$$ is $$D$$.

------Edited 17/10/2019------------

I now have a more explicit idea on what I would like to ask. My question's still surrounding 7.7 (b). I perfectly understand by linear equivalence, we can write $$D=D_0+(f)$$ and $$f$$ will define a global section $$s\in\Gamma(X,\mathscr{L})$$. By result of (a), the divisor of zero of $$s$$, $$(s)_0=D_1$$, where $$D_1$$ is certain effective Cartier divisor.

Now, my question is: How can I show $$D=D_1$$, the exact equivalence?

• You might find 'my' answer to math.stackexchange.com/questions/1994463/… helpful: – peter a g Oct 13 at 3:54
• Sorry that my earlier question statement didn't address my concern clearly. Now I hope this will give a better picture. – IvanSo Oct 17 at 5:45

Now Apparently I have an idea. $$D=D_0+(f)$$ gives the linear equivalence of divisors and $$f$$ define a global section $$s\in\Gamma(X,\mathscr{L})$$ as mentioned in the first statement of the proof of (b).
What's missing is just the isomorphism to $$\mathscr{O}_{U_i}$$, which actually had been defined (a) to be a morphism $$\varphi$$ gluing the set $$\{\varphi_i:f\in\Gamma(X,\mathscr{L})\mapsto ff_i\in\Gamma(X,\mathscr{O}_{U_i})\}$$.


text:
# Macro based flags for forest tree

I'm using simple y/n macros as flags in my document to include or exclude certain parts of the overall document (these normally are in a separate "config.tex" file for ease of use). With the forest package, I get strange results when using this approach (using pdftex). The inserted texts seem to be interpreted as text instead of added or non-added leaves.

Minimum working example:

\documentclass[]{scrreprt}

\usepackage{ifthen}
\usepackage[edges]{forest}

\newcommand{\hasOptionOne}{y}
\newcommand{\hasOptionFour}{y}

\begin{document}

The user has the following options:
\begin{itemize}
\item Option Two
\item Option Three
\end{itemize}

\begin{figure}
\centering
\caption{Available Options}
\label{fig-available-options}
\begin{forest}
for tree={draw,align=center},
forked edges,
[Main item
[Option Two]
[Option Three]
]
\end{forest}
\end{figure}

\end{document}

Result:

• forest has a highly sophisticated and powerful parser. I believe it is practically hopeless to try to trick it this way, You would have to makes sure that forest sees the expanded version of these \AddIfs, but the way you construct this command, already \edef\temp{\AddIf{\hasOptionOne}{\item Option One}{}} fails. So I would like to argue that you should resort to pure forest methods to achieve what you want. – user121799 Jan 29 '19 at 17:52
• Hi marmot. Can you suggest any pure forest methods that can be somehow connected to (possibly differently designed) flags outside the forest environment? I'd be happy to use them, but as I need these flags to be set centrally for the entire document, I'm not sure how to connect these two worlds. – Michael Jan 30 '19 at 8:34
• I added one example. Quite possible that there exist alternatives. (Just for the records, I usually try to avoid using the ifthen package because of such issues.) – user121799 Jan 30 '19 at 13:59

Since you asked for it... I replaced your command \AddIf by some version that can be appropriately expanded. And then a trick is used that has also some applications in pgfplots and so on. It makes sure that the content of the tree gets expanded first, and then it gets passed to forest.

\documentclass[]{scrreprt}

% \usepackage{ifthen} % no longer used here
\usepackage[edges]{forest}
\newcommand{\Yes}{y}
#2%
\else
#3%
\fi}

\newcommand{\hasOptionOne}{y}
\newcommand{\hasOptionFour}{y}

\begin{document}

The user has the following options:
\begin{itemize}
\item Option Two
\item Option Three
\end{itemize}

\begin{figure}
\centering
\caption{Available Options}
\label{fig-available-options}
\edef\temp{\noexpand\begin{forest}
for tree={draw,align=center},
forked edges,
[Main item
[Option Two]
[Option Three]

• @Michael Did you try to replace  \ by \noexpand\? – user121799 Jan 31 '19 at 16:59


text:
Find all School-related info fast with the new School-Specific MBA Forum

 It is currently 09 Feb 2016, 17:01

### GMAT Club Daily Prep

#### Thank you for using the timer - this advanced tool can estimate your performance and suggest more practice questions. We have subscribed you to Daily Prep Questions via email.

Customized
for You

we will pick new questions that match your level based on your Timer History

Track

every week, we’ll send you an estimated GMAT score based on your performance

Practice
Pays

we will pick new questions that match your level based on your Timer History

# Events & Promotions

###### Events & Promotions in June
Open Detailed Calendar

# Hard probability problem: 2 dice sum of 3 BEFORE sum of 7

Author Message
TAGS:
Intern
Joined: 15 Apr 2010
Posts: 48
Followers: 0

Kudos [?]: 24 [0], given: 11

Hard probability problem: 2 dice sum of 3 BEFORE sum of 7 [#permalink]  06 Oct 2010, 00:21
1
This post was
BOOKMARKED
00:00

Difficulty:

(N/A)

Question Stats:

50% (00:00) correct 50% (00:02) wrong based on 1 sessions

You have two dice, what is the probability of rolling a sum of 3 BEFORE rolling a sum of 7?

Thanks..
Retired Moderator
Joined: 02 Sep 2010
Posts: 805
Location: London
Followers: 92

Kudos [?]: 715 [0], given: 25

Re: Hard probability problem: 2 dice sum of 3 BEFORE sum of 7 [#permalink]  06 Oct 2010, 00:47
catennacio wrote:

You have two dice, what is the probability of rolling a sum of 3 BEFORE rolling a sum of 7?

Thanks..

Can you define the problem more precisely ?

You start rolling the dice, and the sum of two dice is 3, but the third dice adds up to a 7 ?

Or do u roll three dice twice, and the first time you get a 3 and the second time a 7 ?
_________________
Math Expert
Joined: 02 Sep 2009
Posts: 31288
Followers: 5352

Kudos [?]: 62275 [1] , given: 9445

Re: Hard probability problem: 2 dice sum of 3 BEFORE sum of 7 [#permalink]  06 Oct 2010, 02:39
1
KUDOS
Expert's post
catennacio wrote:

You have two dice, what is the probability of rolling a sum of 3 BEFORE rolling a sum of 7?

Thanks..

First of all please note that this question is far beyond the GMAT scope.

$$P(sum=3)=\frac{2}{36}=\frac{1}{18}$$: either (1,2) or (2,1) out of total of 36 different combinations of two dice;

$$P(sum=7)=\frac{6}{36}=\frac{1}{6}$$: (1,6), (2,5), (3,4), (4,3), (5,2), or (6,1);

$$P(other \ sum)=1-(\frac{1}{18}+\frac{1}{6})=\frac{7}{9}$$, probability of sums: 4, 5, 6, 8, 9, 10, 11, and 12;

Winning scenarios:
{sum=3} - we have sum of 3 on the first roll of two dice - $$P_1=\frac{1}{18}$$;
{other sum; sum=3} - on the first roll we have other sum and sum of 3 on the second roll - $$P_2=\frac{7}{9}*\frac{1}{18}$$;
{other sum; other sum; sum=3} - $$P_3=(\frac{7}{9})^2*\frac{1}{18}$$;
{other sum; other sum; other sum; sum=3} - $$P_4=(\frac{7}{9})^3*\frac{1}{18}$$;
...

So probability of rolling a sum of 3 BEFORE rolling a sum of 7 would be the sum of the above infinite series:
$$P=\frac{1}{18}+\frac{7}{9}*\frac{1}{18}+(\frac{7}{9})^2*\frac{1}{18}+(\frac{7}{9})^3*\frac{1}{18}+...=\frac{1}{18}(1+\frac{7}{9}+(\frac{7}{9})^2+(\frac{7}{9})^3+...)=\frac{1}{18}(1+\frac{\frac{7}{9}}{1-\frac{7}{9}})=\frac{1}{18}(1+\frac{7}{2})=\frac{1}{4}$$ (for geometric progression with common ratio $$|q|<1$$, the sum of the progression: $$b_1, b_2, ...$$ is $$Sum=\frac{b_1}{1-q}$$.).

OR:

As $$P(sum=3)=\frac{2}{36}$$ and $$P(sum=7)=\frac{6}{36}$$ then getting the sum of 7 is 3 times more likely than getting the sum of 3, so the sum of 3 has 1 chance out of 4 to get first out of any number of tries, so $$P=\frac{1}{4}$$ or $$P=\frac{\frac{2}{36}}{\frac{2}{36}+\frac{6}{36}}=\frac{1}{4}$$.

Hope it's clear.
_________________
Manager
Joined: 25 Jun 2010
Posts: 91
Followers: 1

Kudos [?]: 28 [0], given: 0

Re: Hard probability problem: 2 dice sum of 3 BEFORE sum of 7 [#permalink]  06 Oct 2010, 04:29
Excellently done Bunuel!

Posted from my mobile device
Intern
Joined: 15 Apr 2010
Posts: 48
Followers: 0

Kudos [?]: 24 [0], given: 11

Re: Hard probability problem: 2 dice sum of 3 BEFORE sum of 7 [#permalink]  06 Oct 2010, 15:42
Thank you very much Buneul for your answer. However I have a few questions:

I understand up to P(other sum). How can you conclude the winning scenario is other sum then sum 3? I know it's a possible case, but why is it (other sum, sum 3) will lead to a (other sum, sum 3, then sum 7). It could be (other sum, sum 3, sum 8) - after 3 rollings, while what we expect is sum 7. Therefore the (other sum, other sum,..., sum 3) could be a wrong case.

On the other hand, if we can conclude other sum, other sum,..., sum 3 is a winning scenario, have we assume the probability of sum 7 and other sum but not 7 are the same, while there are different?

I don't understand this sentence too "So probability of rolling a sum of 3 BEFORE rolling a sum of 7 would be the sum of the above infinite series" - how can you conclude it's the sum that series, how about if we have an AFTER word? What is the difference between BEFORE and AFTER?

Edit: I like your second approach, by comparing the fraction of the probability of 2 events we can say P = 1/4, but I still don't understand the word BEFORE.. What if they ask for AFTER? Will we still compare the 2 probabilities?
Math Expert
Joined: 02 Sep 2009
Posts: 31288
Followers: 5352

Kudos [?]: 62275 [0], given: 9445

Re: Hard probability problem: 2 dice sum of 3 BEFORE sum of 7 [#permalink]  07 Oct 2010, 02:12
Expert's post
catennacio wrote:
Thank you very much Buneul for your answer. However I have a few questions:

I understand up to P(other sum). How can you conclude the winning scenario is other sum then sum 3? I know it's a possible case, but why is it (other sum, sum 3) will lead to a (other sum, sum 3, then sum 7). It could be (other sum, sum 3, sum 8) - after 3 rollings, while what we expect is sum 7. Therefore the (other sum, other sum,..., sum 3) could be a wrong case.

On the other hand, if we can conclude other sum, other sum,..., sum 3 is a winning scenario, have we assume the probability of sum 7 and other sum but not 7 are the same, while there are different?

I don't understand this sentence too "So probability of rolling a sum of 3 BEFORE rolling a sum of 7 would be the sum of the above infinite series" - how can you conclude it's the sum that series, how about if we have an AFTER word? What is the difference between BEFORE and AFTER?

Edit: I like your second approach, by comparing the fraction of the probability of 2 events we can say P = 1/4, but I still don't understand the word BEFORE.. What if they ask for AFTER? Will we still compare the 2 probabilities?

When we roll 2 dice the sum can be 3, 7, or some other number (not 3 and not 7). The questions asks for the cases when we get the sum of 3 BEFORE the sum of 7.

For example why the cases I wrote are the winning scenarios:
{sum=3} - means that right on the first throw we have sum of 3, so we have 3 before 7 (as no 7 at all);
{other sum; sum=3} - first roll not 7 and not 3, so we can continue. On the second throw we have sum of 3, so again 3 before 7 - OK;
{other sum; other sum; sum=3} - sum of 3 on the third roll;
{other sum; other sum; other sum; sum=3} - sum of 3 on the fourth roll;
....
{other sum; other sum; other sum; ..., other sum on the nth roll; sum of 3 on the (n+1)th roll} - out of n+1 rolls we have other sum for the rolls from 1 to n and sum of 3 on the (n+1)th roll, still 3 before 7 - OK;
...

The above can be continued infinitely, and all above case represent the scenario when we have the sum of 3 BEFORE we have the sum of 7 (which will eventually occur on some roll afterwards). So the probability of getting 3 before 7 would be the sum of the probabilities of the above events.

Hope it's clear. Anyway: you won't need this for GMAT, so don't worry too much.
_________________
Intern
Joined: 15 Apr 2010
Posts: 48
Followers: 0

Kudos [?]: 24 [0], given: 11

Re: Hard probability problem: 2 dice sum of 3 BEFORE sum of 7 [#permalink]  07 Oct 2010, 03:28
Thanks Bunuel now I understand it. However I think you miss the scenario where sum=7 occurs before sum=3. For example, 1st time sum=7, 2nd time sum=3, so the probability must be 6/36 * 2/36. You assumed that sum 7 never happens before sum 3 so you take the probability of other sum (7/9) to calculate. Am I wrong?
Math Expert
Joined: 02 Sep 2009
Posts: 31288
Followers: 5352

Kudos [?]: 62275 [0], given: 9445

Re: Hard probability problem: 2 dice sum of 3 BEFORE sum of 7 [#permalink]  07 Oct 2010, 04:38
Expert's post
catennacio wrote:
Thanks Bunuel now I understand it. However I think you miss the scenario where sum=7 occurs before sum=3. For example, 1st time sum=7, 2nd time sum=3, so the probability must be 6/36 * 2/36. You assumed that sum 7 never happens before sum 3 so you take the probability of other sum (7/9) to calculate. Am I wrong?

Yes, you are wrong. I'm not assuming that 7 doesn't occur before 3 rather than I'm only interested to count the probability of the cases when 3 occur before 7 as this is what the question is asking, that's why I'm not considering the cases when 7 occur before 3.
_________________
Manager
Joined: 27 May 2008
Posts: 126
Followers: 2

Kudos [?]: 59 [0], given: 4

Re: Hard probability problem: 2 dice sum of 3 BEFORE sum of 7 [#permalink]  07 Oct 2010, 22:40
Nice explanation Bunuel !
Intern
Joined: 15 Apr 2010
Posts: 48
Followers: 0

Kudos [?]: 24 [0], given: 11

Re: Hard probability problem: 2 dice sum of 3 BEFORE sum of 7 [#permalink]  08 Oct 2010, 18:11
Thanks Bunuel, you're right.. sometimes I got off the track when thinking... thanks for being patient with me
Re: Hard probability problem: 2 dice sum of 3 BEFORE sum of 7   [#permalink] 08 Oct 2010, 18:11
Similar topics Replies Last post
Similar
Topics:
6 Given two fair dice, what is the probability that the sum of their no. 5 10 Sep 2015, 03:39
4 What is the probability that the sum of two dice will yield a 7, and 9 02 Jul 2015, 01:25
2 If the sum of the last 3 integers in a set of 7 consecutive 4 20 Sep 2013, 15:29
8 A and B in turns, throw a dice. If A gets a sum of 8 before 3 08 Aug 2013, 06:27
1 What is the probability that the sum of two dice will yield 2 08 Feb 2012, 13:50
Display posts from previous: Sort by


text:
# The SPECTRA Procedure

### Transforming Frequencies

The variable FREQ in the data set created by the SPECTRA procedure ranges from 0 to . Sometimes it is preferable to express frequencies in cycles per observation period, which is equal to FREQ.

To express frequencies in cycles per unit time (for example, in cycles per year), multiply FREQ by , where d is the number of observations per unit of time. For example, for monthly data, if the desired time unit is years then d is 12. The period of the cycle is , which ranges from to infinity.


text:
# Proportionally Fair Clustering

9 May 2019

We extend the fair machine learning literature by considering the problem of proportional centroid clustering in a metric context. For clustering $n$ points with $k$ centers, we define fairness as proportionality to mean that any $n/k$ points are entitled to form their own cluster if there is another center that is closer in distance for all $n/k$ points... (read more)

PDF Abstract

# Code Add Remove Mark official

No code implementations yet. Submit your code now


text:
Documentation last updated on 1 August 2018 by Brian Coventry (bcov@uw.edu).

Back to Filters page.

## InterfaceHydrophobicResidueContacts

Filters structures based on the number of hydrophobic residues on the target that have at least a certain hydrophobic ddG.

<InterfaceHydrophobicResidueContacts name="(&string)" target_selector="(&string)" binder_selector="(&string)" scorefxn="(&string)" threshold="(5 &int)" score_cut="(-0.5 &Real)" apolar_res="(ALA,CYS,CYD,PHE,ILE,LEU,MET,PRO,THR,VAL,TRP,TYR &string)" />
• target_selector: Required. Which residues should be counted as hydrophobic target residues?
• binder_selector: Required. Which residues are part of the binder so that the interface can be defined?
• scorefxn: Required. Which scorefunction do you want to use? Only fa_rep, fa_sol, and fa_atr will be kept. (Soft score functions like ref2015_soft often work well too)
• threshold: How many hydrophobic residues should have at least the score cutoff?
• score_cut: What score cut should be used to determine whether a hydrophobic residue is contacted? (A note here. This is the energy from the pose.energies() object; therefore the actual ddG of the residue may be twice as big as what is typed here because pose.energies() only contains half of the interaction energy.)
• apolar_res: What residues should count as hydrophobic residues (comma separated name3 list)?

This mover looks for designs that make the most use of the target, with the hypothesis being that binders that use more of the hydrophobic residues on the target are better binders. Be careful with your target selector though! If you select extraneous hydrophobic residues, designs with the highest InterfaceHydrophobicResidueContacts will all contact those residues!


text:
Thank you for visiting nature.com. You are using a browser version with limited support for CSS. To obtain the best experience, we recommend you use a more up to date browser (or turn off compatibility mode in Internet Explorer). In the meantime, to ensure continued support, we are displaying the site without styles and JavaScript.

# Early-stage evaluation of catalyst manufacturing cost and environmental impact using CatCost

## Abstract

The costs and environmental impacts of catalyst manufacture are often neglected during early-stage research because of a lack of accessible, standardized tools to assess them. Here we report the key features of CatCost, a free and public estimation tool for the evaluation of catalyst cost. We demonstrate its functionality with a case study of diverse catalysts (ZSM-5, Pt/TiO2 and Mo2C) for the catalytic fast pyrolysis of biomass. We quantified the economic and environmental improvements made by replacing circulating-bed ZSM-5 with more stable, fixed-bed Pt/TiO2 and Mo2C catalysts, while revealing the effects of synthesis methods and production scale on catalyst costs. The manufacture of ZSM-5 had a large processing cost contribution that was strongly scale dependent, whereas the costs of the other catalysts were dominated by raw materials at all scales. Furthermore, while ZSM-5 costs the least per kilogram, the more stable catalysts cost half as much per gallon of fuel.

This is a preview of subscription content, access via your institution

$32.00 All prices are NET prices. ## Data availability The latest version of CatCost, including the downloadable spreadsheet in Microsoft Excel format, the web-based app. and the user guide, is available at https://catcost.chemcatbio.org. Completed, editable CatCost spreadsheets for the catalysts featured in this article have been included as Supplementary data files and are also shown as Supplementary Figs. 1324. The data used to compile specific figures in this article, if not already found in the Supplementary Information, can be obtained from the authors upon reasonable request. ## References 1. Technology Roadmap: Energy and GHG Reductions in the Chemical Industry via Catalytic Processes (International Energy Agency, 2013). 2. Bligaard, T. et al. Toward benchmarking in catalysis science: best practices, challenges, and opportunities. ACS Catal. 6, 2590–2602 (2016). 3. Scott, S. L. A matter of life(time) and death. ACS Catal. 8, 8597–8599 (2018). 4. Murzin, D. Engineering Catalysis (De Gruyter, 2013). 5. Armor, J. N. Do you really have a better catalyst? Appl. Catal. A Gen. 282, 1–4 (2005). 6. Mitchell, S., Michels, N.-L. & Perez-Ramirez, J. From powder to technical body: the undervalued science of catalyst scale up. Chem. Soc. Rev. 42, 6094–6112 (2013). 7. Boren, M., Chan, V. & Musso, C. The Path to Improved Returns in Materials Commercialization (McKinsey & Co., 2012). 8. Schaidle, J. A. et al. in Catalysis Vol. 29 (eds Spivey, J. & Han, Y.-F.) 213–281 (Royal Society of Chemistry, 2017). 9. Dutta, A. et al. Process Design and Economics for the Conversion of Lignocellulosic Biomass to Hydrocarbon Fuels: Thermochemical Research Pathways with In Situ and Ex Situ Upgrading of Fast Pyrolysis Vapors. Report no. NREL/TP-5100-62455 (National Renewable Energy Laboratory, 2015). 10. Dutta, A., Schaidle, J. A., Humbird, D., Baddour, F. G. & Sahir, A. Conceptual process design and techno-economic assessment of ex situ catalytic fast pyrolysis of biomass: a fixed bed reactor implementation scenario for future feasibility. Top. Catal. 59, 2–18 (2016). 11. Dutta, A. et al. Ex Situ Catalytic Fast Pyrolysis of Lignocellulosic Biomass to Hydrocarbon Fuels: 2018 State of Technology and Future Research. Report no. NREL/TP-5100-71954 (National Renewable Energy Laboratory, 2018). 12. Dutta, A. et al. Ex Situ Catalytic Fast Pyrolysis of Lignocellulosic Biomass to Hydrocarbon Fuels: 2019 State of Technology and Future Research. Report no. NREL/TP-5100-76269 (National Renewable Energy Laboratory, 2020). 13. Dutta, A. et al. Ex Situ Catalytic Fast Pyrolysis of Lignocellulosic Biomass to Hydrocarbon Fuels: 2020 State of Technology. Report no. NREL/TP-5100-80291 (National Renewable Energy Laboratory, 2021). 14. Tan, E. C. D. et al. Conceptual process design and economics for the production of high-octane gasoline blendstock via indirect liquefaction of biomass through methanol/dimethyl ether intermediates. Biofuel. Bioprod. Biorefin. 10, 17–35 (2016). 15. Snowden-Swan, L. J., Spies, K. A., Lee, G. J. & Zhu, Y. Life cycle greenhouse gas emissions analysis of catalysts for hydrotreating of fast pyrolysis bio-oil. Biomass Bioenergy 86, 136–145 (2016). 16. Kazi, F. K., Patel, A. D., Serrano-Ruiz, J. C., Dumesic, J. A. & Anex, R. P. Techno-economic analysis of dimethylfuran (DMF) and hydroxymethylfurfural (HMF) production from pure fructose in catalytic processes. Chem. Eng. J. 169, 329–338 (2011). 17. Dutta, A. et al. Process Design and Economics for Conversion of Lignocellulosic Biomass to Ethanol: Thermochemical Pathway by Indirect Gasification and Mixed Alcohol Synthesis. Report no. NREL/TP-5100-51400 (National Renewable Energy Laboratory, 2011). 18. Tan, E. C. D. et al. Process Design and Economics for the Conversion of Lignocellulosic Biomass to Hydrocarbons via Indirect Liquefaction: Thermochemical Research Pathway to High-Octane Gasoline Blendstock Through Methanol/Dimethyl Ether Intermediates. Report no. NREL/TP-5100-62402 (National Renewable Energy Laboratory, 2015). 19. Anderson, J. Determining Manufacturing Costs. Chem. Eng. Prog. 27–31 (2009). 20. Anderson, J. Communicating the Cost of Product and Process Development. Chem. Eng. Prog. 46–51 (2010). 21. Anderson, J. & Fennell, A. Calculate Financial Indicators to Guide Investments. Chem. Eng. Prog. 34–40 (2013). 22. Peters, M. S. & Timmerhaus, K. D. Plant Design and Economics for Chemical Engineers 5th edn (McGraw-Hill, 2003). 23. Ulrich, G. D. & Vasudevan, P. T. Chemical Engineering Process Design and Economics 2nd edn (Process, 2004). 24. Towler, G. & Sinnott, R. K. Chemical Engineering Design – Principles, Practice, and Economics of Plant and Process Design 2nd edn (Butterworth-Heinemann, 2013). 25. Green, D. W. & Perry, R. H. Perry’s Chemical Engineer’s Handbook 8th edn (McGraw-Hill, 2008). 26. Garrett, D. E. Chemical Engineering Economics (Van Nostrand-Reinhold, 1989). 27. Vajglová, Z. et al. Synthesis and physicochemical characterization of shaped catalysts of β and Y zeolites for cyclization of citronellal. Ind. Eng. Chem. Res. 58, 18084–18096 (2019). 28. Devyatkov, S., Kuzichkin, N. V. & Murzin, D. Y. On comprehensive understanding of catalyst shaping by extrusion. Chim. Oggi 33, 57–64 (2015). 29. Stiles, A. B. Catalyst Manufacture (Marcel Dekker, 1983). 30. Bankmann, M., Brand, R., Engler, B. H. & Ohmer, J. Forming of high surface area TiO2 to catalyst supports. Catal. Today 14, 225–242 (1992). 31. Tufvesson, P. R., Lima-Ramos, J., Nordblad, M. & Woodley, J. M. Guidelines and cost analysis for catalyst production in biocatalytic processes. Org. Process Res. Dev. 15, 266–274 (2011). 32. Menten, F., Chèze, B., Patouillard, L. & Bouvart, F. A review of LCA greenhouse gas emissions results for advanced biofuels: the use of meta-regression analysis. Renew. Sustain. Energy Rev. 26, 108–134 (2013). 33. Greig, A. L. & Carey, S. International Molybdenum Association (IMOA) life cycle assessment program and perspectives on the LCA harmonization effort. Int. J. Life Cycle Assess. 21, 1554–1558 (2015). 34. Sick, V. et al. The need for and path to harmonized life cycle assessment and techno‐economic assessment for carbon dioxide capture and utilization. Energy Technol. https://onlinelibrary.wiley.com/doi/abs/10.1002/ente.201901034 (2019). 35. Trippe, F., Fröhling, M., Schultmann, F., Stahl, R. & Henrich, E. Techno-economic analysis of fast pyrolysis as a process step within biomass-to-liquid fuel production. Waste Biomass Valoriz. 1, 415–430 (2010). 36. Hu, W., Dang, Q., Rover, M., Brown, R. C. & Wright, M. M. Comparative techno-economic analysis of advanced biofuels, biochemicals, and hydrocarbon chemicals via the fast pyrolysis platform. Biofuels 7, 57–67 (2015). 37. Meyer, P. A. et al. Field-to-fuel performance testing of lignocellulosic feedstocks for fast pyrolysis and upgrading: techno-economic analysis and greenhouse gas life cycle analysis. Energy Fuels 30, 9427–9439 (2016). 38. Talmadge, M. et al. Techno-economic analysis for co-processing fast pyrolysis liquid with vacuum gasoil in FCC units for second-generation biofuel production. Fuel 293, 119960 (2021). 39. CatCost v.1.1.0 (National Renewable Energy Laboratory, 2021); https://catcost.chemcatbio.org 40. Qi, W., Sathre, R., Morrow, W. R. & Shehabi, A. Unit Price Scaling Trends for Chemical Products. Report no. LBNL-189844 (Lawrence Berkeley National Laboratory, 2015). 41. Baddour, F. G., Snowden-Swan, L., Super, J. D. & Van Allsburg, K. M. Estimating precommercial heterogeneous catalyst price: a simple step-based method. Org. Process Res. Dev. 22, 1599–1605 (2018). 42. World Catalysts (Freedonia Group, 2014). 43. Guthrie, K. M. Data and Techniques for Preliminary Capital Cost Estimation. Chem. Eng. (New York) 114–142 (1969). 44. Guthrie, K. M. Process Plant Estimating, Evaluation, and Control (Craftsman, 1974). 45. Cran, J. Improved factored method gives better preliminary cost estimates. Chem. Eng. (New York) 65–79 (1981). 46. Desai, M. B. Preliminary cost estimating of process plants. Chem. Eng. (New York) 65–70 (1981). 47. Brown, T. R. Estimating Product Costs. Chem. Eng. (New York) 86–89 (2000). 48. Ward, T. J. Economic Evaluation. In Kirk-Othmer Encyclopedia of Chemical Technology (online) (Wiley, 2001). https://onlinelibrary.wiley.com/doi/book/10.1002/0471238961 49. Seider, W. D. et al. Product and Process Design Principles: Synthesis, Analysis and Evaluation 4th edn (Wiley, 2016). 50. Super, J. D. The precious metal loop, costs from an operating company perspective. Top. Catal. 53, 1138–1141 (2010). 51. Feng, Y. & Rangaiah, G. P. Evaluating Capital Cost Estimation Programs. Chem. Eng. (New York) 22–29 (2011). 52. Griffin, M. B. et al. Driving towards cost-competitive biofuels through catalytic fast pyrolysis by rethinking catalyst selection and reactor configuration. Energy Environ. Sci. 11, 2904–2918 (2018). 53. Ruddy, D. A. et al. Recent advances in heterogeneous catalysts for bio-oil upgrading via “ex situ catalytic fast pyrolysis”: catalyst development through the study of model compounds. Green Chem. 16, 454–490 (2014). 54. Liu, C., Wang, H., Karim, A. M., Sun, J. & Wang, Y. Catalytic fast pyrolysis of lignocellulosic biomass. Chem. Soc. Rev. 43, 7594–7623 (2014). 55. Iisa, K., French, R. J., Orton, K. A., Dutta, A. & Schaidle, J. A. Production of low-oxygen bio-oil via ex situ catalytic fast pyrolysis and hydrotreating. Fuel 207, 413–422 (2017). 56. Zacher, A. H. et al. Technology advancements in hydroprocessing of bio-oils. Biomass Bioenergy 125, 151–168 (2019). 57. Iida, T. et al. Encapsulation of molybdenum carbide nanoclusters inside zeolite micropores enables synergistic bifunctional catalysis for anisole hydrodeoxygenation. ACS Catal. 7, 8147–8151 (2017). 58. Chen, C.-J. & Bhan, A. Mo2C modification by CO2, H2O, and O2: effects of oxygen content and oxygen osurce on rates and selectivity of m-cresol hydrodeoxygenation. ACS Catal. 7, 1113–1122 (2017). 59. Pgm Market Report (Johnson Matthey PLC, 2019). 60. Vaughan, D. E. W. in Fluid Catalytic Cracking: Science and Technology (eds Magee, J. S. & Mitchell, M. M.) 83–104 (Elsevier, 1993). 61. Schmidt, M. The Sankey diagram in energy and material flow management. J. Ind. Ecol. 12, 82–94 (2008). 62. Bare, J. C., Norris, G. A., Pennington, D. W. & McKone, T. TRACI: the tool for the reduction and assessment of chemical and other environmental impacts. J. Ind. Ecol. 6, 49–78 (2003). 63. Bare, J. TRACI 2.0: the tool for the reduction and assessment of chemical and other environmental impacts 2.0. Clean Technol. Environ. Policy 13, 687–696 (2011). 64. TRACI v.2.1 (Environmental Protection Agency, 2012); https://www.epa.gov/chemical-research/tool-reduction-and-assessment-chemicals-and-other-environmental-impacts-traci 65. Celik, I., Mason, B. E., Phillips, A. B., Heben, M. J. & Apul, D. Environmental impacts from photovoltaic solar cells made with single walled carbon nanotubes. Environ. Sci. Technol. 51, 4722–4732 (2017). 66. Ambrose, H. & Kendall, A. Understanding the future of lithium: part 2, temporally and spatially resolved life‐cycle assessment modeling. J. Ind. Ecol. 24, 90–100 (2019). 67. Ryberg, M., Vieira, M. D. M., Zgola, M., Bare, J. & Rosenbaum, R. K. Updated US and Canadian normalization factors for TRACI 2.1. Clean Technol. Environ. Policy 16, 329–339 (2013). 68. Saaty, T. L. How to make a decision: the analytic hierarchy process. Eur. J. Oper. Res. 48, 9–26 (1990). 69. Schreier, M. & Regalbuto, J. R. A fundamental study of Pt tetraammine impregnation of silica 1. The electrostatic nature of platinum adsorption. J. Catal. 225, 190–202 (2004). 70. Miller, J. T., Schreier, M., Kropf, A. J. & Regalbuto, J. R. A fundamental study of platinum tetraammine impregnation of silica 2. The effect of method of preparation, loading, and calcination temperature on (reduced) particle size. J. Catal. 225, 203–212 (2004). 71. Aspen Plus (Aspen Technology, Inc., 2017). 72. Lang, H. J. Cost Relationships in Preliminary Cost Estimation. Chem. Eng. (New York) 117–121 (1947). 73. Lang, H. J. Simplified Approach to Preliminary Cost Estimates. Chem. Eng. (New York) 112–113 (1948). 74. SimaPro v.8.5.2.0 (Product Ecology Consultants, 2016). 75. State-level Average Annual Gasoline Expenditures per Capita Ranged from$400 to \$1,400 (U.S. Energy Information Administration, 2021); https://www.eia.gov/todayinenergy/detail.php?id=40893

76. Paasikallio, V. et al. Product quality and catalyst deactivation in a four day catalytic fast pyrolysis production run. Green Chem. 16, 3549–3559 (2014).

## Acknowledgements

We thank J. Hensley, S. Habas, D. Ruddy, A. Dutta, M. Talmadge and L. Snowden-Swan for their contributions to the early conceptual development of CatCost. For the final figure comparing catalyst alternatives, we thank A. Dutta, K. Iisa and C. Mukarakate for helpful discussions. We thank M. Griffin for discussion of SEA methods. We thank the team that developed the web-based app. version of CatCost from the spreadsheet version, including N. Wunder, K. Potter, J. Yarbrough, K. Gruchalla, M. Jankousky and A. Young. We thank T. Sandberg of the NREL Library and E. Livingston of Scopus for their assistance in performing the catalyst cost literature frequency survey. We thank A. Bhatt for his contributions to the Pt/TiO2 synthesis process model. This work was authored in part by NREL, operated by the Alliance for Sustainable Energy, LLC for the US Department of Energy (DOE) under contract no. DE-AC36–08GO28308, in collaboration with the Chemical Catalysis for Bioenergy Consortium, a member of the Energy Materials Network. Funding was provided by the US DOE Office of Energy Efficiency and Renewable Energy Bioenergy Technologies Office. The views expressed in this article do not necessarily represent the views of the DOE or the US Government. The US Government retains and the publisher, by accepting the article for publication, acknowledges that the US Government retains a non-exclusive, paid-up, irrevocable, worldwide licence to publish or reproduce the published form of this work, or allow others to do so, for US Government purposes.

## Author information

Authors

### Contributions

F.G.B. and J.A.S. formulated the CatCost concept and won funding. K.M.V. developed cost estimation methods and built the spreadsheet version of CatCost, as well as portions of the web-based app. K.M.V. and F.G.B. managed the development of the web-based app. version of CatCost. E.C.D.T. and J.D.S. developed the process models that translate laboratory-scale syntheses into industrial production costs. K.M.V. performed cost analysis. E.C.D.T. developed life cycle assessment. K.M.V., E.C.D.T., J.A.S. and F.G.B. wrote the manuscript.

## Ethics declarations

### Competing interests

The authors declare no competing interests.

## Peer review

### Peer review information

Nature Catalysis thanks Marianthi Ierapetritou, Aimaro Sanna and the other, anonymous, reviewer(s) for their contribution to the peer review of this work.

Publisher’s note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

## Supplementary information

### Supplementary Information

Supplementary Figs. 1–24, Tables 1–13, Notes 1–3 and Discussion.

### Supplementary Data 1

CatCost estimate: ZSM-5.

### Supplementary Data 2

CatCost estimate: 2% Pt/TiO2.

### Supplementary Data 3

CatCost estimate: 0.5% Pt/TiO2.

### Supplementary Data 4

CatCost estimate: Mo2C.

## Rights and permissions

Reprints and Permissions

Van Allsburg, K.M., Tan, E.C.D., Super, J.D. et al. Early-stage evaluation of catalyst manufacturing cost and environmental impact using CatCost. Nat Catal 5, 342–353 (2022). https://doi.org/10.1038/s41929-022-00759-6

• Accepted:

• Published:

• Issue Date:

• DOI: https://doi.org/10.1038/s41929-022-00759-6