text:
# Compounding english

A compound word is a word that contains 2 or more words in it. We can do better than that, though. We need you to create 1 (nonsensical) word that contains every word.

However, we want this word to be as short as possible. We can use overlapping letters to achieve this.

For example, if your word list was ["cat", "atom", "a"], you would want to return "catom".

# Input/Output

Your program will need to take a list of words as input, and return a compound word as output.

The word list you will be using is the top 10000 words in English, according to Google (If this list turns out to be too easy, I may change it to a longer one). For reference, simply appending each word gives you a score of 65888.

Your score is the number of letters in your final word, lower is better. Tie breaker goes to the first poster.

• – Martin Ender Aug 1 '16 at 18:35
• @Loovjo no, but if it ends up that bruteforcing is fast enough to run, then I'll change the word list to make it longer. – Nathan Merrill Aug 1 '16 at 18:41
• @PatrickRoberts If it fits in your answer, props to you :) A pastebin/gist link would be great, but isn't required. – Nathan Merrill Aug 1 '16 at 19:28
• Hmm, who knows a good asymmetric travelling salesman heuristic? – Dave Aug 1 '16 at 20:48
• No wrapping, and yes to deterministic. – Nathan Merrill Aug 1 '16 at 22:14

# C++, final word length: 38272

(optimised version took about 20 minutes)

#include <iostream>
#include <string>
#include <vector>

std::size_t calcOverlap(const std::string &a, const std::string &b, std::size_t limit, std::size_t minimal) {
std::size_t la = a.size();
for(std::size_t p = std::min(std::min(la, b.size()), limit + 1); -- p > minimal; ) {
if(a.compare(la - p, p, b, 0, p) == 0) {
return p;
}
}
return 0;
}

int main() {
std::vector<std::string> words;

// Load all words from input
while(true) {
std::string word;
std::getline(std::cin, word);
if(word.empty()) {
break;
}
words.push_back(word);
}

std::cerr
<< "Input word count: " << words.size() << std::endl;

// Remove all fully subsumed words

for(auto p = words.begin(); p != words.end(); ) {
bool subsumed = false;
for(auto i = words.begin(); i != words.end(); ++ i) {
if(i == p) {
continue;
}
if(i->find(*p) != std::string::npos) {
subsumed = true;
break;
}
}
if(subsumed) {
p = words.erase(p);
} else {
++ p;
}
}

std::cerr
<< "After subsuming checks: " << words.size()
<< std::endl;

// Sort words longest-to-shortest (not necessary but doesn't hurt. Makes finding maxlen a tiny bit easier)
std::sort(words.begin(), words.end(), [](const std::string &a, const std::string &b) {
return a.size() > b.size();
});

std::size_t maxlen = words.front().size();

// Repeatedly combine most-compatible words until there is only one left
std::size_t bestPossible = maxlen - 1;
while(words.size() > 1) {
auto bestA = words.begin();
auto bestB = -- words.end();
std::size_t bestOverlap = 0;
for(auto p = ++ words.begin(), e = words.end(); p != e; ++ p) {
if(p->size() - 1 <= bestOverlap) {
continue;
}
for(auto q = words.begin(); q != p; ++ q) {
std::size_t overlap = calcOverlap(*p, *q, bestPossible, bestOverlap);
if(overlap > bestOverlap) {
bestA = p;
bestB = q;
bestOverlap = overlap;
}
overlap = calcOverlap(*q, *p, bestPossible, bestOverlap);
if(overlap > bestOverlap) {
bestA = q;
bestB = p;
bestOverlap = overlap;
}
}
if(bestOverlap == bestPossible) {
break;
}
}
std::string newStr = std::move(*bestA);
newStr.append(*bestB, bestOverlap, std::string::npos);

if(bestA == -- words.end()) {
words.pop_back();
*bestB = std::move(words.back());
words.pop_back();
} else {
*bestB = std::move(words.back());
words.pop_back();
*bestA = std::move(words.back());
words.pop_back();
}

// Remove any words which are now in the result
for(auto p = words.begin(); p != words.end(); ) {
if(newStr.find(*p) != std::string::npos) {
std::cerr << "Now subsumes: " << *p << std::endl;
p = words.erase(p);
} else {
++ p;
}
}

std::cerr
<< "Words remaining: " << (words.size() + 1)
<< " Latest combination: (" << bestOverlap << ") " << newStr
<< std::endl;

words.push_back(std::move(newStr));
bestPossible = bestOverlap; // Merging existing words will never make longer merges possible
}

std::string result = words.front();

std::cout
<< result
<< std::endl;
std::cerr
<< "Word size: " << result.size()
<< std::endl;
return 0;
}

Verification bash one-liner:

cat commonwords.txt | while read p; do grep "$p" merged.txt >/dev/null || echo "Not found:$p"; done

It also produced some pretty cool in-progress words. Here are some of my favourites:

• polyesterday (synthetic nostalgia)
• afghanistanbul (something [insert politician you dislike] would say)
• togethernet (the friendly internet)
• elephantom (a large ghost)
• thundergroundwaterproof (as in "I don't know why they felt the need to make it thundergroundwaterproof, but it's making me nervous")

And:

• codescribingo (maybe an upcoming challenge on this site?)

The final output is on pastebin here: http://pastebin.com/j3qYb65b

• An observation which might be useful to others looking to get the optimal solution: the problem can be reduced to a non-euclidean, asymmetric travelling salesman problem: define a matrix where element i, j = max_word_length - overlap(word[i], word[j]) (where overlap checks the overlap from the right of the first argument to the left of the second). Solving this (good luck!) then cutting the resulting loop at the highest cost (lowest overlap) will give an ordered list of words which can be merged to give an optimal solution. – Dave Aug 1 '16 at 22:53
• Impressive. Is this checking every word in the current list against every other, each time through? I was considering this but assumed I'd need to just check a random sample to make it run in a reasonable time. – trichoplax Aug 2 '16 at 1:08
• @ValueInk yes caching would be a big performance boost. An earlier version had that, but it adds a lot of complexity, so when I adapted some logic I had to re-write the lot. Instead I chose to drop caching. Also no, this isn't completely optimal. It's a greedy algorithm so it can't judge trade-offs, and it's unable to choose between "equally good" options. See my TSP comment for the (NP-Hard) optimal solution. – Dave Aug 2 '16 at 6:53
• @trichoplax yup, that's what it's doing. Running time is O(n^3), which isn't so bad for this sample size. With caching it could be reduced to O(n^2). The inner check is also very parallel-isable, so even for larger samples it could run in reasonable time with threading / distributed computation. Also this gets a big speed boost from knowing the range of possible overlap widths for each step, which cut the runtime by a factor of 10. – Dave Aug 2 '16 at 7:02
• This might not be as hard as general TSP, because we have the funny constraint that overlap(a, b) ≥ min{overlap(a, d), overlap(c, d), overlap(c, b)} for all a, b, c, d. – Anders Kaseorg Aug 2 '16 at 11:20

# C++11, 38272 letters, proven optimal

This algorithm is guaranteed to provide a lower bound on the solution. In this case, it is able to achieve the lower bound and output an optimal 38272 letter solution. (This matches the solution found by Dave’s greedy algorithm. I was surprised and a little disappointed to discover that it’s optimal, but, there we are.)

It works by solving the minimum-cost flow problem on the network built as follows.

• First, any words contained in other words are redundant; discard them.
• For every word w, draw two nodes w_0 and w_1, where w_0 is a source with capacity 1 and w_1 is a sink with capacity 1.
• For every (strict) prefix or suffix a of any word, draw a node a.
• For every suffix a of w, draw an arc from w_0 to a with capacity 1 and cost 0.
• For every prefix a of w, draw an arc from a to w_1 with capacity 1 and cost length(w) − length(a).

Any string of length n that contains every word can be converted into a flow on this network with cost at most n. Therefore, the minimum cost flow on this network is a lower bound on the length of the shortest such string.

If we’re lucky—and in this case we are—then after we redirect the flow coming into w_1 back out of w_0, we will find an optimal flow that has just one connected component and that passes through the node for the empty string. If so, it will contain an Eulerian circuit starting and ending there. Such an Eulerian circuit can be read back out as a string of optimal length.

If we weren’t lucky, add some extra arcs between the empty string and the shortest strings in the other connected components in order to ensure that an Eulerian circuit exists. The string would no longer necessarily be optimal in that case.

I use the LEMON library for its min-cost flow and Eulerian circuit algorithms. (This was my first time using this library, and I was impressed—I will definitely use it again for future graph algorithm needs.) LEMON comes with four different minimum-cost flow algorithms; you can try them here with --net, --cost, --cap, and --cycle (default).

The program runs in 0.5 seconds, producing this output string.

#include <iostream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <lemon/core.h>
#include <lemon/connectivity.h>
#include <lemon/euler.h>
#include <lemon/maps.h>
#include <lemon/list_graph.h>
#include <lemon/network_simplex.h>
#include <lemon/cost_scaling.h>
#include <lemon/capacity_scaling.h>
#include <lemon/cycle_canceling.h>

using namespace std;

typedef lemon::ListDigraph G;

struct Word {
G::Node suffix, prefix;
G::Node tour_node;
};

struct Edge {
unordered_map<string, Word>::iterator w;
G::Arc arc;
};

struct Affix {
vector<Edge> suffix, prefix;
G::Node node;
G::Node tour_node;
};

template<class MCF>
bool solve(const G &net, const G::ArcMap<int> &lowerMap, const G::ArcMap<int> &upperMap, const G::ArcMap<int> &costMap, const G::NodeMap<int> &supplyMap, int &totalCost, G::ArcMap<int> &flowMap)
{
MCF mcf(net);
if (mcf.lowerMap(lowerMap).upperMap(upperMap).costMap(costMap).supplyMap(supplyMap).run() != mcf.OPTIMAL)
return false;
totalCost = mcf.totalCost();
mcf.flowMap(flowMap);
return true;
}

int main(int argc, char **argv)
{
clog << "Reading dictionary from stdin" << endl;
unordered_map<string, Affix> affixes;
unordered_map<string, Word> words;
unordered_set<string> subwords;
G net, tour;
G::ArcMap<int> lowerMap(net), upperMap(net), costMap(net);
G::NodeMap<int> supplyMap(net);
string new_word;
while (getline(cin, new_word)) {
if (subwords.find(new_word) != subwords.end())
continue;
for (auto i = new_word.begin(); i != new_word.end(); ++i) {
for (auto j = new_word.end(); j != i; --j) {
string s(i, j);
words.erase(s);
subwords.insert(s);
}
}
words.emplace(new_word, Word());
}
for (auto w = words.begin(); w != words.end(); ++w) {
supplyMap.set(w->second.suffix, 1);
supplyMap.set(w->second.prefix, -1);
for (auto i = w->first.begin(); ; ++i) {
affixes.emplace(string(w->first.begin(), i), Affix()).first->second.prefix.push_back(Edge {w});
affixes.emplace(string(i, w->first.end()), Affix()).first->second.suffix.push_back(Edge {w});
if (i == w->first.end())
break;
}
}
for (auto a = affixes.begin(); a != affixes.end();) {
if (a->second.suffix.empty() || a->second.prefix.empty() ||
(a->second.suffix.size() == 1 && a->second.prefix.size() == 1 &&
a->second.suffix.begin()->w == a->second.prefix.begin()->w)) {
affixes.erase(a++);
} else {
supplyMap.set(a->second.node, 0);
for (auto &e : a->second.suffix) {
lowerMap.set(e.arc, 0);
upperMap.set(e.arc, 1);
costMap.set(e.arc, 0);
}
for (auto &e : a->second.prefix) {
lowerMap.set(e.arc, 0);
upperMap.set(e.arc, 1);
costMap.set(e.arc, e.w->first.length() - a->first.length());
}
a->second.tour_node = lemon::INVALID;
++a;
}
}

clog << "Read " << words.size() << " words and found " << affixes.size() << " affixes; ";
clog << "created network with " << countNodes(net) << " nodes and " << countArcs(net) << " arcs" << endl;

int totalCost;
G::ArcMap<int> flowMap(net);
bool solved;
if (argc > 1 && string(argv[1]) == "--net") {
clog << "Using network simplex algorithm" << endl;
solved = solve<lemon::NetworkSimplex<G>>(net, lowerMap, upperMap, costMap, supplyMap, totalCost, flowMap);
} else if (argc > 1 && string(argv[1]) == "--cost") {
clog << "Using cost scaling algorithm" << endl;
solved = solve<lemon::CostScaling<G>>(net, lowerMap, upperMap, costMap, supplyMap, totalCost, flowMap);
} else if (argc > 1 && string(argv[1]) == "--cap") {
clog << "Using capacity scaling algorithm" << endl;
solved = solve<lemon::CapacityScaling<G>>(net, lowerMap, upperMap, costMap, supplyMap, totalCost, flowMap);
} else if ((argc > 1 && string(argv[1]) == "--cycle") || true) {
clog << "Using cycle canceling algorithm" << endl;
solved = solve<lemon::CycleCanceling<G>>(net, lowerMap, upperMap, costMap, supplyMap, totalCost, flowMap);
}

if (!solved) {
clog << "error: no solution found" << endl;
return 1;
}
clog << "Lower bound: " << totalCost << endl;

G::ArcMap<string> arcLabel(tour);
affixes.find("")->second.tour_node = empty;
for (auto &a : affixes) {
for (auto &e : a.second.suffix) {
if (flowMap[e.arc]) {
if (a.second.tour_node == lemon::INVALID)
}
}
for (auto &e : a.second.prefix) {
if (flowMap[e.arc]) {
if (a.second.tour_node == lemon::INVALID)
}
}
}

clog << "Created tour graph with " << countNodes(tour) << " nodes and " << countArcs(tour) << " arcs" << endl;

G::NodeMap<int> compMap(tour);
int components = lemon::stronglyConnectedComponents(tour, compMap);
if (components != 1) {
vector<unordered_map<string, Affix>::iterator> breaks(components, affixes.end());
for (auto a = affixes.begin(); a != affixes.end(); ++a) {
if (a->second.tour_node == lemon::INVALID)
continue;
int c = compMap[a->second.tour_node];
if (c == compMap[empty])
continue;
auto &b = breaks[compMap[a->second.tour_node]];
if (b == affixes.end() || b->first.length() > a->first.length())
b = a;
}
int offset = 0;
for (auto &b : breaks) {
if (b != affixes.end()) {
offset += b->first.length();
}
}
clog << "warning: Found " << components << " components; solution may be suboptimal by up to " << offset << " letters" << endl;
}

if (!lemon::eulerian(tour)) {
clog << "error: failed to make tour graph Eulerian" << endl;
return 1;
}

for (lemon::DiEulerIt<G> e(tour, empty); e != lemon::INVALID; ++e)
cout << arcLabel[e];
cout << endl;

return 0;
}

• While I can't claim to understand how min flow works, if this really is optimal, well done! – Nathan Merrill Aug 3 '16 at 12:38
• Sorry to disappoint :P I hadn't thought of a flow network; that's pretty elegant. Took me a while to understand how you were linking the words together in your network before I finally realised "For every (strict) prefix or suffix a of any word, draw a node a" meant that the nodes "a" can be shared between multiple words. – Dave Aug 3 '16 at 17:55
• Also your solution is about 2,000 times faster than mine! – Dave Aug 3 '16 at 17:56
• Maybe help this guy (cs.cmu.edu/~tom7/portmantout) out with his attempt at a similar thing? – Oliver Daugherty-Long Aug 6 '16 at 0:02
• @OliverDaugherty-Long Done! (For real this time.) The best previously known bounds were 520732 ≤ optimal length ≤ 537136, and I believe I have improved both bounds to 536186. – Anders Kaseorg Aug 7 '16 at 10:30

# Java 8, ~5 Minutes, Length of 39,279

import java.io.BufferedReader;
import java.io.File;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Optional;
import java.util.Set;
import java.util.stream.Collectors;

public class Words {

public static void main(String[] args) throws Throwable {
File file = new File("words.txt");
List<String> wordsList = new ArrayList<>();
String line;
}

Set<String> words = new HashSet<>();

System.out.println("Finished I/O");

for (int i = 0; i < wordsList.size(); i++) { //Step 1: remove any words that occur in other words
boolean in = false;
for (int j = 0; j < wordsList.size(); j++) {
if (i != j && wordsList.get(j).contains(wordsList.get(i))) {
in = true;
break;
}
}
if (!in) {
}
}

System.out.println("Removed direct containers");

List<String> working = words.stream().sorted((c, b) -> Integer.compare(c.length(), b.length())).collect(Collectors.toList()); //Sort by length, shortest first
StringBuilder result = new StringBuilder();
result.append(working.get(0));
while (!working.isEmpty()) {
Optional<String> target = working.stream().sorted((c, b) -> Integer.compare(firstLastCommonality(result.toString(), b), firstLastCommonality(result.toString(), c))).findFirst(); //Find the string that has the greatest in common with the end of 'result'
if(target.isPresent()) { //It really should be present, but just in case
String s = target.get();
working.remove(s);
int commonality = firstLastCommonality(result.toString(), s);
s = s.substring(commonality);
result.append(s);
}
}

System.out.println("Finished algorithm");

String r = result.toString();
System.out.println("The string: \n" + r);
System.out.println("Length: \n" + r.length());
System.out.println("Verified: \n" + !wordsList.stream().filter(s -> !r.contains(s)).findFirst().isPresent());
}

private static int firstLastCommonality(String a, String b) {
int count = 0;
int len = b.length();
while (!a.endsWith(b) && !b.equals("")) {
b = cutLastChar(b);
count++;
}
return len - count;
}

private static String cutLastChar(String string) {
if (string.length() - 1 < 0) {
return string;
} else {
return string.substring(0, string.length() - 1);
}
}

}

### Input:

• a file called 'words.txt' in the working directory, in the exact same format as the file in the main post

### Output:

Finished I/O
Removed direct containers
Finished algorithm
The string:
[Moved to pastebin](http://pastebin.com/iygyR3zL)
Length:
39279
Verified:
true

• FGITW, and in Java no less. You sir have my vote. – Patrick Roberts Aug 1 '16 at 19:30
• Nice! You got rid of 26,609 characters. – R. Kap Aug 1 '16 at 20:21
• @R.Kap go figure! I didn't even think to calculate that... There must be a smarter algorithm though, this is just the first thing that came to mind... – Socratic Phoenix Aug 1 '16 at 20:26

# Python 2, 39254 characters

Takes 1-2 minutes to run on my machine, works by taking the longest word and then always adding the word to the result string that has the most strings in common. (Before that all words that are substrings of other words are removed to prevent unnecessary adding to the string.)

Update: Tried to look in both directions, but that doesn't do any better. (maybe it's using words that can be used better later?)

Link to the word on pastebin.

first 100 chars:

telecommunicationsawayneillegallynnbabyenbcjrxltdxmlbsrcwvtxxxboxespnycdsriconsentencessexyrsslipodc

### Code:

import re
import urllib

def suffix_dist(w1,w2):
for i in range(min(map(len,[w1,w2])))[::-1]:
if w1[-i:]==w2[:i]:
return i
return 0

words=s.split()
words.sort(key=len,reverse=True)

## remove words that are substrings of other words anyway
for i in range(len(words))[::-1]:
if any(words[i] in w for w in words[:i]):
words.pop(i)

print len(words)

words.sort(key=len)
w1=words.pop(-1)
result=w1
while words:
## get the word with longest shared suffix/prefix
w2=max(words,key=lambda x:suffix_dist(w1,x))
print w2
words.pop(words.index(w2))
if w2 in result:
break
result+=w2[suffix_dist(w1,w2):]
w1=w2

print result[:100]
print len(result)
print "Test:", all(w in result for w in s.split())

• Welp, I've been beaten by 25 characters... +1 for that – Socratic Phoenix Aug 1 '16 at 20:28
• Nice work! I had a similar idea but you already had an answer up. My version starts with a small word instead of a big word, plus some other pruning that causes it to drastically lose out on the time factor, taking up to 3x the amount of time to run. – Value Ink Aug 2 '16 at 2:15

# Ruby, 39222 characters

Uses a similar approach to @KarlKastor in his Python answer, but the starting string is one of the smallest words instead of the largest. Another optimization (I don't know how much it helps) is that in between each addition, it prunes any words that may have already been included in the string due to overlapping words.

Runs in a little over 4 minutes on my machine, not counting the web request to retrieve the list of words, but not quite 4:20.

The word on Pastebin.

require 'net/http'

puts "Obtaining word list..."
puts "Word list obtained!"

puts "Starting calculation..."
time = Time.now

words = data.split.sort_by(&:size)
words.reject!{|w| words.find{|x| w!=x && x.include?(w)}}

string = words.shift

def merge_dist(prefix, suffix)
[prefix.size,suffix.size].min.downto(0).find{|i| prefix.end_with?(suffix[0,i])}
end

while words.length > 0
suffix = words.max_by{|w| merge_dist string, w}
string += suffix[merge_dist(string, suffix)..-1]
words.reject!{|w| string.include? w}
end

delta = Time.now - time

puts "Calculation completed in #{delta} seconds!"
puts "Word is #{string.size} chars long."

open("word.txt", 'w') << string

puts "Word saved to word.txt"

## PowerShell v2+, 46152 characters

param([System.Collections.ArrayList]$n)$n=$n|sort length -des;while($n){$x=$n.Count;$o+=$n[0];0..$x|%{if($o.IndexOf($n[$_])-ge0){$n.RemoveAt($_)}}}$o  Takes the input as a list, casts it into an ArrayList (so we can manipulate it). We sort it by length in -descending order. Then, while we still have words in our input array, do a loop. Each iteration, set helper $x to be equal to how many we have left, tack on the next item in the list to our output $o, and then trawl through everything still in our list. If the .IndexOf is not equal to -1 (i.e., the word was found somewhere in $o), we remove that word from our list of remaining words. Finally, at the end, output $o. I don't have access to a Pastebin or similar, so here's the beginning and end of the word for temporary -- telecommunicationscharacterizationresponsibilitiessublimedirectory...fcmxvtwvfxwujmjsuhjjrxjdbkdxqc. Which I guess has shaved about 20,000 characters off of the input, so not that bad, I suppose. I'm working on refinements. PHP 46612 characters This is just a start. I hope to improve it. All I've done so far is remove any word that is a sub-string of another word. I'm working on 3 copies of the array, but the memory doesn't seem to be an issue. <?php set_time_limit(3000);$words=file('https://raw.githubusercontent.com/first20hours/google-10000-english/master/google-10000-english.txt');
$words = array_map('trim',$words);

usort($words, function ($a, $b) { if (strlen($a) == strlen($b) ){ return 0; } return ( strlen($a) < strlen($b) )? -1 : 1; });$final_array=$words;$comparison_array=$words; foreach($words as $key =>$word){
echo $word."<br>\n"; foreach($comparison_array as $nestedKey =>$nestedWord){
if (strlen($nestedWord) <= strlen($word)) {
unset($comparison_array[$nestedKey]);
continue;
}
if( strpos($nestedWord,$word) !== FALSE ){
unset($final_array[$key]);
$restart=true; break; } } } sort($final_array);
$compound='';$compound = implode($final_array); echo$compound;
echo "  <br><br>\n\n". strlen(\$compound);


text:
MathSciNet bibliographic data MR1502720 Contributed Item Hartley, R. W. Determination of the ternary collineation groups whose coefficients lie in the ${\rm GF}(2\sp n)$${\rm GF}(2\sp n)$. Ann. of Math. (2) 27 (1925), no. 2, 140–158. Article

For users without a MathSciNet license , Relay Station allows linking from MR numbers in online mathematical literature directly to electronic journals and original articles. Subscribers receive the added value of full MathSciNet reviews.

format: plain


text:
# Wrap text at any point if normal hyphenation not possible

I have data (generated from a database, not manually typed in) that mostly fits into a table cell with fixed width, but sometimes overflows because there are long words for which no hyphenation is found.

The problem can be demonstrated with the following example:

\documentclass{article}
\usepackage[utf8]{inputenc}
\begin{document}
\begin{tabular}{|p{1cm}|p{4cm}|}
1 & Cell where normal hyphenation is possible ÄÖÜ \\
\end{tabular}
\end{document}

My requirements are:

1. Text never overflows the cell (assuming some minimum width such that at least a handful characters have place)
2. First priority measure to achieve 1. is the normal hyphenation
3. If 2. fails, it is allowed to break the word at any character, so fill the line and break just before overflow would happen (disregarding normal hyphenation rules)

In the example, the overflow in cell 1 is prevented by measure 2., the normal hyphenation. The second cell overflows. I would like to have this cell treated by measure 3.

• Package seqsplit didn't help me
• The custom macro \wrap proposed in the answer to seqsplit - keep spaces comes near my wish, but can't handle the non-ascii characters ÄÖÜ (independent if they are input with utf8 input encoding or with \"A\"O\"U)
• As the text comes from a database, no manual editing of the cell content is wanted.

One of my ideas was to insert \linebreak[0] after every character, to tell LaTeX that a break can be made if no better opportunities exist. But this doesn't work like intended.

• I suspect you need to play with the penalties and glue. – John Kormylo Oct 14 '14 at 15:39

You can make a trial setting , see if you have any over large boxes, then if so loop through character by character adding \penalty0 and re-set.

\documentclass{article}
\usepackage[utf8]{inputenc}
\makeatletter
\def\foo#1{%
\setbox0\vbox{%
\global\let\foonext\foohyph
\hfuzz\maxdimen
#1\par
\loop
\unskip\unpenalty\unskip\unpenalty
\setbox\z@\lastbox
\ifvoid\z@
\else
\setbox\z@\hbox{\unhbox\z@}%
\ifdim\wd\z@>\dimexpr\hsize+4pt\relax% compensate for hfuzz and not checking for shrink
\global\let\foonext\foowrap
\fi
\repeat}%
\foonext{#1}%
}
\def\foohyph#1{#1}
\def\foowrap#1{\foowrap@#1\foowrap@}

\def\foowrap@{\futurelet\tmp\foowrap@@}

\def\foowrap@@{%
\let\next\relax
\ifx\tmp\foowrap@
\let\foowrap@\relax
\else\ifx\tmp\lbrace
\else\ifx\tmp\@sptoken
\let\next\foowrap@sp
\else\ifcat\noexpand\tmp\active% only active character utf8 chars
\let\next\foowrap@aa
\else
\let\next\foowrap@a
\fi\fi\fi\fi
\next
}

\def\foowrap@sp{\afterassignment\foowrap@\let\tmp= }

\def\foowrap@a#1{%
\leavevmode\penalty\z@#1\foowrap@}

\def\foowrap@aa#1#2{%
\leavevmode\penalty\z@#1#2%
\foowrap@}

\begin{document}
\begin{tabular}{|p{1cm}|p{4cm}|}
1 & \foo{Cell where normal hyphenation is possible ÄÖÜ}\\
\end{tabular}

\end{document}

This works when just two byte UTF-8 characters are used; testing three byte characters requires a more complex regular expression. Of course, with XeLaTeX or LuaLaTeX a simpler approach would be possible, because single letters would be seen.

\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage{xparse,l3regex}

\newcommand{\breakandspace}{%
\nolinebreak % don't break here
\hspace{0pt plus 1fil}% add a filling space
\linebreak[0]% possible break here
\hspace{0pt plus -1fil}% remove the filling space
}

\ExplSyntaxOn
\NewDocumentCommand{\longcell}{m}
{
\mivt_long_cell:n { #1 }
}

\cs_new_protected:Npn \mivt_long_cell:n #1
{
\tl_set:Nn \l__mivt_cell_text_tl { #1 }
\regex_replace_all:nnN { (\cL.|\cA.{2}) } { \1\c{breakandspace} } \l__mivt_cell_text_tl
\tl_use:N \l__mivt_cell_text_tl
}
\ExplSyntaxOff

\begin{document}
\begin{tabular}{|p{1cm}|p{4cm}|}
1 & Cell where normal hyphenation is possible ÄÖÜ \\

The spaces will cancel with each other if the break is not taken at \linebreak[0]; if the break is taken, the second space will disappear at the left margin.
The regular expression search and replace will add \breakandspace after each letter or each group of two byte UTF-8 characters.


text:
+0

$f(x) = \begin{cases} \frac{a}{b}x & \text{ if }x\le-4, \\ abx^2 & \text{ if }x>-4. \end{cases}$

0
65
2
+105

Suppose that a and b are positive real numbers, and let $$f(x) = \begin{cases} \frac{a}{b}x & \text{ if }x\le-4, \\ abx^2 & \text{ if }x>-4. \end{cases}$$

If $$f(-4)=-\frac{60}{13}$$ and $$f(4)=3120$$, what is $$a+b$$?

Aug 28, 2021

#2
+114875
+1

$$f(-4)=\frac{a}{b}*-4=\frac{-4a}{b}\\ \frac{-4a}{b}=\frac{-60}{13}\\ \frac{4a}{b}=\frac{60}{13}\\ \frac{a}{b}=\frac{15}{13}\\ a=\frac{15b}{13}$$

$$f(4)=ab*4^2=16ab\\ 16ab=3120\\ ab=195\\~\\ so\\ \frac{15b}{13}*b=195\\ \frac{b^2}{13}=13\\ b^2=13^2\\ b=\pm13$$

You can check what I have done and continue from there.

LaTex:

f(-4)=\frac{a}{b}*-4=\frac{-4a}{b}\\
\frac{-4a}{b}=\frac{-60}{13}\\
\frac{4a}{b}=\frac{60}{13}\\
\frac{a}{b}=\frac{15}{13}\\
a=\frac{15b}{13}

Aug 30, 2021


text:
# How can I tell if an object in a tile grid is surrounded?

I'm making a game which uses a 10x20 matrix to store the position of the objects.

I have a castle object, represented by a number in a matrix. It is randomly deployed in some cell of the matrix. I also have a wall object, represented by a different number, which the user will deploy into the matrix by clicking on cells. The idea is to surround the castle.

Basically it'll look like this:

0 0 0 0 0 0 0
0 1 1 1 1 1 0
0 1 0 0 2 1 0
0 1 1 0 0 1 0
0 0 1 0 0 1 0
0 1 1 1 1 1 0
0 0 0 0 0 0 0

(2 is the castle, and 1 is the wall.)

How can I tell if the castle is surrounded by walls?

• Can't you just check the 8 surrounding position of each castle ? – Emadpres Dec 17 '14 at 16:00
• Sadly no, because the player should choose the way they deploy the wall. – Cafn Dec 17 '14 at 16:18
• So you can use a DFS or BFS algorithm easily and check If you reach the border of your matrix or not. – Emadpres Dec 17 '14 at 19:57

Sounds like you're after something like a flood fill algorithm.

Basically, something like the following algorithm (you can see other examples on the wikipedia page):

 1. Add your castle to the Checklist
2. Get the first item from the Checklist
3. For each surrounding position
4. If not on Complete list
5. If 0 add to Checklist
6. If 1 continue
7. Add position to Complete list and remove from Checklist

If at any point you reach an outside boundary, your castle is not surrounded by walls. If you complete your Checklist without touching an outside boundary, your castle is surrounded by walls.

• I'll try this one tonight and give a feedback! Seems to be the easier way! – Cafn Dec 17 '14 at 16:19
• The alternative method you describe (following the walls) detects only whether the walls form a loop - it doesn't verify that the castle is inside that loop. Also, the single-wall-thickness constraint might not be enforceable given that the OP says "the player should choose the way they deploy the wall." The first flood-fill suggestion works just fine though. – DMGregory Dec 17 '14 at 18:52
• @DMGregory You're correct. I tried to think of other ways to traverse the wall while ensuring the castle was inside, but couldn't think of any. Since the player can freely place the walls, the shapes can be concave or convex making a lot of the "contains" tests in geometry invalid (like traversing the edges clockwise and ensuring the castle is always to the right, which relies on convex shapes). – MichaelHouse Dec 17 '14 at 19:06
• To know if the castle is inside the walls, you can simply traverse the grid, starting from the castle position, in any direction, and count the number of walls you traverse until you arrive at an edge of the map; even means you are outside, odd or zero you're in. This is assuming that your walls form a closed shape. But yeah, flood fill is the way. – sharvey Dec 17 '14 at 22:09
• @Byte56, i've been trying to implement this algorithm, but being kinda failures.. Cant see how can i realize that the castel is inside the walls, can only see it to change the path around castel.. – Cafn Dec 18 '14 at 21:05


text:
## Introductory Chemistry (5th Edition)

There are $1.3 \times 10^{27}$ atoms of Cu
Number of mole = $\frac{mass}{molar mass} = \frac{133 \times 10^{3}}{63.5} = 2094.45$ moles 1 mole = $6.022 \times 10^{23}$ atoms number of atoms = (number of moles) $\times (6.022 \times 10^{23})$ = $(2094.45) \times (6.022 \times 10^{23})$ = $1.3 \times 10^{27}$ atoms Therefore there are $1.3 \times 10^{27}$ atoms of Cu


text:
# Discrepancy between cross-validation and un-seen data predictions

I am facing an issue with an imbalanced dataset. The dataset contains 20% targets and 80% non-targets. I am expecting a confusion matrix below when I give un-seen data to the trained model.

[[1200   0  ]
[0      240]]

In reality I am getting a confusion matrix below. As you must have observed, it is classifying very less targets.

[[1133   67]
[ 227   13]]

The training and validation curve of a CNN model looks like below.

Any thoughts on, why so less targets get classified even though the training and validation goes quite well! Am I missing something here? I tried changing the CNN model parameters (the kernel size, dropouts, number of CNN layers, early stopping etc). However, I donot see much change.

I read the below post on "stack exchange" about data leakage. However, (hopefully) that should not be the case with my code. Why k-fold cross validation (CV) overfits? Or why discrepancy occurs between CV and test set?

• What is exactly the issue, that you are not getting a perfect confusion matrix? Comparing the training and validation loss it seems you are overfitting your model, and as a result you model will perform worse on new unseen data than on the data it was trained on. Try to see if you can decrease the amount of overfitting that happens as that should improve the performance on out of sample data. Feb 4 at 14:25

I could figure out the issue with my code. It was "data leakage".

My earlier sequence of pre-processing code was below:

1. Load the data
2. Augment the data
3. Balance the data
4. Shuffle the data
5. Split the data between "Train" and "Validation"
6. Saturate the "Train" outliers to a constant value
7. Saturate the "Validation" outliers to a constant value
8. Normalize the data between 0 and 1
9. Feed the "Train" and "Validation" data to the model
10. Plot the training and validation graph

As you can see in the above sequence the information was leaking from the validation data to the training data. Hence I was getting a perfect picture of converging model (as graph posted in the original question). I modified the sequence of pre-processing as below:

1. Load the data
2. Split the data between "Train" and "Validation"
3. Augment the "Train" data
4. Balance the "Train" data
5. Shuffle the "Train" data
6. Shuffle the "Validation" data
7. Saturate the "Train" outliers to a constant value
8. Saturate the "Validation" outliers to a constant value
9. Normalize the "Train" data between 0 and 1
10. Normalize the "Validation" data between 0 and 1
11. Feed the "Train" and "Validation" data to the model
12. Plot the training and validation graph

Now the graph gives me much more realistic picture of accuracy and loss in the CNN. See below. It looks like after 100 iterations, accuracy remains constant (around 70%) and loss blows up. I do not know how to fix the exploded loss. However, at least I am not getting a false picture now.


text:
# Dimension of a certain quotient ring of $\mathbb{C}[x_0,\ldots,x_{m-1}]$.

Let $A=\mathbb C[x_0,\dots,x_{m-1}]$ be the polynomial ring on $m$ variables.

Define $X(u)=\sum_{i=0}^{m-1} x_i u^{i+1}$ and denote by $(X(u)^r)_n$ the coefficient of $u^n$ in the expansion of the $r$-th power of $X(u)$, i.e $X(u)^r$.

Set $I=\langle (X(u)^{r})_s\mid 1\le r \le m+1, \ s\ge m+1 \rangle$.

I am trying to find a basis for $A/I$ and I am guided by some questions:

1) Is that possible to calculate the dimension of $A/I$? In fact, I am happy if I find a way to prove that it is at most $2^m$.

2) What is a Gröbner basis for $I$?

3) What is a linear basis for $A/I$?

Any help are welcome!

Added: If we let $m=2$, then $$X(u) = x_0u +x_1u^2$$ $$X(u)^2 = x_0^2u^2 + 2x_0x_1u^3 + x_1^2 u^4$$ $$X(u)^3 = x_0^3 u^3+ 3x_0^2x_1u^4 + 3 x_0x_1^2u^5+ x_1^3u^6$$ so then $I$ would be generated by $$\{x_0x_1,\ x_1^2, \ x_0^3,\ x_0^2x_1, \ x_0x_1^2,\ x_1^3 \}.$$ Therefore we conclude that $I$ is the ideal generated by $\{ x_0x_1,\ x_1^2, \ x_0^3 \}$, so that $A/I$ is a $\mathbb C$-space with basis given by the image (with respect to the natural projection) of $\{ 1, \ x_0, \ x_0^2, \ x_1 \}$.

-
Let me make sure I'm understanding your definitions right. If we let $m=2$, then $$\begin{array}{lcl} X(u) &=& x_0+u x_1 \\ X(u)^2 &=& x_0^2+2 x_0x_1 u+x_0^2 u^2 \\ X(u)^3 &=& x_0^3+3 x_0^2 x_1 u +3 x_0 x_1^2u^2+ x_1^3u^3 \end{array}$$ so then $I$ would be generated by $0$ and $x_1^3$, right? –  Alexander Gruber Dec 27 '12 at 5:32
@Alexander Gruber: I am sorry, I forgot to lift the power of $u$ in the definition of $X(u)$. As you have spent your time doing calculations, I added in the question the example of the case $m=2$. Thanks. –  Binai Dec 27 '12 at 12:57
Alright, cool, after lifting the $u$ that is what I get for $m=2$ also. –  Alexander Gruber Dec 27 '12 at 13:09
In commutative algebra dimension of a ring stands for the Krull dimension. Since you want in (1) the dimension of $A/I$ as a $\mathbb C$-vectorspace, maybe it would be good to say it explicitely. –  user26857 Dec 28 '12 at 17:25

So, if you happen to have access to MAGMA, you can run this code.

m := 5;
P<[x]> := PolynomialRing(RationalField(), m+1);

p := P!0;
for i in [1..m] do
p := p + x[i]*x[m+1]^i;
end for;

Igen := [];
for r in [1..m+1] do
C := Coefficients(p^r,x[m+1]);
for s in [m+2..#C] do
Append(~Igen,C[s]);
end for;
end for;

I := ideal<P|Append(Igen,x[m+1])>;

GroebnerBasis(EasyIdeal(I));

Q := P/I;

Dimension(Q);

Using this I've found that $\text{dim}(A/I)=2^m$ exactly for $m\leq 9$ and computed the corresponding Groebner bases and quotient rings. I am not sure how this could be proven for all $m$. Aside from actually computing it, I don't know if there is any way to get the basis of $I$ or $A/I$ in general, as the output seems quite complicated. MAGMA uses the $\rm F_4$ algorithm to find Groebner bases, which seems to be the fastest method available at this point in time. If you try to implement a Groebner basis algorithm yourself, however, I would suggest Mutant XL since it is intuitively very easy and still pretty fast.

-
Hope this helps! Feel free to leave the question open if you need to, especially if you don't have access to MAGMA. –  Alexander Gruber Dec 27 '12 at 14:12
Thanks for the suggestion by using MAGMA. I wrote a procedure to calculate the Grobner basis for $I$ and the linear basis for $A/I$ and I am obtaining the answer until $m=9$ too. I will leave open the question to see if anyone can suggest anything else. –  Binai Dec 27 '12 at 14:23


text:
Get intersection of files occuring in at least 2 files?
1
0
Entering edit mode
21 months ago
vctrm67 ▴ 20

Is there an easy way to use bedtools (or any other software) to get the features of the intersection of multiple bed files, for features/intervals that occur in at least 2 bed files?

bedtools • 575 views
ADD COMMENT
1
Entering edit mode
21 months ago

Here is a general approach with BEDOPS bedmap --count, which generalizes to N internally-disjoint (and sort-bed-sorted) input files:

$bedops --everything 1.bed 2.bed 3.bed ... N.bed \ | bedmap --count --echo --delim '\t' - \ | uniq \ | awk -v OVERLAPS=2 '$1 >= OVERLAPS' \
| cut -f2- \
> common.bed

The bedmap step uses, by default, overlap of one or more bases for inclusion. You can modify this threshold to be more stringent. The readthedocs site has details, or run bedmap --help for a shorter overview.

By changing the test in the awk statement, this approach can be modified to return other subsets of the input's power set, e.g., all elements common to exactly, less than, or greater than N inputs.

Once you have the elements which meet your overlap threshold, you can then process those elements to get their overlapping regions via a final operation:

$bedops --partition common.bed | bedmap --count --echo --delim '\t' - common.bed | awk '$1 >= 2' | cut -f2- > overlaps.bed

If your inputs are not internally disjoint — if some elements may overlap within any one of the N input files — you might instead apply some ID-based tricks I describe in my answer over here: A: Intersect multiple BED files

ADD COMMENT
0
Entering edit mode

Hi, thanks for the answer. I am a bit confused by when you say "internally disjoint". Are you implying that for any region in any bed file, it must not overlap with any other region in any other bed file? If so, I think this would not help me; I am looking to preserve the regions that overlap in at least 2 bed files.

Or by "internally disjoint" do you refer to any region within a single bam file? As in, no region within any given bam file can overlap with any other region in that same bam file?

ADD REPLY
0
Entering edit mode

What I mean is the case where any two regions within a single BED file overlap.

For instance, sequencing reads converted from BAM or SAM to BED will almost certainly overlap within the same file, because reads typically pile up that way.

Other types of annotations could also be problematic, in that they can overlap: genes, TF binding sites, DHSs.

If this is the case, then you need to do a little more work to add (unique) per-file identifiers to each BED file, so that when you find overlaps, you also test if they have different per-file identifiers.

Otherwise, without that step (or some similar approach) you would get overlapping regions that are internal to one file. This does not appear to be what you want. It sounds like you want overlaps only from at least two or more files.

ADD REPLY
0
Entering edit mode

I was looking at the bedmaps manual, and I read this line:

Looking back at the Map and Reference datasets, let’s say we want to count the number of elements in Map that overlap a given Reference element, as well as the extent of that overlap as measured by the total number of overlapping bases from mapped elements. For this, we use the --count and --bases flags, respectively:

$bedmap --echo --count --bases reference.bed map.bed chr21 33031200 33032400 ref-1|61|1200 chr21 33031400 33031800 ref-2|21|400 chr21 33031900 33032000 ref-3|6|100 This result tells us that there are 61 elements in Map that overlap ref-1, and 1200 total bases from the 61 elements overlap bases of ref-1. Similarly, 21 elements overlap ref-2, and 400 total bases from the 21 elements overlap bases of ref-2, etc.  If I utilize more than 2 bed files A, B, C...etc., will this get all the common elements in bed files B, C, D... compared to A, or will it compare among all bed files (such as A, C, D, E... to B) as well? ADD REPLY 0 Entering edit mode The bedops tool allows more than two files (A, B, C, etc.). Conversely, the bedmap tool only takes two files as arguments (reference and map). However, if you're using bedmap, you can use a trick called a "process substitution" to replace the reference.bed or map.bed files. A process substitution is a fancy term for building a BED file on the fly. We can use it as input to bedmap. Here's an example: $ bedmap --echo --count --bases reference.bed <(bedops --everything A.bed B.bed ... N.bed)

In this example, the former map.bed input gets replaced with what would come out of bedops --everything A.bed B.bed ... N.bed (the set union of files A, B, C, etc.).

This is functionally equivalent to:

\$ bedops --everything A.bed ... N.bed | bedmap --echo --count --bases reference.bed -

Any command you put into the ... in <(...) returns a file. You can specify this as input to bedmap, bedops, and other tools. You could do <(bedops --merge A.bed ... N.bed), or any other operations on any other files. It just depends on what kinds of elements you want to map.

ADD REPLY
0
Entering edit mode

Also if you could explain the purpose of the second command, that would be helpful. I ran these commands but in the overlap.bed file, I see that the intervals are not contiguous and are only 1 base long. Is there a reason for this?

ADD REPLY
0
Entering edit mode

Can you post the command you're running and perhaps provide access to your input files (or a small sample snippet)? I can run that locally and help answer your question with more specifics.

ADD REPLY

Login before adding your answer.

Traffic: 2440 users visited in the last hour
Help About
FAQ
Access RSS
API
Stats

Use of this site constitutes acceptance of our User Agreement and Privacy Policy.

Powered by the version 2.3.6


text:
## Definition

Let $p$ be any prime number.

Let $\norm {\,\cdot\,}_p$ be the p-adic norm on the rationals $\Q$.

By P-adic Norm is Non-Archimedean Norm then $\norm {\,\cdot\,}_p$ is a non-archimedean norm on $\Q$ and the pair $\struct {\Q, \norm {\,\cdot\,}_p}$ is a valued field.

### $p$-adic Norm Completion of Rational Numbers

The p-adic numbers, denoted $\struct {\Q_p, \norm {\,\cdot\,}_p}$, is the unique (up to isometric isomorphism) non-Archimedean valued field that completes $\struct {\Q, \norm {\,\cdot\,}_p}$.

Each element of $\Q_p$ is called a $p$-adic number.

### Quotient of Cauchy Sequences in $p$-adic Norm

Let $\CC$ be the commutative ring of Cauchy sequences over $\struct {\Q, \norm {\,\cdot\,}_p}$.

Let $\NN$ be the set of null sequences in $\struct {\Q, \norm {\,\cdot\,}_p}$.

Let $\Q_p$ denote the quotient ring $\CC \, \big / \NN$.

Let $\norm {\, \cdot \,}_p:\Q_p \to \R_{\ge 0}$ be the norm on the quotient ring $\Q_p$ defined by:

$\displaystyle \forall \sequence {x_n} + \NN: \norm {\sequence {x_n} + \NN }_p = \lim_{n \mathop \to \infty} \norm{x_n}_p$

By Corollary to Quotient Ring of Cauchy Sequences is Normed Division Ring, then $\struct {\Q_p, \norm {\, \cdot \,}_p}$ is a valued field.

Each left coset $\sequence {x_n} + \NN \in \CC \, \big / \NN$ is called a $p$-adic number.

The p-adic numbers is the valued field $\struct {\Q_p, \norm {\,\cdot\,}_p}$.

### $p$-adic Norm on $\Q_p$

The norm $\norm {\,\cdot\,}_p$ on $\Q_p$ is called the $p$-adic norm on $\Q_p$.

## Also denoted as

The $p$-adic numbers are often simply denoted as $\Q_p$ where the $p$-adic Norm is implied.


text:
## Guessing at the discretization, of the Sallen-Key Filter, with Q-Multiplier.

One concept that exists in modern digital signal processing is, that a simple algorithm can often be written, to perform what old-fashioned, analog filters were able to do.

But then, one place where I find lacking progress – at least, where I can find the information posted publicly – is, about how to discretize slightly more complicated analog filters. Specifically, if one wants to design 2nd-order low-pass or high-pass filters, one approach which is often recommended is, just to chain the primitive low-pass or high-pass filters. The problem with that is, the highly damped frequency-response curve that follows, which is evident, in the attenuated voltage gain, at the cutoff frequency itself.

In analog circuitry, a solution to this problem exists in the “Sallen-Key Filter“, which naturally has a gain at the corner frequency of (-6db), which would also result, if two primitive filters were simply chained. But beyond that, the analog filter can be given (positive) feedback gain, in order to increase its Q-factor.

I set out to write some pseudo-code, for how such a filter could also be converted into algorithms…

Second-Order...

LP:
for i from 1 to n
Y[i] := ( k * Y[i-1] ) + ((1 - k) * X[i]) + Feedback[i-1]
Z[i] := ( k * Z[i-1] ) + ((1 - k) * Y[i])
Feedback[i] := (Z[i] - Z[i-1]) * k * α
(output Z[i])

BP:
for i from 1 to n
Y[i] := ( k * Y[i-1] ) + ((1 - k) * X[i]) + Feedback[i-1]
Z[i] := ( k * (Z[i-1] + Y[i] - Y[i-1]) )
Feedback[i] := Z[i] * (1 - k) * α
(output Z[i])

HP:
for i from 1 to n
Y[i] := ( k * (Y[i-1] + X[i] - X[i-1]) ) + Feedback[i-1]
Z[i] := ( k * (Z[i-1] + Y[i] - Y[i-1]) )
Feedback[i] := Z[i] * (1 - k) * α
(output Z[i])

Where:

k is the constant that defines the corner frequency via ω, And
α is the constant that peaks the Q-factor.

ω = 2 * sin(π * F0 / h)
k = 1 / (1 + ω), F0 < (h / 4)

h   Is the sample-rate.
F0  Is the corner frequency.

To achieve a Q-factor (Q):
α = (2 + (sin^2(π * F0 / h) * 2) - (1 / Q))
'Damping Factor' = (ζ) = 1 / (2 * Q)

Critical Damping:
ζ = 1 / sqrt(2)
(...)
Q = 1 / sqrt(2)

(Algorithm Revised 2/08/2021, 23h40. )

(Computation of parameters Revised 2/09/2021, 2h15. )

(Updated 2/10/2021, 18h25… )

## Some realizations about Digital Signal Processing

One of the realizations which I’ve just come across recently, about digital signal processing, is that apparently, when up-sampling a digital stream twofold, just for the purpose of playing it back, simply to perform a linear interpolation, to turn a 44.1kHz stream into an 88.2kHz, or a 48kHz stream into a 96kHz, does less damage to the sound quality, than I had previously thought. And one reason I think this is the factual realization that to do so, really achieves the same thing that applying a (low-pass) Haar Wavelet would achieve, after each original sample had been doubled. After all, I had already said, that Humans would have a hard time being able to hear that this has been done.

But then, given such an assumption, I think I’ve also come into more realizations, of where I was having trouble understanding what exactly Digital Signal Processors do. It might be Mathematically true to say, that a convolution can be applied to a stream after it has been up-sampled, but, depending on how many elements the convolution is supposed to have, whether or not a single DSP chip is supposed to decode both stereo channels or only one, and whether that DSP chip is also supposed to perform other steps associated with playing back the audio, such as, to decode whatever compression Bluetooth 4 or Bluetooth 5 have put on the stream, it may turn out that realistic Digital Signal Processing chips just don’t have enough MIPS – Millions of Instructions Per Second – to do all that.

Now, I do know that DSP chips exist that have more MIPS, but then those chips may also measure 2cm x 2cm, and may require much of the circuit-board they are to be soldered in to. Those types of chips are unlikely to be built-in to a mid-price-range set of (Stereo) Bluetooth Headphones, that have an equalization function.

But what I can then speculate further is that some combination of alterations of these ideas should work.

For example, the convolution that is to be computed could be computed on the stream before it has been up-sampled, and it could then be up-sampled ‘cheaply’, using the linear interpolation. The way I had it before, the half-used virtual equalizer bands would also accomplish a kind of brick-wall filter, whereas, to perform the virtual equalizer function on the stream before up-sampling would make use of almost all the bands, and doing it that way would halve the amount of MIPS that a DSP chip needs to possess. Doing it that way would also halve the frequency linearly separating the bands, which would have created issues at the low end of the audible spectrum.

Alternatively, implementing a digital 9- or 10-band equalizer, with the
bands spaced an octave apart, could be achieved after up-sampling, instead of before up-sampling, but again, much more cheaply in terms of computational power required.

Dirk


text:
View Single Post

## Need help understanding the pushforward

In my notes, the following two functions are defined:

Suppose $M^m$ and $N^n$ are smooth manifolds, $F:M \to N$ is smooth and $p \in M$. We define:
$$F^*:C^\infty (F(p)) \to C^\infty (p)\ ,\ F^*(f) = f \circ F$$
$$F_{*p}: T_pM \to T_{F(p)}N\ ,\ [F_{*p}(X)](f) = X(F^*f) = X(f \circ F)$$

I understand the first function, $F^*$; it maps $f$, a function on $C^\infty(F(p))$, to $f \circ F$, a function on $C^\infty(p)$.

However, I don't understand the second one, $F_{*p}$. Since $X(f) \in T_pM$, it follows that $f \in C^\infty (p)$. But then how is
$$[F_{*p}(X)](f) = X(F^*f)$$
defined? After all, in the definition of $F_{*p}(X)$, $f$ is a function on $C^\infty (p)$, not $C^\infty(F(p))$, so how can we evaluate $F^*f$?
 PhysOrg.com science news on PhysOrg.com >> City-life changes blackbird personalities, study shows>> Origins of 'The Hoff' crab revealed (w/ Video)>> Older males make better fathers: Mature male beetles work harder, care less about female infidelity


text:
# What is the standard form of y=(3x - 15)(x - 5) ?

Mar 8, 2016

Standard form is $y = 3 {x}^{2} - 30 x + 75$

#### Explanation:

Standard form of quadratic polynomial with one variable is $y = a {x}^{2} + b x + c$ Hence to convert y=(3x−15)(x−5), one should expand the RHS.

y=(3x−15)(x−5)=3x(x-5)-15(x-5)

= $3 {x}^{2} - 15 x - 15 x + 75$ or

= $3 {x}^{2} - 30 x + 75$


text:
# Posterior distribution of logistic regression coefficient

I have a binary logistic regression with the following properties

Consider the logistic regressionfor binarydataYi ∈{0,1} and the covariate vector xi =(xi,1,xi,2,…,xi,p) . Under the logistic regression assumption, the sampling distribution of Yi is (1). We assume a normal prior for βj for j = 1,…,n as in (2), and βj’s are independent of each other. (μj,σj2) are prior parameters and need to be specified.

Prob(Yi = 1|β) = exp(x⊤i β)/ 1+exp(x⊤i β) βj ∼N(μj,σj2) (2)

I have to find the posterior distribution for β, i.e., p(β|y, μ1, . . . , μp, σ12, . . . , σp2),.


text:
A dynamical system is a space X, together with an action $(g,x) \mapsto gx$ of some group $G = (G,\cdot)$.  [In practice, one often places topological or measure-theoretic structure on X or G, but this will not be relevant for the current discussion.  In most applications, G is an abelian (additive) group such as the integers ${\Bbb Z}$ or the reals ${\Bbb R}$, but I prefer to use multiplicative notation here.]  A useful notion in the subject is that of an (abelian) cocycle; this is a function $\rho: G \times X \to U$ taking values in an abelian group $U = (U,+)$ that obeys the cocycle equation

$\rho(gh, x) = \rho(h,x) + \rho(g,hx)$ (1)

for all $g,h \in G$ and $x \in X$.  [Again, if one is placing topological or measure-theoretic structure on the system, one would want $\rho$ to be continuous or measurable, but we will ignore these issues.] The significance of cocycles in the subject is that they allow one to construct (abelian) extensions or skew products $X \times_\rho U$ of the original dynamical system X, defined as the Cartesian product $\{ (x,u): x \in X, u \in U \}$ with the group action $g(x,u) := (gx,u + \rho(g,x))$.  (The cocycle equation (1) is needed to ensure that one indeed has a group action, and in particular that $(gh)(x,u) = g(h(x,u))$.)  This turns out to be a useful means to build complex dynamical systems out of simpler ones.  (For instance, one can build nilsystems by starting with a point and taking a finite number of abelian extensions of that point by a certain type of cocycle.)

A special type of cocycle is a coboundary; this is a cocycle $\rho: G \times X \to U$ that takes the form $\rho(g,x) := F(gx) - F(x)$ for some function $F: X \to U$.  (Note that the cocycle equation (1) is automaticaly satisfied if $\rho$ is of this form.)  An extension $X \times_\rho U$ of a dynamical system by a coboundary $\rho(g,x) := F(gx) - F(x)$ can be conjugated to the trivial extension $X \times_0 U$ by the change of variables $(x,u) \mapsto (x,u-F(x))$.

While every coboundary is a cocycle, the converse is not always true.  (For instance, if X is a point, the only coboundary is the zero function, whereas a cocycle is essentially the same thing as a homomorphism from G to U, so in many cases there will be more cocycles than coboundaries.  For a contrasting example, if X and G are finite (for simplicity) and G acts freely on X, it is not difficult to see that every cocycle is a coboundary.)  One can measure the extent to which this converse fails by introducing the first cohomology group $H^1(G,X,U) := Z^1(G,X,U) / B^1(G,X,U)$, where $Z^1(G,X,U)$ is the space of cocycles $\rho: G \times X \to U$ and $B^1(G,X,U)$ is the space of coboundaries (note that both spaces are abelian groups).  In my forthcoming paper with Vitaly Bergelson and Tamar Ziegler on the ergodic inverse Gowers conjecture (which should be available shortly), we make substantial use of some basic facts about this cohomology group (in the category of measure-preserving systems) that were established in a paper of Host and Kra.

The above terminology of cocycles, coboundaries, and cohomology groups of course comes from the theory of cohomology in algebraic topology.  Comparing the formal definitions of cohomology groups in that theory with the ones given above, there is certainly quite a bit of similarity, but in the dynamical systems literature the precise connection does not seem to be heavily emphasised.   The purpose of this post is to record the precise fashion in which dynamical systems cohomology is a special case of cochain complex cohomology from algebraic topology, and more specifically is analogous to singular cohomology (and can also be viewed as the group cohomology of the space of scalar-valued functions on X, when viewed as a G-module); this is not particularly difficult, but I found it an instructive exercise (especially given that my algebraic topology is extremely rusty), though perhaps this post is more for my own benefit that for anyone else.

— Chains —

Throughout this discussion, the dynamical system X, the group G, and the group U will be fixed.

For any $n \geq 0$, we define an n-chain to be a formal integer linear combination of n+1-tuples $(g_1,\ldots,g_n,x)$, where $x \in X$ and $g_1,\ldots,g_n \in G$.  One may wish to think of each such tuple as an “oriented simplex” connecting the n+1 points $x, g_n x, g_{n-1} g_n x, \ldots, g_1 \ldots g_n x$.  Thus, a 0-chain is a formal combination $\sum_{i=1}^m c_i x_i$ of points, a 1-chain is a formal combination $\sum_{i=1}^m c_i (g_i,x_i)$ of “line segments” from $x_i$ to $g_i x_i$, and so forth.  Let $C_n(G,X)$ be the space of n-chains; this is an abelian group.  We also adopt the convention that $C_n(G,X)$ is trivial for $n < 0$.

For each $n > 0$, we define the boundary map $\partial: C_n(G,X) \to C_{n-1}(G,X)$ to be the unique homomorphism such that

$\displaystyle \partial (g_1,\ldots,g_n,x) = (g_1,\ldots,g_{n-1},g_n x)$

$\displaystyle + \sum_{i=1}^{n-1} (-1)^{n-i} (g_1,\ldots,g_{i-1},g_i g_{i+1}, g_{i+2},\ldots,g_n, x)$

$+ (-1)^n (g_2,\ldots,g_n,x)$

thus for instance

$\partial (g,x) = gx - x$

$\partial (g,h,x) = (g,hx) - (gh,x) + (h,x)$

$\partial (g,h,k,x) = (g,h,kx) - (g,hk,x) + (gh,k,x) - (h,k,x)$

and so forth.  Note that this is analogous to the boundary map in singular homology, if one views the n+1-tuple $(x,g_1,\ldots,g_n)$ as a simplex as discussed earlier.  We also define the boundary maps $\partial: C_n(G,X) \to C_{n-1}(G,X)$ for $n \leq 0$ to be the trivial map, thus for instance $\partial x = 0$.  It is not hard to verify the fundamental relation

$\partial^2 = 0$

thus turning the sequence of groups $C_n(G,X)$ into a chain complex.

An n-chain with vanishing boundary is called an n-cycle, while an n-chain which is the boundary of an (n-1)-chain is called an n-boundary; the spaces of n-cycles and n-boundaries are denoted $Z_n(G,X)$ and $B_n(G,X)$ respectively.  Thus for instance $(gh,x) - (h,x) - (g,hx)$ is both a 1-cycle and a 1-boundary.  However, if g is a non-trivial group element that fixes x and G is abelian, one can show that $(g,x)$ is a 1-cycle but not a 1-boundary.

We define the homology groups $H_n(G,X) := Z_n(G,X)/B_n(G,X)$ for all n.  It is a nice exercise to compute these groups in some simple cases, e.g.

• If G acts transitively on X, then $H_0(G,X) \equiv {\Bbb Z}$.
• If G acts freely on X, then $H_n(G,X)$ is trivial for $n > 0$.
• If X is a point, then $H_1(G,X) \equiv G/[G,G]$ is the abelianisation of G.  [Question: Is there a nice description of the higher homology groups $H_n(G,X)$, $n > 1$ in this case?]

However, I don’t know of any application of these homology groups to the theory of dynamical systems.

— Cochains —

An n-cochain is a homomorphism from the space $C_n(G,X)$ of n-chains to U.  Since $C_n(G,X)$ is a free abelian group generated by the simplices $(x,g_1,\ldots,g_n)$, we can view an n-cochain as a function $F: (x,g_1,\ldots,g_n) \to F(x,g_1,\ldots,g_n)$ from $G \times \ldots \times G \times X$ to U.  (Again, we are ignoring all measure-theoretic or topological considerations here.)  The space of all n-cochains is denoted $C^n(G,X,U) := \hbox{Hom}(C_n(G,X),U)$; this is an abelian group.

The boundary map $\partial: C_n(G,X) \to C_{n-1}(G,X)$ defines by duality a coboundary map $\delta: C^{n-1}(G,X,U) \to C^n(G,X,U)$, defined by the formula

$\delta F( c ) := F( \partial c )$

for all $F \in C^{n-1}(G,X,U)$ and $c \in C_n(G,X)$; viewing F as a function on simplices, we thus have

$\displaystyle \delta F(g_1,\ldots,g_n,x) = F(g_1,\ldots,g_{n-1},g_n x)$

$\displaystyle + \sum_{i=1}^{n-1} (-1)^{n-i} F( g_1,\ldots,g_{i-1},g_i g_{i+1},\ldots,g_n,x)$

$+ (-1)^n F(g_2,\ldots,g_n,x).$

Thus for instance

$\delta F(g,x) = F(gx) - F(x)$

for 0-cochains $F:X \to U$,

$\delta \rho(g,h,x) = \rho(g,hx) - \rho(gh,x) + \rho(h,x)$

for 1-cochains $\rho: G \times X \to U$, and so forth.

Because $\partial^2 = 0$, we have $\delta^2 = 0$, and so $C^n(G,X,U)$ becomes a cochain complex.  n-cochains whose coboundary vanishes are known as n-cocycles, and n-cochains which are the coboundary of an (n-1)-cochain are known as n-coboundaries.  The spaces of n-cocycles and n-cochains are denoted $Z^n(G,X,U)$ and $B^n(G,X,U)$ respectively, allowing us to define the $n^{th}$ cohomology group $H^n(G,X,U) := Z^n(G,X,U)/B^n(G,X,U)$.

When n=0, and if the action of G is transitive (in the discrete category), minimal (in the topological category), or ergodic (in the measure-theoretic category), the only 0-cocycles are the constants, and the only 0-coboundary is the zero function, so $H^0(G,X,U) \equiv U$.  When n=1, it is not hard to see that the notion of 1-cocycle and 1-coboundary correspond to the notion of cocycle and coboundary discussed at the beginning of this post.

This whole theory raises the obvious question as to whether the higher cocycles, coboundaries, and cohomology groups have any relevance in dynamical systems.  For instance, a 2-cocycle is (after minor notational changes) a function $\psi: G \times G \times X \to U$ that obeys the 2-cocycle equation

$\psi(g,h,kx) - \psi(g,hk,x) + \psi(gh,k,x) - \psi(h,k,x) = 0$

while a 2-coboundary is a function of the form

$\psi(g,h,x) := \rho(gh,x) - \rho(h,x) - \rho(g,hx)$

for some $\rho: G \times X \to U$.  Is there some dynamical systems interpretation of these objects, much as 1-cocycles and 1-coboundaries can be interpreted as describing abelian extensions and essentially trivial abelian extensions respectively?  I don’t know the answer to this question.  (Perhaps one would have to start introducing the concept of a “2-dynamical system”, whatever that means.)  In my forthcoming paper with Vitaly Bergelson and Tamar Ziegler, we do briefly encounter 2-coboundaries (we have to deal with various “quasi-cocycles” – 1-chains $\rho$ whose 2-coboundary $\delta \rho$ does not vanish completely, as with 1-cocycles, but is still of a relatively simple form, such as a constant or a polynomial) but we do not make systematic use of this concept.  (We also rely heavily in our paper on the cubic complexes ${}X^{[k]}{}$ of Host and Kra, which have some superficial resemblance to the simplex structures appearing here, but I do not know if there is a substantive connection in this regard.)

Another oddity is that homology and cohomology, as it is classically defined, requires the space of chains, cochains, etc. to all be abelian groups; but for dynamical systems one can certainly talk about cocycles and coboundaries taking values in a non-abelian group U by modifying the definitions slightly, leading to the concept of a group extension of a dynamical system.  (In this context, the first cohomology $H^1(G,X,U)$ becomes a quotient space rather than a group; see also my earlier post interpreting these cocycles in the language of gauge theory.)  It seems to me that in this case, the dynamical system concept of a cocycle or coboundary cannot be interpreted in terms of classical cohomology theory (but presumably can be handled by non-abelian group cohomology).

[Update, Dec 22: Some typos and LaTeX anomalies fixed.]

Update, Jan 8: Over at the n-Category Café, Minhyong Kim has provided a nice answer to my question about the relevance of higher order cohomology, such as $H^2(G,X,U)$, to the problem of extending dynamical systems.  Suppose one has a short exact sequence

$0 \to V \to \tilde U \to U \to 0$

of abelian groups, thus one can view $\tilde U$ as the space of pairs $(u,v)$ with $u\in U, v \in V$ with some group addition law

$(u,v) + (u',v') := (u+u', v+v'+B(u,u'))$ (2)

for some function $B: U \times U \to V$, that needs to obey a certain set of axioms to make $\tilde U$ an abelian group, which we will not write down here.  We then claim that we have a long exact sequence

$\to H^1(G,X,\tilde U) \to H^1(G,X,U) \to H^2(G,X,V) \to$,  (3)

thus $H^2(G,X,V)$ is capable of detecting whether a U-extension of a G-system X can be lifted to a $\tilde U$-extension.

The first map in (3) is obvious: the projection from $\tilde U$ to $U$ induces a projection from 1-cocycles $\tilde \rho: G \times X \to \tilde U$ to 1-cocycles $\rho: G \times X \to U$ which maps 1-coboundaries to 1-coboundaries, and thus maps $H^1(G,X,\tilde U)$ to $H^1(G,X,U)$.  The second map requires a bit more thought.  Suppose one is given a 1-cocycle $\rho: G \times X \to U$ and asks whether it can be lifted to a 1-cocycle $\tilde \rho: G \times X \to \tilde U$ by the above projection.  Writing $\tilde \rho = (\rho,\sigma)$ for some $\sigma: G \times X \to V$ and using (1), (2), we see that the question is equivalent to finding a $\sigma$ that obeys the equation

$\sigma(gh, x) = \sigma(h,x) + \sigma(g,hx) + B( \rho(h,x), \rho(g,hx) )$

or in other words, to show that the map $\Phi(\rho): (g,h,x) \mapsto B(\rho(h,x), \rho(g,hx) )$ is a V-valued 2-coboundary.   The same observation (now setting $\sigma=0$) shows that the map $(g,h,x) \mapsto (0,\Phi(\rho))$ is a $\tilde U$-valued 2-coboundary (indeed, it is the coboundary of $(\rho,0)$), hence a $\tilde U$-valued 2-cocycle, and thus $\Phi(\rho)$ is a V-valued 2-cocycle, and so the map $\rho \mapsto \Phi(\rho)$ is a map from 1-cocycles $\rho: G \times X \to U$ to 2-cocycles $\Phi(\rho): G \times G \times X \to V$.  Similarly, given two 1-cocycles $\rho, \rho': G \times X \to U$, we see that $(\rho+\rho',0)$ differs from $(\rho,0)+(\rho',0)$ by some V-valued 1-cochain, so on taking derivatives we see that $\Phi(\rho+\rho')$ differs from $\Phi(\rho)+\Phi(\rho')$ by some 2-coboundary, thus $\Phi$ is linear modulo 2-coboundaries.  Finally, if $\rho$ is a U-valued 1-coboundary, then $(\rho,0)$ is the sum of a $\tilde U$-valued 1-coboundary and a V-valued 1-cochain, and so on taking derivatives we see that $\Phi$ maps 1-coboundaries to 2-coboundaries.  (Presumably the above arguments are a special case of one of the standard diagram chasing lemmas in homological algebra, but I don’t know which one it is.  One could also verify these facts from the axioms of B induced from (2) and the abelian group structure on $\tilde U$, but this turns out to be remarkably tedious.)  Hence it induces a map from $H^1(G,X,U)$ to $H^2(G,X,V)$, and then (3) is exact by the preceding discussion.


text:
# All Questions

673 views

### Slideshow export to PDF (landscape)

I am trying to export a slideshow presentation that I have created in Mathematica 8 to PDF in case I have trouble connecting my laptop to a projector for a talk I am giving. I have tried Save As, Save ...
284 views

### How can I prove an equation has a certain number of real roots?

I have this code ...
64 views

### InputField AutoSize Speed Issue

How do I have an InputField adjust to fill the remaining size of the window automatically? For example: Using the ImageSize ...
358 views

### City/Country Names by GeoLocation

How do I get the city and country names from the output of FindGeoLocation[] {lat, long} ?
134 views

### Retain required terms in asymptotic expansions

I am using Mathematica 8 to do lengthy asymptotic expansions for use in statistics. In particular I have $\lambda=\beta+\epsilon+\delta+\gamma+O(n^{-5/2})$ where the first term is of order ...
472 views

### Multi-dimensional integral in the complex plane with poles and essential singularity

I've passed the last week searching a way to numerically integrate this multi-dimensional integral in the complex plane at the poles and avoiding the singularity at z=0:  \oint_{C}\oint_{C\ auound\ ...
237 views

### Handling Overflow

I have a notebook which takes in a user-defined function and starting value and tracks the orbit of the particle under iteration of the function. The problem occurs when the user enters a starting ...
163 views

### Manipulating several values from the same interval

Some of my calculations depend on the choice of several values from the interval [-2, 2] (it is more or less interpolation of a fixed function using the points as parameters). I want to create a ...
903 views

### How could I define a function as the solution of equations in Mathematica?

I have posed a specific question yesterday but it may be too trivial to answer. I think the question could be asked in a more general way so it is easier to answer. Then I could solve the original ...
291 views

### StringReplace except some pattern

StringReplace and search out of one pattern ...
141 views

### Working precision for each variable

How can I define working precision for each variable individually for example: Maximize[x y< 100, {x, y}] where the working precisions for ...
212 views

### Module Returns Two Values for Plot; I need to Color them

This is probably a very stupid question, but I've been fighting with it for quite awhile now. So suppose you have a module: ...
186 views

### Error in ARIMAProcess example

I am trying to compile the sample of ARIMAProcess of MMA here .It doesn't work.What is wrong?Could you please help?I am using exact same code. ...
939 views

### PlotStyle in ListPlot: change color scheme, manually choose color of first plot

Say i have this data: data1 = Map[Cos, Range[0, 20]]; data2 = Map[Sin, Range[0, 20]]; And i want to plot data1 in gray and a ...
88 views

### How can I transform parts of an Integer list to a String list

There is a sorted list of Integers. ilist = PadRight[Sort[ RandomSample[Range[1, 99999], 3], Less], 5] It should become string area codes like: ...
154 views

I have ...
133 views

### Difference between vector's Dimensions

What's the difference between projection= Table[Conjugate[autoVett[[k]].someVector1], {k, 1, r}] Dimensions[projection] that gave me as results ...
170 views

### How can I change the highlighting color of an InlineMathCell?

When using the InlineMathCell one types Ctrl+9 within the text cell, and gets a slot for starting typing the InlineMathCell part. When typing the content of the InlineMathCell is slightly highlighted ...
107 views

### Split one string about a fixed width with SyntaxQ=True

How to split one string about a fixed width, the string may come from the input or output cell of Notebook. sample string ...
154 views

### Plotting a pattern made of repeating unit blocks but of changing width

I am plotting a pattern as illustrated in link shown below. I want to create an image of fixed size. The whole image should be filled by repeating unit blocks which consist of black and green ...
510 views

### How to embed an image into a string?

Note: The bug described in the post is in Mathematica 9, and has been fixed in 10.0. The documentation for String contains the following statements: Strings ...
692 views

### How to draw a Circle in a graph with Log Y Scale

I've programmed drawing tools for graph images and am experiencing a problem with the coordinates of an Ellipse on a graph with a Log Y axis. It's quite easy to work out the Y Axis coordinates for ...
710 views

### Expression of uncertainty in measurement.

I have a problem with writing a Mathematica function. I have been requested to show the results of my experiments with the measurement uncertainty (mu) like below: ...
184 views

### Non linear constrained interger Optimization

I need to maximize the equation below which is subjected to some nonlinear constraints Maximize hsum + isum + jsum + ksum + lsum + msum + nsum + osum ...
315 views

### Interpolating function as a model in Mathematica's procedures for fitting

Is it possible to use interpolating function with parameters as a model for NonLinearModel fit (and other integrated methods for fitting)? Similar question was already posted earlier - How do I find ...
762 views

### Linear regression with x and y errors

I have a question about finding a linear regression weighted with x and y errors. I found the answer provided by 0x4A4D in Estimate error on slope of linear regression given data with associated ...
139 views

### How to evaluate only arguments, but leave topmost expression unevaluated? [duplicate]

I want to represent expressions mostly in unevaluated form, but being able to evaluate it's subparts. For example, how to evaluate only arguments, but leave topmost expression unevaluated? For ...
36 views

### Eigenvalues for large matrices without Root-Solution [duplicate]

I read some other questions and tried to implement the given answers but yet, I did not succeed to find proper solutions for my eigenvalues. I hope someone can show me how to do this for this case, ...
223 views

### Unresolved differential equation [closed]

Why can't Mathematica solve this equation as stated? ...
2k views

### Visualization of Bivariate Distributions

I know it is perfectly possible to show the bivariate probability distributions in MMA. But my question is can we show each dimension of distribution in 2D dimension while we are showing the 3D plot? ...
375 views

### Is it possible to define custom compound assignment operators like ⊕= similar to built-ins +=, *= etc?

I would like to do something like this: ...
45 views

...
532 views

### Image Processing: Concrete test blocks

Background Concrete is mixture of aggregates and cement. Aggregates are composed of different sizes and colors. Core samples are taken by drilling in order to test the strength of concrete . They are ...
123 views

### Non-Solvable PDE?

I would like to know whether this PDE is solvable and if yes, for which values of $a$. ...
498 views

### Share experiences, preferably the surprising ones, with using ItoProcess

Can people please share their experiences, preferably the surprising ones, with using ItoProcess? I am a big fan of ItoProcess and have already used it for several finance-related tasks, though I ...
423 views

### Performing Computations on Sets

I would like to find a permutation of $\quad S=\{\frac{1}{10}, \frac{1}{2}, \frac{4}{7}, \frac{3}{5}, \frac{2}{3} \}\quad$ that maximizes the sum of theses elements raised to unique powers: ...
148 views

### Integrating and plotting pde system solution

I have a trouble with plotting a pde system solution. I'm solving a PDE system in 2-dimensional space and then I want to integrate the solution along one dimension and build a log plot along the ...
499 views

Running InstallR["RHomeLocation" -> "C:\\Program Files\\R\\R-3.0.1"] results in a popup box titled "Version Mismatch" saying Error: R.DLL version does ...
636 views

### ItoProcess function

While looking in the help manual of Mathematica concerning the ItoProcess function I found the following: ItoProcess[{a,b,c},x,t]: represents an Ito Process y(t)=c(t,x(t)), where ...
112 views

### How can I revise my program to avoid “No more memory available”? [duplicate]

I have a program for calculating a type of list. ...
265 views

### InputField with Scrollbars [duplicate]

Edits are marked in bold: How do I make an InputField that behaves just like the following HTML Textarea example. ...
173 views

### How to convert comment in RowBox to DisplayForm string

ToExpression[RowBox[{"a","(*","what", "*)"}],StandardForm] This conversion above ignores the commment content (*what*) The ...
505 views

### Improve TextRecognize[] on numbers

I have an image contain only numbers, and TextRecognize fail to recognize some numbers: img=; TextRecognize[img] (*826718*) The documentation says that "The ...
447 views

### Summation with constraints

I am trying to do the summation shown below, $\sum_{i_1=0}^{imax_1} \sum_{i_2=0}^{imax_2} \dots \sum_{i_k=0}^{imax_k} f(i_1,\dots,i_k)$ $k$ is a variable. Therefore $i$ and $imax$ are defined as ...
130 views

### Simple Macro or Meta Programming for Data Analysis [duplicate]

I have a large number of data variables that are represented in MMA as symbols set to lists. For example: x = {1, 2, 3}; y = {4, 5, 6}; I want to be able to ...
113 views

### DateListPlot input entry problem

I imported some data from Excel and got the following for my date and values: {{{1986, 1, 2, 0, 0, 0.}, 25.56, ""}, {{1986, 1, 3, 0, 0, 0.}, 26., ""} It seems ...
109 views

### NMaximize with matrix input

I defined function f[x_, fixed_] := {...}. Here x is an $M\times N$ matrix. I want to maximize $f$ with respect to $x$. I have ...
54 views

### Animated 3D graphics is low resolution [duplicate]

I'm trying to animate a 3D shape in Mathematica 7. It's working, but the graphics is extremely crude while animated. The resolution gets better if I stop the animation. Is there a way to get a nice ...


text:
The annual Dask user survey is under way and currently accepting responses at dask.org/survey.

This post provides a preview into early results, focusing on anecdotal responses.

## Motivation

The Dask user survey helps developers focus and prioritize our larger efforts.  It’s also a fascinating and rewarding dataset of anecdotal use cases of how people use Dask today.  Thank you to everyone who has participated so far, you make a difference.

The survey is still open, and I encourage people to speak up about their experience.  This blogpost is intended to encourage participation by giving you a sense for how it affects development, and by sharing user stories provided within the survey.

This article skips all of the quantitative data that we collect, and focuses in on direct feedback listed in the final comments.  For a more quantitative analysis see the posts from previous years by Tom at 2020 Dask User Survey Results and  2019 Dask User Survey Results.

In this post we’re going to look at answers to this one question. This was a long-form response field asking “How can Dask Improve?”. Looking through some of the responses we see that a few of them fall into some common themes. I’ve grouped them here.

In each section we’ll include raw responses, followed up with a few comments from me in response.

## Intermediate Documentation

More long-form content about the internals of Dask to understand when things don’t work and why. The “Hacking Dask” tutorial in the Dask 2021 summit was precisely the kind of content I really need, because 90% of my time with Dask is spent not understanding why I’m running out of memory and I feel like I’ve ready all the documentation pages 5 times already (although sometimes I also stumble upon a useful page I’ve never seen before).

There’s also a dearth of documentation of intermediate topics like blockwise in dask.array. (I think I ended up reverse engineering how it worked from docs, GitHub issue comments, reading the code, and black-box reverse engineering with different functions before I finally “got it”.)

Improve documentation and error messages to cover more of the 2nd-level problems that people run into beyond the first-level tutorial examples.

more examples for complex concepts (passing metadata to custom functions, for example). more examples/support for using dask arrays and cupy.

I think the hardest thing about Dask is debugging performance issues with dask delayed and complex mixing of other libraries and not knowing when things are being pickled or not. I am getting better at reading the performance reports, but I think that better documentation and tutorials surrounding understanding the reports would help me greater than new features. For example, make a tutorial that does some non-trivial dask-delayed work (ie not just computing a mean) that is written against best practices and show how the performance improves with each adopted best practice/explain why things were slow with each step. I think there could also be improvements to the performance reports to point out the slowest 5 parts of your code and what lines they are, and possibly relevant docs links.

### Response

I really like this theme.  We now have a solid community of intermediate-advanced Dask users that we should empower.  We usually write materials that target the broad base of beginning users, but maybe we should rethink this a bit.  There is a lot of good potential material that advanced users have around performance and debugging that could be fun to publish.

## Documentation Organization

Documentation website is sometimes confusing to navigate, better separation of API and examples would help. Maybe this can inspire: https://documentation.divio.com/

I actually think Dask’s documentation is pretty good. But the docs could use some reorganizing – it is often difficult to find the relevant APIs. And there is an incredible amount of HPC insider knowledge that is required to launch a typical workflow - right now much of this knowledge is hidden in the github issues (which is great! but more of it could be pushed into the FAQs to make it more accessible).

More detailed documentation and examples. Start to finish examples that do not assume I know very much (about Dask, command line tools, Cloud technologies, Kubernetes, etc.).

I think an easier introduction to delayed/bags and additional examples for more complex use-cases could be helpful.

### Response

We get alternating praise and scorn for our documentation.  We have what I would call excellent reference documentation.  In fact, if anyone wants to build a dynamic distributed task scheduler today I’m going to claim that distributed.dask.org is probably the most comprehensive reference out there.

However, we lack good narrative documentation, which is the concern raised by most of these comments. This is hard to do because Dask is used in so many different user narratives.  It’s challenging to orient the Dask documentation around all of them simultaneously.

I appreciated the direct reference in the first comment to a website with a framework.  In general I’d love to talk to people who lay out documentation semi-professionally and learn more.

## Functionality

Here is a soup of various feature requests, there are a few themes among them

Have a better pandas support (like multi-index), which can help me migrate my existing code to Dask.

I’d like to see better support for actors. I think having a remote object is a common use case.

Improve Dataframes - multi index!! More feature parity with Pandas API.

Maybe a little less machine learning, more “classical” big data applications (CDF, PDEs, particle physics etc.). Not everything is map-reducable.

Better database integration. Re-writing an SQL query in SQL Alchemy can be very impractical. Would also be great if there were better ways to ensure the process didn’t die from misjudging how much memory was needed per chunk.

Better diagnostic tools; what operations are bottlenecking a task graph? Support for multiindex.

I do work that regularly requires sorting a DataFrame by multiple columns. Pandas can do this single-core; H2O and Spark can do this multicore and distributed. But dask cannot sort_values() on multiple columns at all (such as df.sort_values([ "col1", "col2" ,"col3" ], ascending=False)).

Type-hints! It is very tedious using Dask in a huge ML-Application without even having the option to do some static type-checking.

Additionally it is very frustrating that Dask tries to mimic Pandas API, but then 40% of the API doesn’t work (isn’t implemented), or deviates so far from the Pandas API that some parameters aren’t implemented. Only way to find out about that is to read the docs. With some typehints one could mitigate much of this trial-and-error process when switching from Pandas to Dask.

It’s hard to track everything around dask!!! Actors are a bit unloved, but I find them super useful

Type annotations for all methods for better IDE (VSCode) support

I think the Actor model could use a little love

### Response

Interesting trends, not many that I would have expected

• MultiIndex (well, this was expected)
• Actors
• Type hinting for IDE support
• SQL access

## High Level Optimization

Needs better physical data independence. Manual data chunking, memory management, query optimization are all a big hassle. Automate those more.

Dask makes it easy for users with no parallel computing experience to scale up quickly (me), but we have no sense of how to judge our resource needs. It’d be great if Dask had some tools or tutorials that helped me judge the size of my problem (e.g. memory usage). These may already exist, but examples of how to do it may be hard to find.

## Runtime Stability and Advanced Troubleshooting

Stability is the most important factor

I have answered no to the Long Term Support version of dask but often the really great opportunities are those that arre on demand. The problem is that when these fixes are released, their not well advertised and something under the hood has changed. So, it ends up breaking something else or my particular knowledge of the workings are no longer correct. Dask maintainers have a bit of a weird clique and it can feel as a newbie or a learner that your talked down to or in reality. They don’t have the time to help someone. So they should probably have some more maintainers answering some of the more mundane questions via the blog or via some other method, Things we have seen people do wrong or having difficulty in . A bit of basic, a bit of intermediate and a bit of advanced. If the underlying dask API has changed, then these should be updated with new posts with updates of what has changed. Showing a breakdown of doing it the hard way. So people can see what is done step by step with standard workflows that work. Then vs dask, with less boilerplate and/or speed improvement. If there are places where speed isn’t improved. Show that the difference of where it doesnt work alongside the workflow where it might.

We have long deployed dask clusters (weeks to months) and have noticed that they sometimes go into a wonky state. We’ve been unable to identify root cause(s). Redeployment is simple and easy when it does occur, but slightly annoying nonetheless.

My biggest pain point is the scheduler, as I tend to spend time writing infrastructure to manage the scheduler and breaking apart / rewriting tasks graphs to minimize impact on the scheduler.

As my answers make clear (and from previous conversations with Matt, James, and Genevieve) the biggest improvement I’d like to see is stable releases. Stable from both a runtime point of view (i.e. rock solid Dask distributed), and from an API point of view (so I don’t have to fix my code every couple of weeks). So a big +1 to LTS releases.

Better error handling/descriptions of errors, better interoperability between (slightly) different versions

If something goes wrong (in Dask, the batch system, or the interaction between Dask and the batch system), the problem is very opaque and difficult to diagnose. Dask needs significant additional documentation, and probably additional features, to make debugging easier and more transparent.

Better ways of getting out logs of worker memory usage, especially after dask crashes/failures. Ways of getting performance reports written to log files, rather than html files which don’t write if the dask client process fails.

Two big problems for me are when dask fails determining what when wrong and how to fix it.

### Response

Stability definitely took a dive last December.  I’m feeling good right now though.  There is a lot of good work that should be merged in and released in the next few weeks that I think will significantly improve many of the common pain points.

However, there are still many significant improvements yet to be made.  I in particular like the theme above in reporting and logging when things fail.  We’re ok at this today, but there is a lot of room for growth.

## What’s Next?

Do the views above fully express your thoughts on where Dask should go, or is there something missing?

Share your perspective at dask.org/survey.  The whole process should take less than five minutes.


text:
# Derive a trainable model¶

Documentation in this section describes one of the possible ways to turn a DL model for inference into one that can be used for training.

Additionally, and to provide a more complete walk-through that also trains the model, our example includes the use of a simple data loader for uncompressed MNIST data.

## Automating graph construction¶

In a Machine Learning ecosystem, it makes sense to use automation and abstraction where possible. nGraph was designed to automatically use the “ops” of tensors provided by a framework when constructing graphs. However, nGraph’s graph-construction API operates at a fundamentally lower level than a typical framework’s API, and writing a model directly in nGraph would be somewhat akin to programming in assembly language: not impossible, but not the easiest thing for humans to do.

To make the task easier for developers who need to customize the “automatic”, construction of graphs, we’ve provided some demonstration code for how this could be done. We know, for example, that a trainable model can be derived from any graph that has been constructed with weight-based updates.

The following example named mnist_mlp.cpp represents a hand-designed inference model being converted to a model that can be trained with nGraph.

## Model overview¶

Due to the lower-level nature of the graph-construction API, the example we’ve selected to document here is a relatively simple model: a fully-connected topology with one hidden layer followed by Softmax.

Remember that in nGraph, the graph is stateless; values for the weights must be provided as parameters along with the normal inputs. Starting with the graph for inference, we will use it to create a graph for training. The training function will return tensors for the updated weights.

Note

This example illustrates how to convert an inference model into one that can be trained. Depending on the framework, bridge code may do something similar, or the framework might do this operation itself. Here we do the conversion with nGraph because the computation for training a model is significantly larger than for inference, and doing the conversion manually is tedious and error-prone.

## Code structure¶

### Inference¶

We begin by building the graph, starting with the input parameter X. We also define a fully-connected layer, including parameters for weights and bias:

    // Layer 0
auto W0 = std::make_shared<op::Parameter>(element::f32,
Shape{input_size, l0_size});
auto b0 =
std::make_shared<op::Parameter>(element::f32, Shape{l0_size});
auto l0_dot = std::make_shared<op::Dot>(X, W0, 1);
b0, Shape{batch_size, l0_size}, AxisSet{0});

Repeat the process for the next layer,

    // Layer 1
auto W1 = std::make_shared<op::Parameter>(element::f32,
Shape{l0_size, l1_size});
auto b1 =
std::make_shared<op::Parameter>(element::f32, Shape{l1_size});
auto l1_dot = std::make_shared<op::Dot>(l0, W1, 1);
b1, Shape{batch_size, l1_size}, AxisSet{0});
auto l1 = l1_dot + b1_broadcast;

and normalize everything with a softmax.

    // Softmax
auto softmax = std::make_shared<op::Softmax>(l1, AxisSet{1});

### Loss¶

We use cross-entropy to compute the loss. nGraph does not currenty have a core op for cross-entropy, so we implement it directly, adding clipping to prevent underflow.

    auto labels =
std::make_shared<op::OneHot>(Y, Shape{batch_size, output_size}, 1);
auto softmax_clip_value = std::make_shared<op::Constant>(
element::f32, Shape{}, std::vector<float>{log_min});
softmax_clip_value, Shape{batch_size, output_size}, AxisSet{0, 1});
auto softmax_clip =
auto softmax_log = std::make_shared<op::Log>(softmax_clip);
auto prod = std::make_shared<op::Multiply>(softmax_log, labels);
auto N = std::make_shared<op::Parameter>(element::f32, Shape{});
auto loss = std::make_shared<op::Divide>(
std::make_shared<op::Sum>(prod, AxisSet{0, 1}), N);

### Backprop¶

We want to reduce the loss by adjusting the weights. We compute the adjustments using the reverse-mode autodiff algorithm, commonly referred to as “backprop” because of the way it is implemented in interpreted frameworks. In nGraph, we augment the loss computation with computations for the weight adjustments. This allows the calculations for the adjustments to be further optimized.

    // Each of W0, b0, W1, and b1
auto learning_rate =
std::make_shared<op::Parameter>(element::f32, Shape{});
auto delta = -learning_rate * loss;

For any node N, if the update for loss is delta, the update computation for N will be given by the node

auto update = loss->backprop_node(N, delta);

    auto W0_next = W0 + adjoints.backprop_node(W0);
auto b0_next = b0 + adjoints.backprop_node(b0);
auto W1_next = W1 + adjoints.backprop_node(W1);
auto b1_next = b1 + adjoints.backprop_node(b1);

The different update nodes will share intermediate computations. So to get the updated values for the weights as computed with the specified backend:

    // Get the backend
auto backend = runtime::Backend::create("CPU");

// Allocate and randomly initialize variables
auto t_W0 = make_output_tensor(backend, W0, 0);
auto t_b0 = make_output_tensor(backend, b0, 0);
auto t_W1 = make_output_tensor(backend, W1, 0);
auto t_b1 = make_output_tensor(backend, b1, 0);

std::function<float()> rand(
std::bind(std::uniform_real_distribution<float>(-1.0f, 1.0f),
std::default_random_engine(0)));
randomize(rand, t_W0);
randomize(rand, t_b0);
randomize(rand, t_W1);
randomize(rand, t_b1);

// Allocate inputs
auto t_X = make_output_tensor(backend, X, 0);
auto t_Y = make_output_tensor(backend, Y, 0);

auto t_learning_rate = make_output_tensor(backend, learning_rate, 0);
auto t_N = make_output_tensor(backend, N, 0);
set_scalar(t_N, static_cast<float>(batch_size), 0);

// Allocate updated variables
auto t_W0_next = make_output_tensor(backend, W0_next, 0);
auto t_b0_next = make_output_tensor(backend, b0_next, 0);
auto t_W1_next = make_output_tensor(backend, W1_next, 0);
auto t_b1_next = make_output_tensor(backend, b1_next, 0);

auto t_loss = make_output_tensor(backend, loss, 0);
auto t_softmax = make_output_tensor(backend, softmax, 0);

### Update¶

Since nGraph is stateless, we train by making a function that has the original weights among its inputs and the updated weights among the results. For training, we’ll also need the labeled training data as inputs, and we’ll return the loss as an additional result. We’ll also want to track how well we are doing; this is a function that returns the loss and has the labeled testing data as input. Although we can use the same nodes in different functions, nGraph currently does not allow the same nodes to be compiled in different functions, so we compile clones of the nodes.

    // Train
// X, Y, learning_rate, W0, b0, W1, b1
//    -> loss, softmax, W0_next, b0_next, W1_next, b1_next
NodeMap train_node_map;
auto train_function = clone_function(
Function(
OutputVector{
loss, softmax, W0_next, b0_next, W1_next, b1_next},
ParameterVector{X, Y, N, learning_rate, W0, b0, W1, b1}),
train_node_map);
auto train_exec = backend->compile(train_function);


text:
Morphisms between supermanifolds R^{0|1}→R^{0|1} - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-26T09:44:22Z http://mathoverflow.net/feeds/question/54927 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/54927/morphisms-between-supermanifolds-r01r01 Morphisms between supermanifolds R^{0|1}→R^{0|1} Ma Ming 2011-02-09T20:54:32Z 2011-08-18T13:46:35Z
I am confused with morphisms of supermanifolds. Take a simple example $f:R^{0|1}\to R^{0|1}$. By (one of) definition, $f$ is a morphism of superalgebras of functions $C(R^{0|1})\to C(R^{0|1})$. Morphisms of superalgebras preserve the grading, I deduced that $f$ have the form $1\mapsto 1, \theta\mapsto x\theta$, i.e. $Hom(R^{0|1}\to R^{0|1})=R^1$ (as a set?). But I read from a paper that $Hom(R^{0|1},R^{0|1})=R^{1|1}$. What is going on? Thanks in advance!
 http://mathoverflow.net/questions/54927/morphisms-between-supermanifolds-r01r01/54959#54959 Answer by Martin O for Morphisms between supermanifolds R^{0|1}→R^{0|1} Martin O 2011-02-09T23:47:12Z 2011-02-10T08:25:43Z
You are right that the set of supermanifold morphisms $Hom(\mathbb R^{0|1},\mathbb R^{0|1})$ to itself is $\mathbb R^1$. However, one can define for supermanifolds $X,Y$ with $\dim X=0|d$ a supermanifold $map(X,Y)$ of morphisms from $X$ to $Y$, by $Hom(Z,map(X,Y))=Hom(Z\times X,Y)$ for all supermanifolds $Z$.

And $map(\mathbb R^{0|1},\mathbb R^{0|1})=\mathbb R^{1|1}$.
 http://mathoverflow.net/questions/54927/morphisms-between-supermanifolds-r01r01/73150#73150 Answer by Alexander Alldridge for Morphisms between supermanifolds R^{0|1}→R^{0|1} Alexander Alldridge 2011-08-18T13:38:23Z 2011-08-18T13:46:35Z
@Ma: As an answer to your following question:

Could you give a clue how to calculate the $map$, for example, $map(R^{0∣d},M)$ for any supermanifold $M$?

Take a look at arXiv:math/0307303, where this question is discussed.

For $d=1$, it is well-known (and due to Kontsevich, I think), that $map(R^{0|1},M)$ is the total space of the odd tangent bundle $\Pi TM$ of $M$.

If $U$ is a superdomain of dimension $p|q$, then $map(R^{0|d},U)=U\times R^{pr+qs|ps+qr}$ where $(r+1)|s=2^{d-1}|2^{d-1}$ is the graded dimension of $\bigwedge R^d$. This you can check using the definition of $map$ and the characterisation of morphisms of supermanifolds as given in Leites.

Another good source on this subject (for $d=1$), is the paper "Differential forms and 0-dimensional supersymmetric field theories" by Hohnhold, Kreck, Stolz and Teichner.