text:
# Announcing the vls utility.

One of the joys of modern programming is the ability to utilize external code libraries to speed up development, saving time, and reducing wasted effort. The Ruby language is especially blessed in this regard with its system of code gems. Instead of the narrow minded NIH (not invented here) mindset, the world has become our tool chest.

There is, however, a downside to this modular nirvana. Versioning! To be precise: Am I using the correct version of each (and every) little code gem? This problem goes back all the way to the old Visual Basic days. Back then it was called DLL Hell, as developers struggled to maintain a myriad of cryptic, often poorly documented binary files.

Now Ruby does have the bundler utility that allows gem versions to be specified, but what if you simply want to know: When I use this application, what modules/classes are being used?

The vls utility answers that question. To use this simply enter:

`\$ vls <names>`

where names are a list of gems/files to be required before the modules are listed. Here, see an example of this in action:

```\$ vls fOOrth
vls (VersionLS): 0.1.0

Bignum, 0.0.5
Complex, 0.0.5
Date::Infinity, 0.0.5
FalseClass, 0.0.5
Fixnum, 0.0.5
Float, 0.0.5
FormatEngine, 0.7.2
FullClone, 0.0.5
Gem, 2.2.2
InArray, 0.1.5
Integer, 0.0.5
NilClass, 0.0.5
Numeric, 0.0.5
Rational, 0.0.5
Regexp, 0.0.5
RubySscanf, 0.2.1
SafeClone, 0.0.3
Symbol, 0.0.5
TrueClass, 0.0.5
XfOOrth, 0.6.1```

The vls gem may be found at: https://rubygems.org/gems/vls and the source code lives at: https://github.com/PeterCamilleri/vls.

Yours Truly

Peter Camilleri (aka Squidly Jones)

# The Durham Makerspace

I’ve written about meetup groups in the blog space before and I continue to enjoy them as a social and educational outlet. Yesterday, I attended my first East-End Tech Meetup. I must say that having a group closer to home is a lot nicer than a 3 hour round trip into downtown Toronto. The real excitement, for me however, was the topic. Here it is from the meetup description:

A remarkable young member of our community is planning to launch a GTA-class Makerspace right here in Oshawa. He wants to present his ideas to our community, elicit feedback, generate more ideas & strategies, as well as gather the much needed support from our citizens here in the Durham Region. This is no small undertaking and it will take the effort of many to back his execution.

This would be a substantial asset to Oshawa and its people so spread the word. Tell your friends & neighbors. Every bit of support is needed to make (pun) this a reality.

Now, I’ve visited maker labs before. They were all far away, very expensive, and difficult to join, especially for an older person such as myself. Let’s just say that I did not feel welcome.

This group is different. I suppose it is at least partly the thrill of getting in on the ground floor, but there was an energy present that I had not seen or felt before. There was also an open exchange of ideas and many diverse contributions were being sought after. My impressions were very positive.

The effort is still in its infancy, but they have a facebook page. Take a look and hopefully find a resource to express your creativity through engineering and making.

Yours Truly

Peter Camilleri (aka Squidly Jones)

# The Clone’s Family Tree

The Ruby programming language has two methods for duplicating data. These are “dup” and “clone”. While these methods are quite useful, they both suffer from two shortcomings:

1. In Ruby, if an attempt is made to clone (or dup) an immutable data item like a number, an error occurs. The justification for this uncharacteristic strictness is not at all clear, but it does mean that the clone (or dup) operation must be applied with great care.
2. The copying process used by both clone and dup is said to be a shallow (or incomplete) copy. While the target data structure is copied, any internal data structures are not. References to those data remain aliased in the copy.

I started off to create a gem to resolve these issues. I ended up creating a family of  four gems that are tailored to the exacting data copying requirements of the application. Here is a summary of those gems:

 Depth / Action Need to copy all data and metadata attributes? Need to copy data only? Only need a shallow copy? Use the safe_clone gem. Use the safe_dup gem. Need a full, recursive copy? Use the full_clone gem. Use the full_dup gem.

Notes:

• Since none of these gems override the default clone and dup methods, the default behaviors remain available. Further, if multiple, differing requirements exists, more than one family member gem may be employed in the same project without fear of conflict.
• If multiple family gems are employed, they will each need to be installed and required into the application. See each gem’s github source for details.
• Meta-data attributes include the frozen status and singleton methods. However the tainted status is always copied.

I hope you find these little gems as useful as I have found them to be. I you like them, give the code repository a star as a sign of approval!

Yours Truly

Peter Camilleri (aka Squidly Jones)

# Hidden Traps: String Mutations

In the world of Sci-Fi movies and video games, mutants are not always a bad thing. In fact, sometimes, the mutants are the hero or the key to the hero’s success. On the other hand, no matter how good their intentions, trouble always seems to follow them.

In the world of programming, data can be mutated as well and it attracts trouble there too. Data is mutated when its internal state is modified. The alternative is data that is immutable. This means that the internal value cannot be modified, it can only be replaced with a new value.

Let’s see an example of immutable data in action first:

a=42
b=a
a+= 4
puts a   #Displays 46
puts b   #Displays 42

This is the safe, sane case. Changes to the variable a do not affect the variable b. Now, in Ruby, strings are mutable. Let’s see how this plays out.

a=”hello”
b=a
a << ” world”
puts a    #Displays: hello world
puts b    #Also displays: hello world

In this case, the string data in a and b was mutated. The change to a was expected. The change to the seemingly unrelated variable b could be a nasty surprise and a source of bugs. I can say that this very issue is without doubt the number one source of trouble in my own code.

The sensible question to ask is: Why are string mutated at all? Why not always protect the programmer from this issue? The answer is performance. Creating new instance of strings all the time is wasteful of resources and places a heavy load on the memory management system. Let’s see how this issue is handled by two leading languages: C# and Ruby.

## C#

In C#, the mutation of strings issue is handled by giving the programmer choice. The default, goto class for strings, namely the String class, is fully safe and immutable. Thus for simple programming tasks and less experienced programmers, the obvious choice also is the easiest to get right. Maybe not super-fast, but the expected results.

When (and where) performance issues do arise, the StringBuffer class exists that can be more efficient because is allows data mutation. In fact, it embraces it with special mutating methods, not part of the String class. Since a conscious choice must be made to allow and use mutation, hopefully, the programmer will focus there attention on those areas, thus avoiding nasty surprises.

## Ruby

In contrast, Ruby (currently) allows string mutation by default. This means that any string at any time could be mutated. This causes a lot of problems. There are some possible answers:

• When assigning a string, clone it. A statement like: a = b.clone breaks the connection between a and b by making a full copy of the string. It works, but this can be slow.
• When creating a string, freeze it. This looks like: b = “Hello”.freeze and now any mutation will raise an error that reveals the bug at the point it first occurs. This is not slow, but requires thorough testing to avoid exceptions in the field. You also need to remember to use the freeze in the first place.
• In upcoming versions of Ruby (version 3 I believe), strings will be frozen by default. You will now need special syntax to create mutable strings. This will look (probably) something like b = String.new(“Hello”). This suffers from the fact that it is likely to break a lot of older code.

These two languages show two divergent approaches to the issue of string mutation. Now I really like Ruby, and C# is a pretty decent language too. On this issue though, C# looks like the clear winner here. Safe by default, gentle on programmers, efficient where needed, and above all, not breaking older code. To me it’s a slam-dunk!

What are your thoughts? Does another language do an even better job? I’d love to hear from you, so chime in with a comment, idea, or objection!

Yours Truly

Peter Camilleri (aka Squidly Jones)

# Article Update: April 15, 2016

I am pleased to announce the release of the fOOrth 0.6.0 language system. The major change in this version is to split the String class into an immutable String class and a mutable StringBuffer class. Even though fOOrth is based on Ruby, the underlying architecture is more than flexible enough to accommodate this change.

# fOOrth

It is with great pleasure that I am finally able to announce the release the initial beta of the fOOrth programming language system version 0.5.0. This language, written entirely in pure Ruby is released both as a Ruby gem and in Source Code on github.

So, what exactly is the fOOrth programming language system anyway? The source code repository has this to say about the project:

The fOOrth language is an experimental variant of FORTH that attempts to incorporate object oriented and functional programming concepts. It also tries to extrapolate an alternate reality where FORTH was not frozen in the past, but continued to grow and develop with the times. Above all this project is the result of nearly 30 years of thought on the design of threaded compilers and languages with simplified grammars and syntax.

Also included in the docs folder are a User’s Guide and Reference in both open office and PDF formats.

A lot of work and effort has gone into this personal labour of love. For example, I have discovered that writing good documentation is a lot harder than it looks. It is certainly harder than just writing code. I have also found however that having to explain what is going on in plain, simple, and easy-to-understand terms has resulted in many improvements to the code that would not have happened otherwise. In effect, it served as a sober, detailed review of the code being generated.

This is still only a beta, and there is still a great deal more work to do. I hope you find it useful or at least interesting. If you like what you see, give the code a star to show your support. Suggestions, comments, complaints and ideas are always most welcomed.

Yours Truly

Peter Camilleri (aka Squidly Jones)

# The redesigned minitest_visible gem (v0.1.0)

Just because code works, doesn’t mean it’s the correct code. A case in point is my own minitest_visible gem. This little bit of Ruby code adds simple progress tracking to the testing process. In any programming, and especially in a  dynamic language like Ruby, testing is vital. So is having faith in those tests.

Now the standard minitest testing system is awesome! It is full of helpful methods for confirming the correctness of code. It is however a little terse regarding progress. That is where minitest_visible comes in. When used, it lets you know the version of minitest being used and prints out the name of each test file as it is processed.

A fairly simple task. Yet, when I came up with the first version of this code, it was clunky and ugly, but it worked. I suppose I had other matters pressing at the time, but I let things stand at “good enough”

Recently, I began to think that there must be a way to make the code better, cleaner, and easier to use. It seems that I have indeed learned some stuff in the last year because I am now writing about a new version that is far simpler and streamlined.

OK, let’s be clear: The old way of doing things is still supported, but prints out a message about the needed changes. Test still pass though so disruption and panic should be minimal.

The new minitest_visible can be found https://rubygems.org/gems/minitest_visible and the source code is at https://github.com/PeterCamilleri/minitest_visible.

Yours Truly

Peter Camilleri (aka Squidly Jones)

# A Double Bill!

Having just announced format_engine version 0.4.0, things seem to be speeding along as I now announce format_engine version 0.5.1 and ruby_sscanf version 0.1.1.

These two gems are rather tightly coupled. The ruby_sscanf gem uses the capabilities of the format_engine to create a Ruby translation of the POSIX ‘C’ sscanf routine. This allows a formatted string to be processed into the data elements contained within. The new version of the format_engine is required to add some features required by the ruby_sscanf gem.

I thought a great deal about the idea of merging the ruby_sscanf gem into the format_engine, but in the end, concluded that they did different things despite the high degree of coupling. Further, ruby_sscanf modifies (or monkey patches) the base String class, and that was something that might not always be desired. So two separate gems.

These may be found at:

I hope all Ruby programmers find these programming tools to be useful.

Yours Truly

Peter Camilleri (aka Squidly Jones)

# Format Engine Version 0.4.0

I am pleased to announce the new version of the format_engine gem. This blog has been highly remiss in keeping up with the releases of new code. So, we are skipping ahead from version 0.0.2 to 0.4.0. After a hiatus of six months, the new version has improvements, mostly to the parser side of the engine.

1. Parsed spaces may match zero or more input spaces so that it is no longer necessary to predict the exact number of spaces between data elements.
2. The parser now supports strings with regular expression sub-sets like %[abc] which matches the input in the set “a”, “b”, and “c”. Also supported is exclusion sub-sets like %[^abc] which matches the input not in the set “a”, “b”, and “c”.
3. Improved documentation in the README.md file.

The gem may be found at Ruby Gems and the source code at GitHub.

Yours Truly

Peter Camilleri (aka Squidly Jones)

# Hidden Traps: Floating Point Math.

As a life long programmer, I’ve programmed a lot of calculations over the years. Yet, I was recently astounded to hear expressed the opinion that “Computer computations are error free and flawless”. The reasons that this is not (and never will be) the case are fairly deep and fundamental.

Mathematics routinely deals with matters of the infinite like the infinite digits in the value of the famous irrational number π (called pi). Engineers and computers on the others hand live in a world of the finite: finite memory, finite processing power, and finite time. The IEEE standards for computer arithmetic are marvels of ingenuity. They are also a compromise between the needs of speed, storage, and accuracy.

Let’s see a real example and test the associative property of addition. This crucial, fundamental rule of math says that:

$(a+b)+c = a+(b+c)$

Now lets try to program this. We’ll use Ruby for brevity, but the results would be the same for virtually any programming language that uses the computer’s floating point hardware.

a = 1.0e20
b = -1.0e20
c = 1.0

puts “(a+b)+c = #{(a+b)+c}”
puts “a+(b+c) = #{a+(b+c)}”

The output of this little snippet of code is:

(a+b)+c = 1.0
a+(b+c) = 0.0

The two results should be the same but they’re not. In one case, the use of a finite amount of memory to represent the numbers has caused an important “bit” of data to fall off the “end” and be lost. Addition in computers is not always associative.

Are there ways around this? Sure, you can improve things. In Ruby I can switch from Floats to Rational data, and this problem mostly goes away. The new program will consume more memory and take longer to run. Eventually, if the required precision becomes excessive, the program will slow to a crawl and/or run out of memory. Processing power and memory remain finite no matter how sophisticated the tools we use.

The moral: Know your math, yes, but realize that computers can’t do math, they can only approximate it! So know the limitations of your tools too.

Yours Truly

Peter Camilleri (aka Squidly Jones)

# Version 0.0.2 format_engine released.

In other news, a very minor bug fix for the format_engine gem (just recently released) is now available. This corrects an issue with the handling of invalid format strings. A very minor fix and most need not rush out a get the update. Still found on RubyGems and GitHub. The plus side is that as a minor bug fix, and now passing even more tests, this is a low risk upgrade.

As always, comments and suggestions are welcomed. If problems or questions are encountered, please raise an issue under the GitHub project. I do watch the issues very closely so will be sure to give any reports immediate attention.

Yours Truly

Peter Camilleri (aka Squidly Jones)


text:
# Tech Report CS-90-32

## When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks

### Abstract:

We give the first approximation algorithm for the {\em generalized network Steiner tree problem}, a problem in network design. An instance consists of a network with link-costs and, for each pair ${i,j}$ of nodes, an edge-connectivity requirement. The goal is to find a minimum-cost network using the available links and satisfying the requirements. Our algorithm outputs a solution whose cost is within $2 \log R$ of optimal, where $R$ is the highest requirement value.

In the course of proving the performance guarantee, we prove a combinatorial min-max approximate equality relating minimum-cost networks to maximum packings of certain kinds of cuts. As a consequence of the proof of this theorem, we obtain an approximation algorithm for optimally packing these cuts; we show that this algorithm has application to estimating the reliability of a probabilistic network.

(complete text in pdf or gzipped postscript)

format: plain


text:
# Pixel Binning Methods

## Introduction

This vignette is intended to explain the implications of different binning methods for doing color similarity analyses with the colordistance package.

colordistance comes with two binning functions: getImageHist() and getKMeanColors() (or getHistList() and getKMeansList() for multiple images at once), which categorize colors in a picture using two popular approaches for pixel clustering. Depending on the dataset, the method you choose can have a dramatic impact on your final results. The following explanations should hopefully clarify the differences, and which binning method is most appropriate for a certain dataset.

## Why binning?

Binning is a way of grouping continuous data into categories defined by specific ranges – shoe sizes are a good example of binning (there are certainly more unique foot dimensions than commercially available shoe sizes). In image processing, the first step in measuring color composition of an image is usually to bin all the pixels into a color histogram. This obviously comes at the cost of reducing the variation in the image, but it has a couple of major advantages for image comparisons:

1. It reduces and normalizes the amount of data we need to compare across images.

If instead of binning, we compared every pixel in an image to a pixel in another image, we would have three major computational problems:

• We would have to decide which pixels to compare to which other pixels;
• Even a simple paired comparison would require thousands or millions of calculations per pair of images;
• And the images almost certainly won’t have the same number of pixels.

By binning, we can compare apples to apples by comparing bins with the same boundaries from different images. And when we do that, we’re only comparing a finite number bins in one image to the exact same number of bins in another image, which is much quicker than trying to do it for every pixel, especially when much of the pixel-level variation isn’t important for the analysis.

2. It allows us to measure the amount of every color in the image.

For example, take the following picture of a Heliconius butterfly (Meyer (2006)):

We could very reasonably say that there are only 3 real colors on this butterfly: black, red, and yellow. But when we plot the individual pixels in the actual image…

# Note: any valid filepath will work; this line is specific to
# example data that comes with the package
Heliconius_08 <- system.file("extdata", "Heliconius/Heliconius_B/Heliconius_08.jpeg", package="colordistance")
colordistance::plotPixels(Heliconius_08, lower = rep(0.8, 3), upper = rep(1, 3))

As you might expect, although we can see black, red, and yellow pixels, they’re not all centered in a single place because of noise, lighting variation, and of course actual minor color differences in the animal itself when it was photographed. But if we define a certain range for black pixels in RGB color space, we can just count the proportion of pixels in that range:

binnedButterfly <- colordistance::getImageHist(Heliconius_08,
bins = 2,
lower = rep(0.8, 3),
upper = rep(1, 3),
plotting = TRUE)
## RGB and HSV are device-dependent, perceptually non-uniform color spaces. See 'Color spaces' vignette for more information.
##
## Using 2^3 = 8 total bins

And we can confidently say that 75% of the pixels in the butterfly were in the “black” range we defined. We’re treating all pixels in that bin as if they’re the same color, but in this case we can say that the simplification doesn’t sacrifice important information. It’s pretty accurate to say that the majority of the butterfly is black; that some of the pixels in the black regions are dark brown or dark grey is not meaningful biological variation for this image. Of course, there are situations where those more subtle color variations do matter, in which case you’d need smaller bins to break those pixels up into tighter ranges.

## Histogram method

Both the getImageHist() and getHistList() functions in colordistance use color histograms to bin the pixels in an image.

Each color channel – either red, green and blue (if using RGB) or hue, saturation, and value (if using HSV) – is divided into ranges of equal size. Each combination of ranges from the three channels forms a 3D “bin”. For example, if we chose to divide the blue channel into 2 bins, our ranges in the blue channel would be $$0 \leq B \leq 0.5$$ and $$0.5 < B \leq 1$$1.

If we did this for each channel, we’d have a total of $$2^{3}=8$$ bins. A pixel with RGB coordinates of [0.2, 0.8, 0.1] would be in the bin defined by RGB bounds of [0, 0.5], [0.5, 1], and [0, 0.5] – a pixel with the value [0.4, 0.6, 0.4] would be in that same bin. If we divided each channel into 3, the ranges for each one would be 0–0.33, 0.33–0.66 and 0.66–1, for a total of 27 bins, and so on.

The histogram functions take image or folder paths as arguments. The bins argument can be a vector of either length 1 or length 3. If it’s a single number, each channel is divided into that number of bins, so settings bins=2 results in 8 bins, bins=3 in 27, bins=4 in 64, etc. If you don’t want the same number of bins in each channel, pass a numeric vector of length 3 with the number of bins in each of the R, G, B or H, S, V channels you want, in that order.

par(mfrow=c(2,2))

# Generate histogram using all the default settings (3 bins per channel, get average pixel color in each bin, use RGB instead of HSV)
# See introduction vignette or documentation if lower/upper background pixel arguments are unclear
# Short version: getting rid of any pixels where R, G, and B values are ALL between 0.8 and 1 (aka white)
lower <- rep(0.8, 3)
upper <- rep(1, 3)
defaultHist <- colordistance::getImageHist(Heliconius_08, lower = lower, upper = upper, title = "3 bins per channel, RGB")
## RGB and HSV are device-dependent, perceptually non-uniform color spaces. See 'Color spaces' vignette for more information.
##
## Using 3^3 = 27 total bins
# We already did 8 bins above, so let's do 1 bin just for sarcasm
oneBin <- colordistance::getImageHist(Heliconius_08, lower = lower, upper = upper, bins = 1, title="1 bin (pointless but didactic?)")
## RGB and HSV are device-dependent, perceptually non-uniform color spaces. See 'Color spaces' vignette for more information.
##
## Using 1^3 = 1 total bins
# Use 2 red and green bins, but only 1 blue bin
unevenBins <- colordistance::getImageHist(Heliconius_08, lower = lower, upper = upper, bins = c(2, 2, 1), title = "Non-uniform channel divisions")
## RGB and HSV are device-dependent, perceptually non-uniform color spaces. See 'Color spaces' vignette for more information.
##
## Using 2*2*1 = 4 bins
# HSV instead of RGB
hsvBins <- colordistance::getImageHist(Heliconius_08, lower = lower, upper = upper, hsv = TRUE, title = "HSV, not RGB")
## RGB and HSV are device-dependent, perceptually non-uniform color spaces. See 'Color spaces' vignette for more information.
##
## Using 3^3 = 27 total bins

In addition to plotting the histogram, the function also returns a dataframe of bin centers and sizes:

defaultHist[1:10, ]
##            r          g          b          Pct
## 1  0.1648303 0.09910732 0.03283184 6.728324e-01
## 2  0.5099977 0.23079050 0.07248014 1.778252e-01
## 3  0.7385743 0.29286938 0.07945645 4.367000e-02
## 4  0.3179272 0.34145658 0.22464986 1.539612e-04
## 5  0.5219391 0.41945242 0.19715851 2.747108e-02
## 6  0.7486583 0.36986414 0.13583021 1.468130e-02
## 7  0.1666667 0.83333333 0.16666667 0.000000e+00
## 8  0.6666667 0.67450980 0.24705882 3.299169e-05
## 9  0.7282275 0.73445933 0.30199961 2.221440e-03
## 10 0.1666667 0.16666667 0.50000000 0.000000e+00

The first three columns of each row are the coordinates in color space of the bin center, and the fourth column is the proportion of pixels in that bin. For example, the first bin, defined by RGB triplet [0.16, 0.10, 0.03], is a very dark brown color, and 6.73e-01 or ~67% of the pixels were assigned to this bin. Two bins with the same set of boundaries may have totally different centers, depending on where the pixels are distributed in that bin. If no pixels are assigned to a bin, its center is defined as the midpoint of the ranges in each channel. So in row 7, the RGB triplet is [0.17, 0.83, 0.17] (a bright green) because the bounds were 0–0.33, 0.67–1, and 0–0.33 and there were no bright green pixels in the image. You can visualize this using plotClusters(), or several cluster sets at once using plotClustersMulti() (see last section).

If you want to get the bin centers and sizes for a set of images at once, use the getHistList() function, which just calls on getImageHist() for all of the images it finds in a folder or set of folders.

images <- dir(system.file("extdata", "Heliconius/", package = "colordistance"), full.names = TRUE)
histList <- colordistance::getHistList(images, bins = 2, plotting = FALSE)
## Warning in colordistance::getHistList(images, bins = 2, plotting = FALSE): RGB and HSV are device-dependent, perceptually non-uniform color spaces. See 'Color spaces' vignette for more information.
## Using 2^3 = 8 total bins
# Output of getHistList() is (you guessed it) a list of dataframes as returned by getImageHist()
histList[[1]]
##           r         g          b          Pct
## 1 0.2498276 0.1778456 0.07136988 3.149805e-01
## 2 0.7012230 0.4155931 0.11083536 4.987998e-02
## 3 0.4901961 0.5067538 0.41503268 9.311758e-05
## 4 0.8772877 0.5701055 0.15564208 9.401771e-02
## 5 0.2500000 0.2500000 0.75000000 0.000000e+00
## 6 0.7500000 0.2500000 0.75000000 0.000000e+00
## 7 0.2500000 0.7500000 0.75000000 0.000000e+00
## 8 0.9909855 0.9905125 0.98736656 5.410286e-01
# and list elements are named for the image they came from
names(histList)
## [1] "Heliconius_01" "Heliconius_02" "Heliconius_03" "Heliconius_04"
## [5] "Heliconius_05" "Heliconius_06" "Heliconius_07" "Heliconius_08"

Unless you have a compelling reason to use k-means instead of the color histogram, I strongly recommend using the histogram binning method.

• Quick. Because we’re just counting how many pixels fall into each of a set of predetermined bounds, computing the histogram takes very little time. K-means (discussed below) takes longer, because it requires iteratively choosing where to place the cluster centers in an image-specific manner.

• Consistent comparisons. Because the bins have the exact same bounds for each image, we can compare the number of pixels in a bin in one image to the number of pixels in the same bin for another image without having to decide if the comparison is a fair one. For example, if you compare color histograms of the French and the Canadian flags, the Canadian flag histogram will have an empty blue bin, but the French flag histogram will have a large blue bin – so we can take into account that one image has a color that is missing from the other image. If you only note the colors that are present, it’s difficult to compare images that have totally different colors.

• Details remain. Even if a color takes up a small part of an image, that detail will still show up in the histogram rather than getting swamped by the more dominant colors.

• Dominant colors aren’t overrepresented. Conversely, if most of an object is a single color, meaning there’s more variation in that color purely because there are more pixels of that color present, they will still all get grouped together in a single bin. K-means, on the other hand, might assign several different clusters to the same color because so many of the pixels fall into that range.

• Artificial distinctions. If you have a cluster of pixels near a boundary, they will be counted separately. The histograms above are a good example: the yellow pixels usually got stuck into two different bins, one with the darker yellow and one with the more pale yellow, even though the yellow pixels in the pixel plot are relatively continuous, because the distribution crossed the blue boundary at 0.5.

• Loss of specific color information. Any binning method will sacrifice color information, but the histogram method treats all pixels within the boundaries of a bin as equivalent. You could have clusters of pixels on opposite sides of a bin which are part of very different color clusters, but which end up treated as a single color which is not actually found on the object because those pixels are averaged out.

For example, say we had an image of a red and yellow checkerboard, so that all the pixels were either [1, 0, 0] (red) or [1, 1, 0] (yellow). If we only divided the blue channel into bins, then all of the red and yellow pixels would end up in the bin where $$B \leq 0.5$$, and their average color would be orange – so our color histogram would indicate that we have a completely orange object, rather than a binary red and yellow one. Since the boundaries are arbitrary, they risk not falling along the “natural” clustering boundaries.

## K-means method

The k-means method is implemented using either getKmeanColors() or getKMeansList(), and dataframes compatible with the analysis functions in colordistance are extracted using extractClusters().

Where the histogram method will always use the same set of bins for an image regardless of its content, k-means uses k-means clustering, which aims to choose a provided number of clusters for a dataset which minimizes the sum of the distances between datapoints and their assigned clusters. So if we had an image of the French flag and used k-means to find 3 clusters, it would return a white cluster, a red cluster, and a blue cluster, each of which contained $$\frac{1}{3}$$ of the pixels in the image. If we wanted to get those same clusters back using the histogram method, we’d have to use a larger number of clusters overall, most of which would be empty – and we might have to manually guess where to put the boundaries for the bins.

The input for the k-means functions are therefore slightly simpler, because rather than specify bins for each channel, the most important variable is just the number of clusters, n:

lower <- rep(0.8, 3)
upper <- rep(1, 3)
kmeans01 <- colordistance::getKMeanColors(Heliconius_08, lower = lower, upper = upper, n = 3)

Other than the number of clusters, you can also adjust the sample size of pixels on which the fit is performed. Because k-means is iterative and has to perform a fit multiple times for clusters to converge, fitting hundreds of thousands of pixels is computationally expensive. getKmeanColors() gets around this by randomly selecting a number of object pixels equal to sample.size, which is set to a default of 20,000 pixels.

# Using default sample size
system.time(colordistance::getKMeanColors(Heliconius_08, lower = lower, upper = upper, n = 3, plotting = FALSE))
##    user  system elapsed
##   0.147   0.000   0.148
# Using 10,000 instead of 20,000 pixels is slightly faster, but not by much
system.time(colordistance::getKMeanColors(Heliconius_08, lower = lower, upper = upper, n = 3, plotting = FALSE, sample.size = 10000))
##    user  system elapsed
##   0.089   0.000   0.089
# Using all pixels instead of sample takes 5x longer - and this is a very low-res image!
system.time(colordistance::getKMeanColors(Heliconius_08, lower = lower, upper = upper, n = 3, plotting = FALSE, sample.size = FALSE))
## Performing fit on all pixels (slow for large images).
##    user  system elapsed
##   0.549   0.019   0.570

Unlike the histogram method, k-means will not return the exact same clusters every time you run it, even if you perform the fit on the whole image rather than a subset of pixels – this is also a feature of the iterative behavior. You can minimize the differences by increasing the values of iter.max and nstart, which are passed to the kmeans() function of the stats package. (As you might guess, this makes the function slower.) Unless the image has extremely high color complexity, however, the differences should be minor and in my experience don’t affect analyses.

The output of getKMeanColors() is a kmeans() fit object, a list which contains the cluster centers, a vector indicating which cluster each pixel has been assigned, and a series of statistical measures for the goodness of the k-means fit. This more complete information might be useful for other analyses, but for the rest of the colordistance functions, you’ll then want to run extractClusters() to get a dataframe like the one returned by getImageHist():

kmeansDF <- colordistance::extractClusters(kmeans01)
print(kmeansDF)
##           R          G          B     Pct
## 1 0.1696804 0.09884323 0.03151786 0.69090
## 2 0.8299722 0.82366025 0.52355947 0.05545
## 3 0.5736413 0.28328676 0.10514025 0.25365

Looks pretty similar to the one returned by getImageHist() above, with the obvious difference that there are only 3 clusters, and none of them are empty. To run the analysis for all of the images in a set, use getKmeansList() followed by extractClusters():

# In order to see the clusters for each image, set plotting to TRUE and optionally pausing to TRUE as well
kmeans02 <- colordistance::getKMeansList(images, bins = 3, lower = lower, upper = upper, plotting = F)
kmeansClusters <- colordistance::extractClusters(kmeans02, ordering = T)
head(kmeansClusters, 3)
## $Heliconius_01 ## R G B Pct ## 1 0.2264742 0.1574583 0.05622024 0.5719 ## 2 0.8504897 0.5530428 0.17104902 0.2817 ## 3 0.4399804 0.3123420 0.14664229 0.1464 ## ##$Heliconius_02
##           R         G          B     Pct
## 3 0.2765568 0.1930836 0.07054977 0.32625
## 2 0.8389147 0.5273769 0.15245475 0.47485
## 1 0.5678388 0.3637191 0.11956841 0.19890
##
## \$Heliconius_03
##           R         G          B     Pct
## 3 0.2988745 0.2126601 0.07136217 0.33265
## 2 0.8162724 0.5484303 0.14691387 0.56000
## 1 0.9264108 0.8880536 0.45141511 0.10735

The result is nearly identical in structure to the result of getHistList(), but note the ordering on the far left. Because ordering=T in extractClusters(), the clusters were reordered so that the most similar clusters across each cluster set were in the same row. So the black/dark brown cluster is in the same row for every dataset, and so on. This is important for later analyses in order to compare equivalent colors to each other rather than comparing the red on one butterfly to the black of another, and so on.

• Image-specific color choices. If an image has important color variation in a narrow region of color space, k-means may be able to pick up on it more easily than a color histogram would. If an image has lots of blue and blue-green, for example, then you might need to use a large number of bins for a color histogram in order to draw a boundary between these two colors, and you might end up dividing continuous color clusters in the process. With k-means, since the two colors form natural clusters, they will be separated if the appropriate number of clusters is provided.

• Color palette extraction. A popular use of k-means clustering with images is to extract a color palette to examine and isolate the dominant colors of an image. If you care more about getting the main colors out than about comparing that image to other images for color similarity, this method is more useful than a histogram.

• Objects with the same set of dominant colors. If your dataset is mostly objects of images with the same approximate colors, using a histogram might equal out these more subtle differences and you’d end up with near-identical histograms because different colors fall into the same bin. But note that setting bin.avg=T for histogram functions does retain information on where in each bin the pixels center, so bins aren’t totally equalized.

• Misses details. If a very small portion of an image is a different color, this detail will tend to get swallowed up by a cluster unless a very large number of clusters is specified. This is because k-means clustering tries to minimize the sum of the distances between pixels and their clusters. If a detail color is a small fraction of the pixels, then they don’t contribute much to the sum, and that number can be more effectively decreased by adding more clusters in pixel-dense regions of color space, leaving details out of the cluster set.

• Divides dominant colors into near-identical clusters. The flip side of leaving out details is that dominant colors are over-represented. When a color takes up a large portion of an image, it tends to get broken up into several clusters, because the greatest decrease in pixel-cluster distance can be achieved by adding another cluster in a pixel-dense region. 3 clusters worked well for the butterfly picture earlier, but when we use the default of n=10, we get several black/dark brown clusters, several orange/red ones, and several yellow ones, even though it doesn’t make intuitive sense to divide these colors up this way.

colordistance::getKMeanColors(Heliconius_08, lower = lower, upper = upper, return.clust = FALSE)

• Comparisons for dissimilar objects difficult. If we have two black and white objects, we know it makes sense to compare the amount of black in one to the amount of black in the other and same for the white, rather than the black in one to the white in the other. But what if you’re comparing a black and white object to a blue and yellow one? Or an all-black object to one with 10 distinct colors? Unlike the histogram method, which uses empty bins to register the lack of a color in an image, k-means only returns clusters which are present in an image.

• Requires same number of clusters for every image. If images in a dataset have a wide range of color complexity, it can be difficult to choose the right number of clusters – too many, and simpler images will have their colors divided up into extremely similar but still separate clusters; too few, and details in more complex images will be obscured.

• Slow. k-means clustering is iterative and usually working with thousands of data points to perform a fit, while color histograms just have to count how many pixels fall into certain regions, no fit required. K-means binning usually takes much longer than color histograms, which can make a big difference if you’re working with a large set of images or high-resolution images.

## Choosing a binning method & parameters

The best binning method will depend on the dataset and the details being emphasized for analysis. The pros and cons listed above should help clarify what the effects of each method are likely to be, but there’s no harm in trying out a few different methods. I recommend starting out with the color histogram method unless you have a good reason to use k-means instead – the clusters may not look as intuitive, but the comparisons between images tend to have more statistical merit. Even if a color gets broken up across two bins, it will usually get broken up the same way in two different images, so the histograms will still look similar. And when a color is absent, that’s noted via an empty bin so we can compare presence to absence across images. That said, if your primary concern is extracting dominant colors in an image rather than making meaningful comparisons, k-means might be the way to go. If one were superior to the other in all respects, they wouldn’t both be included!

The nice thing about color clustering is that, unlike most statistical analyses, it’s trying to quantify something which is for the most part fairly visually intuitive – it should be obvious if the parameters you’re choosing are returning scores that don’t make a lot of sense, since we’re ranking images by color similarity. If you try k-means and it fails to cluster visually similar objects together, then k-means probably isn’t the right choice; if you choose too few bins and dissimilar objects are scoring as similar, you probably need to use more bins, and so on.

imageClusterPipeline() is a single function that goes from raw images to distance matrix in one line, making it easy to tweak parameters and methods. Setting clusterMethod="hist" or clusterMethod="kmeans" will toggle between the two methods.

## Cheatsheet

Histogram method

par(mfrow=c(1, 3))
# Get and plot histogram for a single image
hist01 <- colordistance::getImageHist(Heliconius_08, bins = 2, plotting = TRUE, title = "RGB, 2 bins per channel", lower = lower, upper = upper)
## RGB and HSV are device-dependent, perceptually non-uniform color spaces. See 'Color spaces' vignette for more information.
##
## Using 2^3 = 8 total bins
# Use the bin center as the cluster value instead of the average pixel location (note the difference between this and when bin.avg=F)
hist02 <- colordistance::getImageHist(Heliconius_08, bins = 2, plotting = TRUE, title = "bin.avg = F", lower = lower, upper = upper, bin.avg = FALSE)
## RGB and HSV are device-dependent, perceptually non-uniform color spaces. See 'Color spaces' vignette for more information.
##
##
## Using 2^3 = 8 total bins
# Use different number of bins for each channel; use HSV instead of RGB
hist03 <- colordistance::getImageHist(Heliconius_08, bins=c(8, 1, 2), plotting=TRUE, hsv=TRUE, title="HSV, 8 hue, 1 sat, 2 val", lower=lower, upper=upper)
## RGB and HSV are device-dependent, perceptually non-uniform color spaces. See 'Color spaces' vignette for more information.
##
## Using 8*1*2 = 16 bins

# Get histograms for a set of images
histMulti <- colordistance::getHistList(images, bins=2, plotting=FALSE, lower=lower, upper=upper)

K-means method

lower <- rep(0.8, 3)
upper <- rep(1, 3)

# Use defaults
kmeans01 <- colordistance::getKMeanColors(Heliconius_08, n=3, plotting=FALSE, lower=lower, upper=upper)
kmeansDF <- colordistance::extractClusters(kmeans01)

# Use a larger sample size
kmeans02 <- colordistance::getKMeanColors(Heliconius_08, n=3, plotting=FALSE, sample.size = 30000, lower=lower, upper=upper)
kmeansDF2 <- colordistance::extractClusters(kmeans02)

# Don't return clusters as a dataframe
colordistance::getKMeanColors(Heliconius_08, n=15, plotting=FALSE, return.clustlust=FALSE, lower=lower, upper=upper)
# For whole dataset
kmeans03 <- colordistance::getKMeansList(images, n=3, plotting=FALSE, lower=lower, upper=upper)
kmeansList <- colordistance::extractClusters(kmeans03)

Quick comparison

# If we use the same number of clusters for both the histogram and k-means methods, how different do the clusters look?
# Not run in this vignette, but produces 3D, interactive plots!
histExample <- colordistance::getHistList(images, lower = lower, upper = upper)

kmeansExample <- colordistance::extractClusters(colordistance::getKMeansList(images, bins = 27, lower = lower, upper = upper))

colordistance::plotClustersMulti(histExample, title = "Histogram method")

colordistance::plotClustersMulti(kmeansExample, title = "K-means method")

Meyer, Axel. 2006. “Repeating Patterns of Mimicry.” PLOS Biology 4 (10): 1–3. https://doi.org/10.1371/journal.pbio.0040341.

1. Although the 0–255 intensity scale is common for RGB images, R reads images in on a 0–1 intensity scale; unless otherwise stated, the 0–1 scale should be assumed for any colordistance` documentation and examples.↩


text:
## Stream: new members

### Topic: Associativity of kronecker product

#### Yunong Shi (Dec 08 2020 at 21:53):

Hi, everyone. @Runzhou Tao and I are new to Lean. We want to use Lean in quantum computing. As a practice, we want to prove the associativity of tensor products of (finite dimensional) matrices in different dimensions using the following code. It seems like defining kronecker product as on line 14, it depends on the dimension of the matrices, thus we cannot express the associativity theorem easily because the 3rd matrix will have a different dimension (a failed trial is on line 26). I am wondering is there a way of defining kronecker product (and matrices) so that the associativity can be expressed and proved? Thanks!

import data.real.basic
import tactic
import data.matrix.basic

def comp {m n} : fin m → fin n → fin (m * n)
| ⟨a, ha⟩ ⟨b, hb⟩ := ⟨a * n + b, by nlinarith⟩

variables (p q : ℕ)
variables (x : fin p) (y : fin q)

@[simp] def my_matrix (m n : ℕ) := matrix (fin m) (fin n) ℝ

def kron {m1 n1 m2 n2} (a : my_matrix m1 n1) (b : my_matrix m2 n2) : my_matrix (m1*m2) (n1*n2) :=
begin
intros i j,
cases i with i hi,
cases j with j hj,
let i1 := i % m1,
let j1 := j % n1,
let i2 := i / m1,
let j2 := j / n1,
exact 0, -- m1 n1 m2 n2 should not be
end

theorem kron_assoc {m1 n1 m2 n2 m3 n3} (a : my_matrix m1 n1) (b : my_matrix m2 n2) (c : my_matrix m3 n3) :
kron (kron a b) c = kron a (kron b c) := sorry

#### Kevin Buzzard (Dec 08 2020 at 21:59):

Yup, this is a standard problem with dependent type theory and there are a few ways around it, although I still haven't really internalised them. The problem is that x*(y*z) and (x*y)*z are equal, but not definitionally equal.

#### Kevin Buzzard (Dec 08 2020 at 22:06):

This is the ugly way:

def my_matrix_equiv {m₁ n₁ m₂ n₂ : ℕ} (hm : m₁ = m₂) (hn : n₁ = n₂)
(a : my_matrix m₁ n₁) (b : my_matrix m₂ n₂) : Prop :=
∀ (i : fin m₁) (j : fin n₁), a i j = b ⟨i.1, hm ▸ i.2⟩ ⟨j.1, hn ▸ j.2⟩

theorem kron_assoc {m1 n1 m2 n2 m3 n3} (a : my_matrix m1 n1) (b : my_matrix m2 n2) (c : my_matrix m3 n3) :
my_matrix_equiv (mul_assoc _ _ _) (mul_assoc _ _ _) (kron (kron a b) c) (kron a (kron b c)) := sorry

but I think there are better ways nowadays.

#### Eric Wieser (Dec 08 2020 at 22:44):

Note that comp a b exists already as docs#fin_prod_fin_equiv, fin_prod_fin_equiv (a, b)

#### Eric Wieser (Dec 08 2020 at 22:45):

You can also use heq, which isn't always as bad as its made out to be, kron (kron a b) c == kron a (kron b c)

#### Yakov Pechersky (Dec 08 2020 at 22:48):

import data.matrix.notation

section repr

variables {m' n' : ℕ} {X : Type*} [has_repr X]

def vec_repr : Π {n' : ℕ}, (fin n' → X) → string :=
λ _ v, string.intercalate ", " ((vector.of_fn v).to_list.map repr)

instance vec_repr_instance : has_repr (fin n' → X) := ⟨vec_repr⟩

def matrix_repr : Π {m' n'}, matrix (fin m') (fin n') X → string :=
λ _ _ M, string.intercalate ";\n" ((vector.of_fn M).to_list.map repr)

instance matrix_repr_instance :
has_repr (matrix (fin n') (fin m') X) := ⟨matrix_repr⟩

end repr

section kron

variables {K : Type*} [semiring K]

def kron {m1 n1 m2 n2 : ℕ}
(a : matrix (fin (m1 + 1)) (fin (n1 + 1)) K) (b : matrix (fin (m2 + 1)) (fin (n2 + 1)) K) :
matrix (fin ((m1 + 1) * (m2 + 1))) (fin ((n1 + 1) * (n2 + 1))) K :=
λ i j, ((a ⟨i / (m2 + 1), (nat.div_lt_iff_lt_mul' (nat.succ_pos')).mpr i.is_lt⟩
⟨j / (n2 + 1), (nat.div_lt_iff_lt_mul' (nat.succ_pos')).mpr j.is_lt⟩)
• b)
⟨i % (m2 + 1), nat.mod_lt _ nat.succ_pos'⟩
⟨j % (n2 + 1), nat.mod_lt _ nat.succ_pos'⟩

#eval kron ![![1, 2], ![3, 4]] ![![0, 5], ![6, 7]]
/-
0, 5, 0, 10;
6, 7, 12, 14;
0, 15, 0, 20;
18, 21, 24, 28
-/

theorem kron_assoc
{m1 n1 m2 n2 m3 n3 : ℕ} {K : Type*} [semiring K]
(a : matrix (fin (m1 + 1)) (fin (n1 + 1)) K)
(b : matrix (fin (m2 + 1)) (fin (n2 + 1)) K)
(c : matrix (fin (m3 + 1)) (fin (n3 + 1)) K)
:
kron (@kron _ _ _ _ _ _ a b) c == (@kron _ _ _ _ _ _ a (@kron _ _ _ _ _ _ b c)) := sorry

#### Yakov Pechersky (Dec 08 2020 at 23:04):

Although proving associativity might be a tiny bit simpler if the mul definition is used instead of smul

#### Frédéric Dupuis (Dec 08 2020 at 23:39):

Hi and welcome! I also work in quantum information, and I've thought a bit about the best way to represent states on multiple quantum systems in Lean. I think the way to go will be to write a pi-type version of the code in linear_algebra/tensor_product.lean. What we have there is the tensor product of two spaces M and N, and it's defined as a free_add_monoid M × N quotiented by an appropriate equivalence relation, so basically arbitrary sums of vectors of the form x ⊗ y and then selecting the right equivalence classes. I think we should do the same thing with free_add_monoid (Π i : ι, f i) with f : ι → Type* in order to have more than two systems. This would have the advantage of avoiding these associativity problems, by not even having an order on the systems in the first place.

#### Frédéric Dupuis (Dec 08 2020 at 23:43):

It also lets us work at a more abstract level, which I've (somewhat counterintuitively) found to be a lot easier in Lean. I also tried to go this route when I first learned Lean (i.e. do everything with concrete matrices) and it was constant pain, with indices everywhere.

#### Yunong Shi (Dec 09 2020 at 00:25):

Thanks everyone. It will take some time for me to fully understand your replies. Let me get back to some of you later.

#### Yunong Shi (Dec 09 2020 at 00:34):

@Frédéric Dupuis Thanks for the great suggestions and glad to know someone here is in quantum computation as well! As I understand your comment, there are two suggestions: 1. we can work with abstract tensor product that defined in linear_algebra/tensor_product.lean. 2. Using Pi-type to get rid of the dimension dependence. For 1, will the abstract definition make some proof harder, for example, prove some concrete results are indeed tensor products? For 2, I think it's a great idea! Will it involve some changes in the matrix definition (matrices with arbitrary dimensions)? Maybe I should look into the implementation more.

#### Alexander Bentkamp (Dec 09 2020 at 09:06):

@Frédéric Dupuis @Yunong Shi Not sure if it's useful for your application, but I've formalized an alternative definition of tensors in here:
https://github.com/leanprover-community/mathlib/blob/1f309c52c472a6cd37e41c580a470033e63d4720/src/data/holor.lean

We called this alternative view on tensors "holors" (I think we found that word in the literature somewhere). The difference is that this definition views the tensors as multidimensional arrays, not as functions. It's like viewing linear maps as matrices. The holor file also contains a proof of associativity of the tensor product.

#### Eric Wieser (Dec 09 2020 at 09:19):

@Alexander Bentkamp, is there a reason you use \N and not fin n like matrices (usually) use?

#### Alexander Bentkamp (Dec 09 2020 at 09:30):

I guess it makes the whole definition a bit simpler, but I am not sure. In some sense, the definition of holor_index is like fin n, but on lists.

#### Alexander Bentkamp (Dec 09 2020 at 09:33):

How would the definition of holor_index look like with fin n? I guess you would need a Pi-type or something?

#### Alexander Bentkamp (Dec 09 2020 at 09:33):

For matrices, it's simpler. It's just fin n ⨉ fin m.

#### Eric Wieser (Dec 09 2020 at 09:38):

def holor {n : ℕ} (α : Type*) (ds : fin n → Type*) [∀ i, fintype (ds i)] := (Π i, ds i) → α

#### Eric Wieser (Dec 09 2020 at 09:40):

Eg holor ℝ ![fin 2, fin 3, fin 4] for a 2x3x4 tensor

#### Alexander Bentkamp (Dec 09 2020 at 09:40):

wow, what is the ![...] notation? It constructs fin n?

#### Eric Wieser (Dec 09 2020 at 09:41):

https://leanprover-community.github.io/mathlib_docs/data/matrix/notation.html

#### Alexander Bentkamp (Dec 09 2020 at 09:42):

Well, then the reason for my definition was that the fin n/matrix library wasn't as developed back then.

#### Eric Wieser (Dec 09 2020 at 09:42):

It constructs fin n → T

#### Eric Wieser (Dec 09 2020 at 09:43):

Ugh, that definition doesn't work: (https://leanprover.zulipchat.com/#narrow/stream/113488-general/topic/fintype.20instances.20for.20matrix.20notation/near/219314820)

#### Eric Wieser (Dec 09 2020 at 10:06):

On second thoughts, my definition probably doesn't work because it means 2-tensors and 3-tensors have different types

#### Eric Wieser (Dec 09 2020 at 10:07):

Maybe I'll explore trying to overhaul holor to use it and see where I get stuck

#### Alexander Bentkamp (Dec 09 2020 at 10:18):

Sure, go for it. It would be nice to have it more consistent with the matrix library.

#### Eric Wieser (Dec 09 2020 at 10:44):

Having explored a little more, I think all the holor_index stuff is still quite hard to write with fin. #4406 would make it easier.

#### Frédéric Dupuis (Dec 09 2020 at 13:29):

@Alexander Bentkamp Thanks for pointing this out! This is very close to what I want, but I think the definition I outlined above would still be worth doing, for a few reasons. I would really like to avoid having the tensor factors indexed by a specific predefined type like ℕ or fin n: for example, in a typical application in quantum information, we would have a quantum state $|φ⟩_{A^n B^n E}$ with $A^n$ and $B^n$ being two $n$-qubit states, and $E$ being some other quantum system. So this object would be a vector in a space that is the tensor product of $2n+1$ spaces with those labels, and I'd like to be able to keep those system labels and never have to artificially number them. Also, one would want to be able to support infinite-dimensional spaces, which wouldn't be possible with holors.

#### Frédéric Dupuis (Dec 09 2020 at 13:46):

@Yunong Shi I don't know what your plans are, but here's my take on doing quantum information in Lean at the moment: we're not there yet! :-) To give you an idea of the current situation, unitaries are not there, adjoints are not there (so forget Hermitian operators), there is no spectral decomposition, and we only got complex inner products and eigenvalues about two months ago. If you have a specific application that doesn't require too many of those features it might be possible to get started now, but personally my plan is to try to get those into mathlib by making PRs whenever I have a bit of time before trying to do actual quantum information.

#### Frédéric Dupuis (Dec 09 2020 at 13:49):

Depending on what you're doing, one option might be to switch to Coq and use this library: https://github.com/inQWIRE/QWIRE

#### Yunong Shi (Dec 09 2020 at 19:48):

Frédéric Dupuis said:

Yunong Shi I don't know what your plans are, but here's my take on doing quantum information in Lean at the moment: we're not there yet! :-) To give you an idea of the current situation, unitaries are not there, adjoints are not there (so forget Hermitian operators), there is no spectral decomposition, and we only got complex inner products and eigenvalues about two months ago. If you have a specific application that doesn't require too many of those features it might be possible to get started now, but personally my plan is to try to get those into mathlib by making PRs whenever I have a bit of time before trying to do actual quantum information.

Thanks for the info. I'd love to help with the dev of libraries for quantum information. I will probably look at the code you mentioned and play around with it first.

#### Frédéric Dupuis (Dec 10 2020 at 19:01):

I just managed to motivate myself to have a crack at this idea for the tensor product of an indexed family of spaces: #5311

#### Eric Wieser (Dec 10 2020 at 21:58):

What should the tensor product of an empty index be? For the sake of tensor algebras, it feels like it should be isomorphic to R, but I think your PR is isomorphic to the trivial ring.

#### Kevin Buzzard (Dec 10 2020 at 21:58):

$M^{\otimes 0}=R$ but I'm not sure if that's what you're asking

#### Riccardo Brasca (Dec 10 2020 at 22:03):

If you mean $\bigotimes_{i \in \emptyset} M_i$, this should definitely be $R$, as in Kevin's answer.

#### Riccardo Brasca (Dec 10 2020 at 22:03):

Having it the zero ring would break the usual formulas for the union of set indexes.

#### Eric Wieser (Dec 10 2020 at 22:06):

That's mostly what I'm asking, but for an indexed tensor product instead of a homogenous power - edit: yes

#### Frédéric Dupuis (Dec 10 2020 at 23:38):

My math answer would also be R, but right now the code assumes that the index type is nonempty.

#### Frédéric Dupuis (Dec 10 2020 at 23:39):

It's a bit awkward to change, because the has_scalar instance is defined by choosing one of the indices and doing smul on that coordinate.

#### Frédéric Dupuis (Dec 10 2020 at 23:41):

Also right now we can only do the tensor product over the whole type, and not a subset. It might be useful to put that in actually.

#### Eric Wieser (Dec 11 2020 at 00:00):

Storing an R and Pi i, M i term separately under your quotient would fix that base case

#### Frédéric Dupuis (Dec 11 2020 at 00:13):

Yeah, I was hoping for a more clever way but it doesn't look possible.

Last updated: May 14 2021 at 22:15 UTC


text:
• 操作系统抢占式优先级调度Priority scheduling is a type of scheduling algorithm used by the operating system to schedule the processes for execution. The priority scheduling has both the preemptive mode...
操作系统抢占式优先级调度Priority scheduling is a type of scheduling algorithm used by the operating system to schedule the processes for execution. The priority scheduling has both the preemptive mode of scheduling and the non-preemptive mode of scheduling. Here, we will discuss the non-preemptive priority scheduling algorithm.
优先级调度是操作系统用来调度要执行的进程的调度算法。 优先级调度既有抢占式调度又有非抢占式调度。 在这里， 我们将讨论非抢占式优先级调度算法 。
As the name suggests, the scheduling depends upon the priority of the processes rather than its burst time. So, the processes, in this case, must also have the priority number in its details on the basis of which the OS will schedule it.
顾名思义，调度取决于进程的优先级，而不是突发时间。 因此，在这种情况下，进程还必须在其详细信息中具有优先级号，操作系统将根据该优先级号对其进行调度。
For example, suppose we have 4 processes: P1, P2, P3 and P4 and they enter the CPU as follows:
例如，假设我们有4个进程： P1 ， P2 ， P3和P4 ，它们按如下方式进入CPU：
Note: Here, lower the priority number, higher is the priority.
注意：此处，优先级数字越低，优先级越高。
As per the non-preemptive priority scheduling, the processes will be executed as follows:
根据非抢先优先级调度 ，将按以下方式执行过程：
Gant Chart:
甘特图：
Explanation:
说明：
There is only P1 available at time 0, so it will be executed first irrespective of the priority, and it cannot be preempted in between before its completion. 在时间0只有P1可用，因此无论优先级如何都将首先执行它，并且在完成之前不能抢占它。 When it is completed at 4th-time unit, we have all P2, P3, and P4 available. So, they are executed according to their priorities. 当以第 4 次单位完成时，我们将拥有所有P2 ， P3和P4 。 因此，将根据优先级执行它们。     Total Turn Around Time = 4 + 7 + 9 + 2
= 22 milliseconds
Average Turn Around Time= Total Turn Around Time / Total No. of Processes
= 22 / 4
= 5.5 milliseconds

Total Waiting Time = 0 + 5 + 6 + 0
= 11 milliseconds
Average Waiting Time = Total Waiting Time / Total No. of Processes
= 11 / 4
= 2.75 milliseconds

翻译自: https://www.includehelp.com/operating-systems/priority-scheduling-non-preemptive.aspx操作系统抢占式优先级调度
展开全文
• 操作系统抢占式优先级调度In the priority scheduling, the processes are scheduled on the basis of their priority, and not on the basis of their burst time. If the preemptive mode of this scheduling is ...
操作系统抢占式优先级调度In the priority scheduling, the processes are scheduled on the basis of their priority, and not on the basis of their burst time. If the preemptive mode of this scheduling is being followed, then a process with a higher priority than the currently executing process can replace the executing process. This can be well explained with the help of the following example:
在优先级调度中 ，将根据进程的优先级而不是根据突发时间来调度进程。 如果遵循此调度的抢占模式 ，则优先级高于当前正在执行的进程的进程可以替换正在执行的进程。 可以通过以下示例很好地解释这一点：
Suppose, we have four processes: P1, P2, P3 and P4, and they enter the CPU in the following manner:
假设我们有四个进程： P1 ， P2 ， P3和P4 ，它们以以下方式进入CPU：
As per the preemptive priority scheduling, the processes will be executed as follows:
根据抢先优先级调度 ，这些过程将按以下方式执行：
Gant Chart
甘特图
Explanation:
说明：
There is only P1 available at time 0, so it will be executed first irrespective of the priority until some other process with a higher priority is encountered by the OS. 在时间0只有P1可用，因此它将优先于优先级执行，直到OS遇到其他具有更高优先级的进程为止。 At the beginning of the 1st-time unit, we have P2 which has a higher priority than P1, so it replaces P1. 在第1 个 -时间单元的开始，我们有P2具有比P1更高的优先级，因此它取代P1。 At 2nd time unit, we have the process P3, but its priority is less than the executing process P2, so P2 keeps executing without any replacement. 在第二时间单位，我们有进程P3 ，但是它的优先级小于执行进程P2 ，因此P2继续执行而没有任何替换。 At 3rd time unit, our P2 has been completed and till now we have processes P1 and P3 left. So, P1 which has a higher priority than P3 is executed. 在第三个时间单元，我们的P2已完成，到现在为止，我们还有流程P1和P3 。 因此，执行优先级高于P3的 P1 。 At 4th time unit, we have process P4 which has the highest priority of them all. So, it replaces P1. 在第 4 个时间单位，我们有进程P4 ，它是所有进程中的最高优先级。 因此，它将替换P1 。 Since now we have no more processes left to arrive, the processes will now run according to their priorities and will complete their execution. 从现在开始，我们不再需要其他任何流程，这些流程将根据其优先级运行并完成其执行。     Total Turn-Around Time = 8 + 2 + 9 + 2
= 21 milliseconds
Average Turn-Around Time= Total Turn-Around Time / Total No. of Processes
= 21 / 4
= 5.25 milliseconds

Total Waiting Time = 4 + 0 + 6 + 0
= 10 milliseconds
Average Waiting Time = Total Waiting Time / Total No. of Processes
= 10 / 4
= 2.5 milliseconds

翻译自: https://www.includehelp.com/operating-systems/priority-scheduling-preemptive.aspx操作系统抢占式优先级调度
展开全文
• 某小型实时操作系统采用优先级进行调度，就绪表最多容纳32个任务，用4个元素的数组P表示就绪表，每个元素为一个字节，每个字节的一位表示该优先级的任务是否就绪。若P[0]=00100010,则表示优先级为1与优先级为5的任务...
• 优先级调度算法动态优先级We are already familiar with what Priority Scheduling is. It is one of the most used process scheduling algorithm used in operating systems, in which every process is assigned ...
优先级调度算法动态优先级We are already familiar with what Priority Scheduling is. It is one of the most used process scheduling algorithm used in operating systems, in which every process is assigned with a priority. According to this algorithm, the process with the highest priority is set to be provided the CPU first or simply is to be executed first.
我们已经熟悉什么是优先调度。 它是操作系统中使用最广泛的进程调度算法之一，在该算法中，每个进程都分配了优先级。 根据该算法，将优先级最高的过程设置为首先提供给CPU或简单地首先执行。
In priority scheduling algorithm, a major problem to be considered is the starvation of a process i.e. a process which is ready to be executed but is waiting for the CPU because of its low priority. This can lead to the indefinite waiting of the low-priority processes. A continuous flow of higher priority processes to the O.S can prevent a low priority process from ever getting the CPU.
在优先级调度算法中 ，要考虑的主要问题是进程的饥饿 ，即由于其低优先级而准备执行但正在等待CPU的进程。 这可能导致无限期等待低优先级进程。 高优先级进程不断流向OS可以防止低优先级进程获得CPU。
Let's take an example to understand what starvation is. Suppose there are 100 processes in which a process 'X' has the lowest priority because of which it will be executed at last. Let say before the process 'X' is provided CPU for the execution some more processes are provided to the operating system having a priority higher than that of process 'X'. Now what will happen is, the process 'X' won't get the chance to get executed no matter what was its arrival time. It is possible that, as the time passes by the O.S is given more processes having higher priority than that of 'X', due to which 'X' can wait indefinitely or could never be executed. This Problem is known as 'Starvation'.
让我们举一个例子来了解什么是饥饿 。 假设有100个进程，其中进程'X'具有最低优先级，因为它最终将被执行。 可以说，在为CPU提供进程“ X”以供执行之前，向操作系统提供的其他进程的优先级高于进程“ X”的优先级。 现在将要发生的是，无论到达时间是什么，进程“ X”都不会有执行的机会。 随着时间的流逝，可能会给OS提供更多比'X'具有更高优先级的进程，因此'X'可以无限期等待或无法执行。 这个问题被称为“饥饿” 。
For solving the problem of starvation we have the concept of Aging. In aging what we do is increasing the priority of those process that has been waiting long because of low priority after some specified amount of time. Due to which after the specified time its priority is increased and could be provided with the CPU for the execution.

为了解决饥饿问题，我们有老龄化的概念。 在老化中，我们要增加由于在指定的时间量后优先级较低而一直等待很久的那些进程的优先级。 因此，在指定的时间之后，其优先级会增加，并且可以随CPU提供以执行该优先级。
翻译自: https://www.includehelp.com/operating-systems/problem-associated-with-priority-scheduling-and-its-solution.aspx优先级调度算法动态优先级
展开全文
• 优先级调度算法c实现Here you will get C and C++ program for priority scheduling algorithm. 在这里，您将获得用于优先级调度算法的C和C ++程序。 What is Priority Scheduling Algorithm? 什么是优先级调度...
优先级调度算法c实现Here you will get C and C++ program for priority scheduling algorithm.
在这里，您将获得用于优先级调度算法的C和C ++程序。
What is Priority Scheduling Algorithm?
什么是优先级调度算法？
In priority scheduling algorithm each process has a priority associated with it and as each process hits the queue, it is stored in based on its priority so that process with higher priority are dealt with first. It should be noted that equal priority processes are scheduled in FCFS order.

Also Read: C Program for Shortest Job First (SJF) Scheduling Algorithm
在优先级调度算法中，每个进程都具有与之关联的优先级，并且当每个进程到达队列时，将根据其优先级将其存储在其中，以便优先处理优先级较高的进程。 应该注意的是，以FCFS顺序安排优先级相同的进程。
另请阅读： 最短作业优先(SJF)调度算法的C程序
C/C++ Program for First Come First Served (FCFS) Scheduling Algorithm用于先到先得(FCFS)调度算法的C / C ++程序To prevent high priority processes from running indefinitely the scheduler may decrease the priority of the currently running process at each clock tick (i.e., at each clock interrupt). If this action causes its priority to drop below that of the next highest process, a process switch occurs. Alternatively, each process may be assigned a maximum time quantum that it is allowed to run. When this quantum is used up, the next highest priority process is given a chance to run.
为了防止高优先级进程无限期地运行，调度程序可以在每个时钟滴答时(即，在每个时钟中断时)降低当前正在运行的进程的优先级。 如果此操作导致其优先级降低到下一个最高进程的优先级以下，则会发生进程切换。 替代地，可以为每个过程分配允许其运行的最大时间量。 当这个数量用完时，下一个优先级最高的进程将有机会运行。
局限性 (Limitations)The problem occurs when the operating system gives a particular task a very low priority, so it sits in the queue for a larger amount of time, not being dealt with by the CPU. If this process is something the user needs, there could be a very long wait, this process is known as “Starvation” or “Infinite Blocking”.
当操作系统为特定任务赋予非常低的优先级时，就会发生此问题，因此它会在队列中停留较长的时间，而不会由CPU处理。 如果用户需要此过程，则可能要等待很长时间，此过程称为“饥饿”或“无限阻止”。
解 (Solution)Many operating systems use a technique called “aging”, in which a low priority process slowly gains priority over time as it sits in the queue. Even if, the priority of the process is low, there is a surety of its execution.
许多操作系统使用一种称为“老化”的技术，其中低优先级的进程位于队列中时，它会随着时间的流逝逐渐获得优先级。 即使该进程的优先级较低，也可以肯定其 执行。
C程序 (C Program)
#include<stdio.h>

int main()
{
int bt[20],p[20],wt[20],tat[20],pr[20],i,j,n,total=0,pos,temp,avg_wt,avg_tat;
printf("Enter Total Number of Process:");
scanf("%d",&n);

printf("\nEnter Burst Time and Priority\n");
for(i=0;i<n;i++)
{
printf("\nP[%d]\n",i+1);
printf("Burst Time:");
scanf("%d",&bt[i]);
printf("Priority:");
scanf("%d",&pr[i]);
p[i]=i+1;           //contains process number
}

//sorting burst time, priority and process number in ascending order using selection sort
for(i=0;i<n;i++)
{
pos=i;
for(j=i+1;j<n;j++)
{
if(pr[j]<pr[pos])
pos=j;
}

temp=pr[i];
pr[i]=pr[pos];
pr[pos]=temp;

temp=bt[i];
bt[i]=bt[pos];
bt[pos]=temp;

temp=p[i];
p[i]=p[pos];
p[pos]=temp;
}

wt[0]=0;	//waiting time for first process is zero

//calculate waiting time
for(i=1;i<n;i++)
{
wt[i]=0;
for(j=0;j<i;j++)
wt[i]+=bt[j];

total+=wt[i];
}

avg_wt=total/n;      //average waiting time
total=0;

printf("\nProcess\t    Burst Time    \tWaiting Time\tTurnaround Time");
for(i=0;i<n;i++)
{
tat[i]=bt[i]+wt[i];     //calculate turnaround time
total+=tat[i];
printf("\nP[%d]\t\t  %d\t\t    %d\t\t\t%d",p[i],bt[i],wt[i],tat[i]);
}

avg_tat=total/n;     //average turnaround time
printf("\n\nAverage Waiting Time=%d",avg_wt);
printf("\nAverage Turnaround Time=%d\n",avg_tat);

return 0;
}
C ++程序 (C++ Program)
#include<iostream>

using namespace std;

int main()
{
int bt[20],p[20],wt[20],tat[20],pr[20],i,j,n,total=0,pos,temp,avg_wt,avg_tat;
cout<<"Enter Total Number of Process:";
cin>>n;

cout<<"\nEnter Burst Time and Priority\n";
for(i=0;i<n;i++)
{
cout<<"\nP["<<i+1<<"]\n";
cout<<"Burst Time:";
cin>>bt[i];
cout<<"Priority:";
cin>>pr[i];
p[i]=i+1;           //contains process number
}

//sorting burst time, priority and process number in ascending order using selection sort
for(i=0;i<n;i++)
{
pos=i;
for(j=i+1;j<n;j++)
{
if(pr[j]<pr[pos])
pos=j;
}

temp=pr[i];
pr[i]=pr[pos];
pr[pos]=temp;

temp=bt[i];
bt[i]=bt[pos];
bt[pos]=temp;

temp=p[i];
p[i]=p[pos];
p[pos]=temp;
}

wt[0]=0;            //waiting time for first process is zero

//calculate waiting time
for(i=1;i<n;i++)
{
wt[i]=0;
for(j=0;j<i;j++)
wt[i]+=bt[j];

total+=wt[i];
}

avg_wt=total/n;      //average waiting time
total=0;

cout<<"\nProcess\t    Burst Time    \tWaiting Time\tTurnaround Time";
for(i=0;i<n;i++)
{
tat[i]=bt[i]+wt[i];     //calculate turnaround time
total+=tat[i];
cout<<"\nP["<<p[i]<<"]\t\t  "<<bt[i]<<"\t\t    "<<wt[i]<<"\t\t\t"<<tat[i];
}

avg_tat=total/n;     //average turnaround time
cout<<"\n\nAverage Waiting Time="<<avg_wt;
cout<<"\nAverage Turnaround Time="<<avg_tat;

return 0;
}
Output
输出量
翻译自: https://www.thecrazyprogrammer.com/2014/11/c-cpp-program-for-priority-scheduling-algorithm.html优先级调度算法c实现
展开全文
• 操作系统实验课程中进程优先级调度算法利用C语言实现程序
• 这是操作系统中的调度问题，调度策略是动态优先级调度，仅是模拟
• 操作系统中的优先级调度和轮转调度 在遭受了大概前后三个下午的折磨之后，我决定把这个痛苦的经历的结果记录下来，于是有了我的第一篇CSDN的博客。 优先级调度和轮转调度的c语言实现 先简述一下实现的过程吧 就是用...
• 处理器优先级调度 操作系统 调度 OS
• 操作系统进程调度中，优先级调度算法模拟，模拟进程调度，采用优先级调度算法，非抢占式，资源分配，资源分配。
• c语言版本，使用数据结构简单实现抢占式动态优先级调度算法
• 最近学习了操作系统内诸多进程调度算法，动手实现了抢占式优先级调度算法 知识点 该算法又称为优先权调度算法，他既可以用于作业调度，又可用于进程调度。该算法中的优先级用于描述作业运行的紧迫程度。 两种类型： ...
• 优先级调度算法 优先级调度算法的类型 优先级调度算法，是把处理机分配给就绪队列中优先级最高的进程。其中又可进一步把该算法分为下面两种。 1、非抢占式优先级调度算法。该算法规定，一旦处理机分配给就绪队列中...
• 《计算机与操作系统（第四版）》进程优先级调度算法 1.时间片轮转调度算法 2.多级反馈队列调度算法 3.高响应比优先调度算法
• 优先级调度算法3.多级反馈队列调度算法4.三种算法的对比总结 0.思维导图 1.时间片轮转—RR Round-Robin 时间片为2举例 以时间片为5举例 可能出现的问题，比如与FCFS对比 2.优先级调度算法 非抢占式例子 -...
• 有各种优先级调度 数组编写 简单 是本人自己写的 可供参考
• 1. 优先级调度算法的类型 优先级进程调度算法，是把处理机分配给就绪队列中优先级最高的进程。这时，又可进一步把该算法分成如下两种。 非抢占式优先级调度算法。 抢占式优先级调度算法。 2. 优先级的类型 静态...
• 实时操作系统优先级调度算法 非抢占式 抢占式优先级调度算法：新进程来的时候判断一下是不是要抢占只有第1级队列所以的运行完了才会把CPU给第2级队列，P2在第二级队列运行到1个时间片后 P3到达第1级队列，此时P2就...
• ## 优先级调度算法

万次阅读 多人点赞 2018-04-24 23:54:39
优先调度算法的类型（用于作业调度） 1）非抢占式优先权调度算法 系统一旦把处理机分配给优先权最高的进程后，便一直执行下去，至完成。 2）抢占式优先权调度算法 只要系统中出现一个新的就绪进程，就进行优先权...
• Java操作系统进程调度算法——优先级调度(HPF)算法 文章目录Java操作系统进程调度算法——优先级调度(HPF)算法前言一、算法思想二、数据结构1.定义(PCB)进程控制块2.实现思路三、流程图四、完整代码运行结果1、输入...
• 优先级调度算法，就是把处理机分配给就绪队列中优先级最高的进程，细分有非抢占式和抢占式两种
•  用高级语言编写和调试一个进程调度程序，以加深对进程的概念及进程调度算法的理解． [准备知识]   一、基本概念 1、进程的概念； 2、进程的状态和进程控制块； 3、进程调度算法 [试验内容]  设计一个有 N个进程...
• 动态优先级算法 动态优先数是指在进程创建时先确定一个初始优先数， 以后在进程运行中随着进程特性的改变不断修改优先数，这样，由于开始优先数很低而得不到CPU的进程，就能因为等待时间的增长而优先数变为最高而...
• 嵌入式系统设计过程中任务优先级调度的策略   调度程序的功能是调度任务的执行顺序，非调度实体的存在却会导致调度程序的效率下降，为时限调度程序而设计的系统总是尽可能地减少非调度实体的数量以及这些实体...
• 设计一个按照优先级调度算法实现处理机调度的程序 一、优先级调度算法实现处理机调度的程序设计提示如下： ( 1 ) 假设系统有n个进程，每个进程用一个进程控制块（PCB）来代表。进程控制块的格式如下表所示，且参数...
• Task1.5 实现优先级调度  Implement priority scheduling in Nachos by completing the PriorityScheduler class. Priority scheduling is a key building block in real-time systems. Note that in order to ...
• PAGE / NUMPAGES 优先级调度算法 1调度算法 考虑到紧迫型作业进入系统后能得到优先处理,引入了高优先级优先调度算法 优先级调度的含义 当该算法用于作业调度时,系统从后背作业队列中选择若干个优先级最高的,且系统能...
• 实验目的 本实验模拟在单处理机情况下的处理机调度，帮助学生了解处理机调度的工作。 实验内容 设计一个按优先数调度算法实现处理机调度的程序。
• 题目二：设计一个按照优先级调度算法实现处理机调度的程序 优先级调度算法实现处理机调度的程序设计提示如下： （1） 假设系统有n个进程，每个进程用一个进程控制块（PCB）来代表。进程控制块的格式如下表所示，且...

...


text:
The current GATK version is 3.7-0
Examples: Monday, today, last week, Mar 26, 3/26/04

#### Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

You can opt in to receive email notifications, for example when your questions get answered or when there are new announcements, by following the instructions given here.

#### ☞ Formatting tip!

Wrap blocks of code, error messages and BAM/VCF snippets--especially content with hashes (#)--with lines with three backticks (  ) each to make a code block as demonstrated here.

GATK 3.7 is here! Be sure to read the Version Highlights and optionally the full Release Notes.

# SuperArray

edited September 2012

### 1. Introduction

The SuperArray annotator is invoked through the
SVVariantAnnotator walker, which defines arguments
common to all annotators.

The SuperArray annotator uses array intensity data to do a form of ''in
silico'' validation of copy number variants.

This annotator requires that each variant indicate (through an INFO tag) the set of samples that are thought to carry the variant (either as homozygotes or heterozygotes). A Wilcoxon rank sum test is performed and a p-value calculated
as follows: For each array probe underlying the variant, each sample is
assigned an integral rank for that probe. Then the set of ranks (across all
probes) is combined and treated as a set of observations for the Wilcoxon rank
sum test. If there is more than one probe, there will certainly be ties (i.e.
some sample will be rank 1 with respect to each probe). Ties are broken
randomly to assign the final ranking.

A Wilcoxon rank sum test is then used to test whether the event-carrying
samples (as indicated by the INFO tag) are shifted with respect to the non-
event-carrying samples (for deletions, this is a one tailed test of a negative
shift).

### 2. Inputs / Arguments

• -arrayIntensityFile <data-file> : The path to an input file containing a
matrix of array intensity values. : The file must be tab delimited with a
header line. Each line of the file contains data for one probe. The first four
columns should be named ID, CHR, START and END. ID is an identifier for the
probe and the other three columns give the 1-relative coordinates of the probe
(START and END can be equal). Columns beyond the first four provide intensity
data for each sample. The header for each additional column should contain the
sample ID.

• -superArraySampleTag <tag-name> : This is the name of the INFO field that
contains the list of carrier samples, which must be comma-separated. The default tag name is _SASAMPLES_. For example, SASAMPLES=NA12878,NA12891,NA12892 would indicate that three samples carry the
variant.

• -sample <sample-or-sample-list> : A subset of samples on which to perform the test (or a .list file of sample identifiers). The default behavior is to use all samples in the array intensity file.

• -superArrayPermute <true/false> : If set to true, then the sample identities are permuted before performing the test to generate a null distribution.

### 3. Annotations

This annotator produces three INFO field annotations for each VCF record:

• SANSAMPLES : The number of carrier samples.

• SANPROBES : The number of probes underlying the event.

• SAPVALUE : The calcualted p-value.

The annotator can also generate a tab-delimited report file containing these
annotations.

### 4. Example

The SuperArray annotator requires Genome STRiP and R.

export SV_DIR=/path/to/SVToolkit/root/directory

java -Xmx4g -cp SVToolkit.jar:GenomeAnalysisTK.jar \
-T SVVariantAnnotator \
-A SuperArray \
-R /humgen/1kg/reference/human_g1k_v37.fasta \
-BTI variant \
-B:variant,VCF input.vcf \
-O output.vcf \
-arrayIntensityFile Omni25_superarray_intensity_matrix.dat \
-sample discovery_samples.list \
-superArraySampleTag SAMPLES \
-writeReport \
-reportFile superarray_output.dat
`

### 5. Performance

The SuperArray annotator uses R as well as java and can consume up to 10G of
memory.

The SuperArray annotator uses an exact test in many cases and this can be
expensive. If you want to test more than a few hundred variants, you should
consider splitting up the input VCF file and processing them in parallel. In
sample runs, testing 1000 variants in 1000 samples can take 2 to 3 hours.

Post edited by Geraldine_VdAuwera on
Tagged:


text:
My Math Forum Nobel Prize Application - Phillips Theory

 New Users Post up here and introduce yourself!

 April 17th, 2012, 07:17 PM #1 Newbie   Joined: Apr 2012 Posts: 2 Thanks: 0 Nobel Prize Application - Phillips Theory To My Maths Friends - I am requesting the nobel prize, and 6 flights to Monte Carlo, after my discovery of the 'Phillips Box' - i have coined. In my theory, the co-ordinates: z=-5 x=5 y=5 y=-5 x=-5 z=5 When plotted on the Cartesian plane, together make a perfect cube. I will be happy to receive my nobel prize by next wednesday. Thanks, Mr. Phillips (Founder of the Phillips's Box)
 April 17th, 2012, 07:29 PM #2 Senior Member     Joined: Jul 2010 From: St. Augustine, FL., U.S.A.'s oldest city Posts: 12,211 Thanks: 521 Math Focus: Calculus/ODEs Re: Nobel Prize Application - Phillips Theory I regret to inform you that this is a derivative of my cube, whose vertices in Cartesian 3-space have the coordinates: (k,k,k) (k,k,-k) (k,-k,k) (k,-k,-k) (-k,k,k) (-k,k,-k) (-k,-k,k) (-k,-k,-k) where $0 and for which I have already been awarded the Fields Medal. As we speak, I am struggling to do the same for the hypercube. I suspect it will have 16 vertices, but the mathematics involved is nearly intractable.
 April 17th, 2012, 09:44 PM #3 Global Moderator     Joined: Nov 2006 From: UTC -5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms Re: Nobel Prize Application - Phillips Theory So many things are wrong with the original post that I conclude that it must be a troll.
 April 17th, 2012, 09:53 PM #4 Senior Member     Joined: Jul 2010 From: St. Augustine, FL., U.S.A.'s oldest city Posts: 12,211 Thanks: 521 Math Focus: Calculus/ODEs Re: Nobel Prize Application - Phillips Theory I was a bit amused, so I played along.
April 18th, 2012, 04:49 AM   #5
Global Moderator

Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: Nobel Prize Application - Phillips Theory

Quote:
 Originally Posted by MarkFL I was a bit amused, so I played along.
Oh, I could tell.

 April 18th, 2012, 04:56 AM #6 Senior Member   Joined: Jan 2010 Posts: 324 Thanks: 0 Re: Nobel Prize Application - Phillips Theory Can I apply for a Nobel Prize in mathematics (to which there isn't one) too? Because my 'mathemagic' work on my tests should give me an award of some kind.
 April 18th, 2012, 06:46 PM #7 Newbie   Joined: Apr 2012 Posts: 2 Thanks: 0 Re: Nobel Prize Application - Phillips Theory I'm so worthy of said nobel prize, and flights to Monte Carlo, that you all can't comprehend my amazing theory. I deserve said nobel prize for my theory, and my cool hat. The nobel prize is MINE!
April 18th, 2012, 06:52 PM   #8
Senior Member

Joined: Jul 2010
From: St. Augustine, FL., U.S.A.'s oldest city

Posts: 12,211
Thanks: 521

Math Focus: Calculus/ODEs
Re: Nobel Prize Application - Phillips Theory

Attached Images

 Tags application, nobel, phillips, prize, theory

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post BenFRayfield Math Events 1 June 17th, 2013 01:56 PM wuzhe New Users 3 November 2nd, 2011 12:04 PM cohiba25 Elementary Math 3 September 5th, 2010 08:56 PM Marcel777 Computer Science 1 July 6th, 2010 01:28 PM PHILLIPSTHEORY Calculus 1 December 31st, 1969 04:00 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top


text:
# An algebra problem by Rocco Dalto

Algebra Level pending

Let $$f: \mathbb R^2 \rightarrow \mathbb R^3$$ be linear transform defined by:

$f \left( \begin{array}{ccc} x_{1} \\ x_{2} \\ \end{array} \right) = \left( \begin{array}{ccc} 3 x_{1} - x_{2}\\ x_{2} \\ x_{1} + x_{2} \end{array} \right)$

and $A = \{ \left( \begin{array}{ccc} -1 \\ 1 \\ \end{array} \right), \left( \begin{array}{ccc} 2 \\ 1 \\ \end{array} \right) \}$ be basis for $$\mathbb R^2$$ and $B = \left \{ \left( \begin{array}{ccc} 1 \\ -1 \\ 1 \\ \end{array} \right), \left( \begin{array}{ccc} -1 \\ 1 \\ 1 \ \end{array} \right), \left( \begin{array}{ccc} 1 \\ 0 \\ 1 \ \end{array} \right) \right \}$ be a basis for $$\mathbb R^3.$$.

Find a matrix representation for the linear transform above.

If $$\: \textbf{X} = \left( \begin{array}{ccc} 1 \\ 2 \\ \end{array} \right) \in \mathbb R^2$$ and $$\textbf{[f(X)]}_{\textbf{B}} = \left( \begin{array}{ccc} \lambda_1 \\ \lambda_2 \\ \lambda_3 \ \end{array} \right)$$,

Find: $$\lambda_1 + \lambda_2 + \lambda_3$$.

Note: Of course you can find $$\textbf{[f(X)]}_{\textbf{B}} = \left( \begin{array}{ccc} \lambda_1 \\ \lambda_2 \\ \lambda_3 \ \end{array} \right)$$ without finding the matrix, but my intention was to find the matrix.

×


text:
## Zeta Functions of Finite Graphs

J. Math. Sci. Univ. Tokyo
Vol. 7 (2000), No. 1, Page 7--25.

Poles of the {\it Ihara zeta function} associated with a finite graph are described by graph-theoretic quantities. Elementary proofs based on the notions of {\it oriented line graphs}, {\it Perron-Frobenius operators}, and {\it discrete Laplacians} are provided for Bass's theorem on the determinant expression of the zeta function and Hashimoto's theorems on the pole at $u=1$.


text:
# Welcome to Rubi, the Rule-based Integrator

By systematically applying its extensive, coherent collection of symbolic integration rules, Rubi is able to find the optimal antiderivative of large classes of mathematical expressions. Also Rubi can show the rules and intermediate steps it uses to integrate an expression, making the system a great tool for both learning and doing mathematics.

The over 6700 rules Rubi uses are organized as a decision tree based on the form of the integrand. Click on Rules to view the mathematical formula and application conditions for each rule expressed in standard 2-D mathematical notation.

If the Mathematica computer algebra system is available on your computer, click on Install Rubi for instructions how to download and install the system. Then click on Using Rubi to learn how to integrate expressions and optionally show the steps required to do so.

An extensive test-suite of over 72,000 integration problems is used to test each new release of Rubi. Since it can also be used to test other symbolic integrators, the test-suite has been translated into the syntax of several popular computer algebra systems. Click on Test Problem to download the available translations of the test-suite. Click on Test Results to view the very illuminating results of running the test-suite on Rubi and on Mathematica’s and Maple’s built-in integrators.

Click on Vision to read a short, plain-language essay describing the numerous advantages of organizing mathematical knowledge as a rule-based decision tree like Rubi does. Finally, click on About to read about Rubi’s development and developers.

## Comparison with other symbolic integrators

Rubi dramatically out-performs other symbolic integrators, including Maple and Mathematica, on a grueling test-suite of integration problems. Each problem consists of an integrand and its optimal antiderivative. For each problem the result produced by a system is given a grade as follows:

• A - if the result is no more than twice the size of the optimal antiderivative and involves functions no higher-level than those in the optimal antiderivative.
• B - if the result is more than twice the size of the optimal antiderivative.
• C - if the result unnecessarily involves higher-level functions or complex numbers. For example, the result involves special functions, but the optimal antiderivative only involves elementary ones.
• F - if the result involves an integral, no result is produced within 120 seconds, or the system hangs or crashes.

Click on the Test Results menu option to see the detailed test results on which this bar chart is based.

Also, Nasser M. Abbasi has done extensive testing of the integration capabilities on these and several other computer algebra systems. Detailed test results are available at his Computer algebra independent integration tests website.

## Articles referencing rule-based integration

Below are some of the articles and online posts written about Rubi in reverse chronological order:

If Rubi is used in your work and you want to cite it appropriately, please reference the article Rule-based integration: An extensive system of symbolic integration rules published in the Journal of Open Source Software. The following entry can be used for bibliographies created using BibTeX:

@article{Rich2018,
title = {Rule-based integration: An extensive system of symbolic integration rules},
author = {Albert Rich and Patrick Scheibe and Nasser Abbasi},
doi = {10.21105/joss.01073},
date  = {2018-12},
publisher = {The Open Journal},
volume = {3},
number = {32},
pages = {1073},
journal = {Journal of Open Source Software}
}


text:
Last Activity:
Apr 21, 2019 at 2:24 AM
Joined:
Feb 10, 2007
Messages:
1,224
104

# pwood66889

Well-Known Member, from Sopchoppy, Florida, USA

pwood66889 was last seen:
Apr 21, 2019 at 2:24 AM
1. agpilot
Percy, Im in Maggie Valley, NC AND SHOULD BE BACK IN Bainbridge late tomorrow
YES IT HANGERED at Decatur,Co. Airport.Jerry
2. Bill-Higdon
I talked with someone several years ago who built a Bobcat & he said the Struts on the Super Cat were needed in his opinion. I'm doing good, my daughter that was living with me got a job she did a "Car move back to Socorro. Now I need to sort things out & pile her stuff in a corner so I have my work/play room back. I have to use 3 weeks worth of vacation at the end of the year or I loose it but it's not all in a 3 week chunk, I'm off the first 2 weeks, work a week then off until 7th of Jan
3. Bill-Higdon
Percy,
It's close, but I can't afford it Bobcat Ultralight Aircraft
Bill IN Lame Salem
4. GlassVampire
I could fly commercial into DHN. I wouldn't need much baggage. I'm camping as well but all I'll have is a small rucksack w/ a small hiking tent and small sleeping bag. I was in the Marines from 2003 till 2008, so I know how to pack light and tight
My dad was also in the Air Force up at Malmstrom untill a few years ago. Retired as a MSgt in the security forces. Glasgow, as I'm sure you probably already know, was shut down awhile back, but is used now I think by Boeing, or a subsiderary of Boeing, for flight tests or some such thing. If you want to know some more about your old base check out this interesting link, Abandoned & Little-Known Airfields: Eastern MontanaGlasgow is about 3/4 down the page.

What days would you plan on being there? Also, how much do you think I should bring to help out with fuel if we do decide to do this?
5. GlassVampire
Hey Percy, if you have the room I'd love to meet you there in bama and fly in with ya. I'll pay my fair share of the gas.

Maybe? Please? LOL BTW I'm a student pilot :)

http://www.eaachapter1193.org
Location:
Sopchoppy, Florida, USA
Current / Future projects:
Purchased an Ercoupe in 2010 and flew it back to Bama in July.
Ercoupe being restored in Terrell, TX, 2015 ---
Have LePelican carcus that will get go Florida to work on.
Past Projects:
Owned an Ercoupe for 10 years and kept that up.
Replaced first coupe and working on that.
Working on LePelican, and friend invited to help with a Weedhopper.
B. Sci., Computer Science 1969. First career was computers.
PPASEL in Nov., 1976, currently operating under Sport Pilot.
Completed A&P school Dec., 2008.
Cert'd Jan., 2009. Got an A&P job Apr., 2009!
Retired May 31, 2018.

Just bumming around in a plane = short cross country; half hour to a couple hours per leg.

Content:


text:
# Sum rule in quantum mechanics

In quantum mechanics, a sum rule is a formula for transitions between energy levels, in which the sum of the transition strengths is expressed in a simple form. Sum rules are used to describe the properties of many physical systems, including solids, atoms, atomic nuclei, and nuclear constituents such as protons and neutrons.

The sum rules are derived from general principles, and are useful in situations where the behavior of individual energy levels is too complex to be described by a precise quantum-mechanical theory. In general, sum rules are derived by using Heisenberg's quantum-mechanical algebra to construct operator equalities, which are then applied to the particles or energy levels of a system.

## Derivation of sum rules[1]

Assume that the Hamiltonian ${\displaystyle {\hat {H}}}$ has a complete set of eigenfunctions ${\displaystyle |n\rangle }$ with eigenvalues ${\displaystyle E_{n}}$:

${\displaystyle {\hat {H}}|n\rangle =E_{n}|n\rangle .}$

For the Hermitian operator ${\displaystyle {\hat {A}}}$ we define the repeated commutator ${\displaystyle {\hat {C}}^{(k)}}$ iteratively by:

{\displaystyle {\begin{aligned}{\hat {C}}^{(0)}&\equiv {\hat {A}}\\{\hat {C}}^{(1)}&\equiv [{\hat {H}},{\hat {A}}]={\hat {H}}{\hat {A}}-{\hat {A}}{\hat {H}}\\{\hat {C}}^{(k)}&\equiv [{\hat {H}},{\hat {C}}^{(k-1)}],\ \ \ k=1,2,\ldots \end{aligned}}}

The operator ${\displaystyle {\hat {C}}^{(0)}}$ is Hermitian since ${\displaystyle {\hat {A}}}$ is defined to be Hermitian. The operator ${\displaystyle {\hat {C}}^{(1)}}$ is anti-Hermitian:

${\displaystyle \left({\hat {C}}^{(1)}\right)^{\dagger }=({\hat {H}}{\hat {A}})^{\dagger }-({\hat {A}}{\hat {H}})^{\dagger }={\hat {A}}{\hat {H}}-{\hat {H}}{\hat {A}}=-{\hat {C}}^{(1)}.}$

By induction one finds:

${\displaystyle \left({\hat {C}}^{(k)}\right)^{\dagger }=(-1)^{k}{\hat {C}}^{(k)}}$

and also

${\displaystyle \langle m|{\hat {C}}^{(k)}|n\rangle =(E_{m}-E_{n})^{k}\langle m|{\hat {A}}|n\rangle .}$

For a Hermitian operator we have

${\displaystyle |\langle m|{\hat {A}}|n\rangle |^{2}=\langle m|{\hat {A}}|n\rangle \langle m|{\hat {A}}|n\rangle ^{\ast }=\langle m|{\hat {A}}|n\rangle \langle n|{\hat {A}}|m\rangle .}$

Using this relation we derive:

{\displaystyle {\begin{aligned}\langle m|[{\hat {A}},{\hat {C}}^{(k)}]|m\rangle &=\langle m|{\hat {A}}{\hat {C}}^{(k)}|m\rangle -\langle m|{\hat {C}}^{(k)}{\hat {A}}|m\rangle \\&=\sum _{n}\langle m|{\hat {A}}|n\rangle \langle n|{\hat {C}}^{(k)}|m\rangle -\langle m|{\hat {C}}^{(k)}|n\rangle \langle n|{\hat {A}}|m\rangle \\&=\sum _{n}\langle m|{\hat {A}}|n\rangle \langle n|{\hat {A}}|m\rangle (E_{n}-E_{m})^{k}-(E_{m}-E_{n})^{k}\langle m|{\hat {A}}|n\rangle \langle n|{\hat {A}}|m\rangle \\&=\sum _{n}(1-(-1)^{k})(E_{n}-E_{m})^{k}|\langle m|{\hat {A}}|n\rangle |^{2}.\end{aligned}}}

The result can be written as

${\displaystyle \langle m|[{\hat {A}},{\hat {C}}^{(k)}]|m\rangle ={\begin{cases}0,&{\mbox{if }}k{\mbox{ is even}}\\2\sum _{n}(E_{n}-E_{m})^{k}|\langle m|{\hat {A}}|n\rangle |^{2},&{\mbox{if }}k{\mbox{ is odd}}.\end{cases}}}$

For ${\displaystyle k=1}$ this gives:

${\displaystyle \langle m|[{\hat {A}},[{\hat {H}},{\hat {A}}]]|m\rangle =2\sum _{n}(E_{n}-E_{m})|\langle m|{\hat {A}}|n\rangle |^{2}.}$

## References

1. ^ Sanwu Wang, Generalization of the Thomas-Reiche-Kuhn and the Bethe sum rules, Physical Review A 60, 262 (1999). http://prola.aps.org/abstract/PRA/v60/i1/p262_1


text:
# Asymptotics of accessibility sets along an abnormal trajectory

Abstract : We describe precisely, under generic conditions, the contact of the accessibility set at time $T$ with an abnormal direction, first for a single-input affine control system with constraint on the control, and then as an application for a sub-Riemannian system of rank 2. As a consequence we obtain in sub-Riemannian geometry a new splitting-up of the sphere near an abnormal minimizer $\gamma$ into two sectors, bordered by the first Pontryagin's cone along $\gamma$, called the $\xLinfty$-sector and the $\xLtwo$-sector. Moreover we find again necessary and sufficient conditions of optimality of an abnormal trajectory for such systems, for any optimization problem.
Keywords :
Document type :
Journal articles

Cited literature [25 references]

https://hal.archives-ouvertes.fr/hal-00086290
Contributor : Emmanuel Trélat <>
Submitted on : Tuesday, July 18, 2006 - 2:05:32 PM
Last modification on : Friday, June 8, 2018 - 2:50:07 PM
Long-term archiving on : Tuesday, April 6, 2010 - 12:13:50 AM

### Citation

Emmanuel Trélat. Asymptotics of accessibility sets along an abnormal trajectory. ESAIM: Control, Optimisation and Calculus of Variations, EDP Sciences, 2001, 6, pp.387--414. ⟨hal-00086290⟩

Record views


text:
Question

# A particle which has zero rest mass and non-zero energy and momentum must travel with a speed

Open in App
Solution

## Step 1. Given data:Rest mass $\left({m}_{0}\right)=$0Let $v=$ speed of the particle; $c=$ speed of light; $m=$ mass of the particle when it is moving Step 2. Formula used:As we know that the mass of a moving particle is given by the following formula,$m=\frac{{m}_{0}}{\sqrt{1-\frac{{v}^{2}}{{c}^{2}}}}$, where all the variables are described above.Step 3. Explanation:Since it is given that the rest mass of the particle is zero, so ${m}_{0}=0$. Putting the value of ${m}_{0}$ in equation, we get$⇒\sqrt{1-\frac{{v}^{2}}{{c}^{2}}}=0$, squaring both sides, we get$1-\frac{{v}^{2}}{{c}^{2}}=0\phantom{\rule{0ex}{0ex}}or\frac{{v}^{2}}{{c}^{2}}=1\phantom{\rule{0ex}{0ex}}⇒v=c$It shows that the speed of the particle is equal to the speed of light.Particle is a photon and it travels with a velocity equal to light in vacuum.Hence, a particle that has zero rest mass and non-zero energy and momentum must travel with a speed equal to the speed of light.

Suggest Corrections
2


text:
# How do you express the phrase "the product of 15 and c" as an algebraic expression?

Apr 10, 2018

$15 c$

#### Explanation:

Product indicates multiplication

Product of (number) and (other number) indicates that the two numbers are being multiplied

$15 \cdot c = 15 c$


text:
# Superpolynomial

This post is just to help a friend that wanted to see why

$\displaystyle \sum_{i=1}^{\lfloor\sqrt{n}\rfloor} \binom{n}{i}$

was superpolynomial.

### Getting a simple lower bound

We can start by keeping only the last term. As all the terms are positive, that will give us a lower bound:

$\displaystyle \sum_{i=1}^{\lfloor\sqrt{n}\rfloor} \binom{n}{i} \ge \binom{n}{\lfloor\sqrt{n}\rfloor}$.

We can expand the binomial coefficient in terms of factorials

$\displaystyle \binom{n}{\lfloor\sqrt{n}\rfloor} = \frac{n!}{(n - \lfloor\sqrt{n}\rfloor)!\lfloor\sqrt{n}\rfloor!}$,

and some of the factors inside $n!$ can then be cancelled with the ones in $(n - \lfloor\sqrt{n}\rfloor)!$, leaving the following expression:

$\displaystyle \binom{n}{\lfloor\sqrt{n}\rfloor} = \frac{n(n-1)\hdots(n - \lfloor\sqrt{n}\rfloor + 1)}{\lfloor\sqrt{n}\rfloor!}$.

As we want a lower bound, we can bound the numerator by below and the denominator by above, leaving us a bound without factorials:

$\displaystyle \frac{n(n-1)\hdots(n - \lfloor\sqrt{n}\rfloor + 1)}{\lfloor\sqrt{n}\rfloor!} \ge \frac{(n - \sqrt{n})^{\sqrt{n} - 1}}{\sqrt{n}^{\sqrt{n}}}$.

For any reasonably big value of $n$ we will have $n - \lfloor\sqrt{n}\rfloor \ge n/2$. If we combine that with factoring out the -1 in the exponent we get

$\displaystyle \frac{(n - \sqrt{n})^{\sqrt{n} - 1}}{\sqrt{n}^{\sqrt{n}}} \ge \frac{1}{n - \sqrt{n}}\left(\frac{n}{\sqrt{n}}\right)^{\sqrt{n}} \ge \frac{1}{n}\sqrt{n}^{\sqrt{n}}$,

removing the problematic floors and arriving to a much simpler expression.

Combining all these bounds we get

$\displaystyle \sum_{i=1}^{\lfloor\sqrt{n}\rfloor} \binom{n}{i} \ge \frac{1}{n}\sqrt{n}^{\sqrt{n}}$,

a much simpler lower bound when compared to the original expression.

### Proving it is superpolynomial

If w take an arbitrary polynomial $p(n)$ of degree $k$ we can say for $n \ge 1$ that

$\displaystyle p(n) = \sum_{i=1}^k p_i\,n^i \le \left(\sum_{i=1}^k |p_i|\right)n^k$,

meaning we can bound by above any polynomial of degree $k$ by a polynomial of the same degree with a single term.

Taking the limit of the quotient of logarithms,

$\displaystyle \lim_{x \to +\infty} \frac{\log \frac{1}{n}\sqrt{n}^{\sqrt{n}}}{\log a\,n^k} = \lim_{x \to +\infty} \frac{\frac{\sqrt{n}}{2}\log n - \log n}{\log a + k\,\log n}$

$\displaystyle = \lim_{x \to +\infty} \frac{\log n\left(\frac{\sqrt{n}}{2} - 1\right)}{\log n\left(\frac{\log a}{\log n} + k\right)}$

$\displaystyle = \lim_{x \to +\infty} \frac{\frac{\sqrt{n}}{2} - 1}{\frac{\log a}{\log n} + k}$

$\displaystyle = +\infty$

we can see the lower bound of the original expression is superpolynomial, making the original expression superpolynomial too.


text:
# zbMATH — the first resource for mathematics

On the structure of linear graphs. (English) Zbl 0063.01277
Introduction: If the numbers of vertices and edges of a (linear) graph are suitably restricted, it is to be expected that something can be said about the configurations which the graph contains. As far as we know the first result in this direction is due to P. Turán [Mat. Fiz. Lapok 48, 436–452 (1941; Zbl 0026.26903, JFM 67.0732.03)]. He proved that a graph with $$kn$$ vertices and $$C_{k,2}n^2+1$$ edges always contains a complete graph of order $$k+1$$. We shall here prove one such theorem (which arose originally out of a topological problem) [A. H. Stone, Connectedness and coherence. Thesis (Ph.D.) Princeton University. (1941)], and then list (without proofs) several other theorems and conjectures of this nature.

##### MSC:
 05C75 Structural characterization of families of graphs
Full Text: