text:
When a given square sparse matrix can be permuted into a lower triangular form?

For some, the question in the title of this post could look trivial. After all, they have been doing LU decomposition in Matlab and using Matlab’s mldivide (or “backslash”) to solve systems with the factor matrices. These are usually done without worrying if the pivoting took place and permuted those factor matrices (Matlab used to call them psychologically triangular matrices. For “why?” and “who said that?”, see here). Because, the help page of mldivide says that it tests if a matrix “is square, is not diagonal, looks triangular, is actually triangular, there are zeros in the diagonal, is a permuted triangular”. So this must be taken care of…

Davis’s “Direct Methods for Sparse Linear Systems” book (a real gem) asks in its Exercise 3.7:

…Consider a matrix $\mathbf{A}$ that may be a permuted upper or lower triangular matrix with both rows and columns permuted by unknown permutations $\mathbf{P}$ and $\mathbf{Q}$. Write an algorithm that determines if the matrix is in this form and, if so, solves $\mathbf{A}x = b$….

Then the book hints an algorithm, which builds the permutation matrices essentially by picking a row with a single nonzero, ordering that row and the associated column, and then by deleting both from the matrix and so on. But this is ok, only if we can recover a full diagonal! What if, at some point, we have rows or columns with no entries at all? The “algorithm” does not handle this case.

It is perhaps ok in the context of LU decomposition, in which case one is warned of about the numerical rank deficiency during LU decomposition (before one attempts to solve the linear systems). But in general it is not ok; at Mathworks, folks are aware of this (see here). If the matrix is not coming from LU decomposition, then we may well be in trouble. We are back to the question: When a given square sparse matrix can be permuted into a lower triangular form?

Some other cases are also easy. If there is a perfect matching in the given matrix, then all standard matching algorithms find it quickly, and after permuting the matching entries to the diagonal, we can check if the matrix is reducible into $1\times 1$ blocks (or the directed graph of $\mathbf{B}=\mathbf{AQ}$ is acyclic, where $\mathbf{Q}$ permutes the columns of $\mathbf{A}$ to have a zero-free diagonal in $\mathbf{B}$). Every step of this is linear time—even computing the matching with the standard tricks). So this case is handled. The question is complicated when we do not have a perfect matching. It is in fact NP-complete to decide if a given square sparse matrix can be permuted into a lower/upper triangular form [1] with unsymmetric permutations.

So writing it once more to emphasize it:

It is easily decidable to test if $\mathbf{A}$ can be symmetrically permuted to a lower/upper triangular form. The directed graph of $\mathbf{A}$ should be acyclic (or $\mathbf{PAP}^T$ is lower/upper triangular).

It is NP-complete to decide if a given square sparse matrix can be permuted to a lower/upper triangular form. Otherwise said, one can find two permutation matrices $\mathbf{P}$ and $\mathbf{Q}$ such that $\mathbf{PAQ}$ is lower/upper triangular only with non-polynomial time algorithms, assuming P$\neq$ NP.

The topic was discussed elsewhere before.

References

1. Guillaume Fertin, Irena Rusu, and Stéphane Vialette:
Obtaining a triangular matrix by independent row-column permutations. ISAAC 2015: 165–175 (doi)

On the degree-1 and degree-2 reduction rules

Karp–Sipser (KS) [5] heuristic is a well-known method to obtain high quality matchings in undirected graphs, bipartite graphs, and hypergraphs.  This heuristic is based on two reduction rules. The first rule says that if there is a vertex with degree one, then we can match that vertex with its unique neighbor and remove both from the graph without any loss.  The second rule says that if there is a vertex $v$ with degree two, then its neighbors can be coalesced, and the vertex $v$ can be discarded. A maximum matching on the reduced graph can be extended to a maximum matching on the original graph. If there is no degree-1 or degree-2 vertices, then a randomly selected edge is used to match two vertices, upon which both of them are removed.

The (full) heuristic with the degree-2 reduction rule turns out to be difficult to analyse. That is why most studies are conserved with the variant with the degree-1 reduction rule. This variant has excellent practical performance [6,7], good theoretical guarantees for certain classes of random graphs [2,5], and can be made to have an approximation ratio around 0.866 [3] for bipartite graphs and a close-by ratio on general graphs [4]. There are graphs for which KS with only the degree-1 reduction can obtain worse results. The following is an example and a table from [3].

The bipartite graph instances giving hard time to KS with the degree-1 rule correspond to the following matrices (rows form one part, and the columns form the other part) . The rows and columns are split into two sets in the middle, yielding a $2\times 2$ structure. The $(1,1)$-block is full, the $(2,2)$-block is empty, and there is an identity matrix at the other two blocks. In order to hide the perfect matching composed of those two identity matrices, additional nonzeros are added to the last $t$ rows in the first row block, and the last $t$ columns in the first column block so that those rows and columns become dense. For $n=3200$, and with different thickness $t\in \{2,4,8,16, 32\}$ in the full rows, KS with only the degree-1 rule obtains the performance shown in the table.

$t$ Performance
2 0.782
4 0.704
8 0.707
16 0.685
32 0.670

We want to now turn attention to the full KS (that is with the degree-1 and degree-2 reduction rules). Anastos and Frieze [1] state in the abstract of a recent arXiv paper:

In a seminal paper on finding large matchings in sparse random graphs, Karp and Sipser (FOCS 1981) proposed two algorithms for this task. The second algorithm has been intensely studied, but due to technical difficulties, the first algorithm has received less attention. Empirical results in the orignal paper suggest that the first algorithm is superior. In this paper we show that this is indeed the case, at least for random cubic graphs. We show that w.h.p. the first algorithm will find a matching of size $n/2-O(\log n)$ on a random cubic graph (indeed on a random graph with degrees in $\{3, 4\}$). We also show that the algorithm can be adapted to find a perfect matching w.h.p. in $O(n)$ time, as opposed to $O(n^{3/2})$ time for the worst-case.

This wonderful result shows improvement with the degree-2 reductions (over using only degree-1 reductions): instead of leaving out $O(n^{1/5})$ vertices as KS with the degree-1 rule only, it leaves out only $\log n$ vertices. We can also create instances for which KS with both reduction rules obtains perfect matchings, whereas that with the degree-1 reduction obtains inferior results. These instances are upper (or lower) Hessenberg matrices, or more sparser versions of it (for example if we discard all but the first and the last subdiagonal nonzeros). A figure is shown below with only two subdiagonal nonzeros. On these instances, an immediate application of the degree-2 reduction triggers a chain of degree-1 reductions, until we have a $2\times 2$ matrix, whose perfect matching is obtained by a degree-2 and then a degree-1 reduction. On the other hand, KS with only the degree-1 rule obtains the performance shown in the table for different $n$ (the performance reported in the table is average of 10 different random runs on the same instance).

$n$ Performance
500 0.828
1000 0.790
5000 0.754

There is a catch though. While there is a linear time, straightforward implementation of the degree-1 rule, the straightforward implementation of the degree-2 rule can be quadratic in the worst case; consider repetitive merges with the same vertex which will happen with an Hessenberg matrix. We can perhaps assume that the worst cases are rare in practice, but nonetheless a worst-case quadratic run time complexity is a lot!

References

1. Michael Anastos and Alan Frieze, Finding perfect matchings in random cubic graphs in linear time, arXiv preprint arXiv:1808.00825, Nov., 2018. (url)
2. Jonathan Aronson, Alan Frieze, and Boris G. Pittel, Maximum matchings in sparse random graphs: Karp-Sipser revisited, Random Structures & Algorithms, 12 (1998), pp. 111-177.
3. Fanny Dufossé, Kamer Kaya, and Bora Uçar, Two approximation algorithms for bipartite matching on multicore architectures, Journal of Parallel and Distributed Computing, 85 (2015), pp. 62–78. (doi)
4. Fanny Dufossé, Kamer Kaya, Ioannis Panagiotas, and Bora Uçar, Approximation algorithms for maximum matchings in undirected graphs, Proceedings of the Seventh SIAM Workshop on Combinatorial Scientific Computing, Bergen, Norway, 2018, pp. 56–65. (doi)
5. Richard M. Karp and Michael Sipser, Maximum matching in sparse random graphs, 22nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), 1981, pp. 364–375. (doi)
6. Johannes Langguth, Fredrik Manne, and Peter Sanders, Heuristic initialization for bipartite matching problems, Journal of Experimental Algorithmics, 15 (2010), pp. 1.1–1.22. (doi)
7. Jakob Magun, Greedy matching algorithms, an experimental study, Journal of Experimental Algorithmics, 3 (1998). (doi)

9 November 2018

Today was a great day at the school. There were two remarkable events. The first one is the 30th anniversary of the lab LIP at ENS Lyon (here is the program). The second was that the ENS Lyon awarded Marc Snir with an honorary doctorate degree (Docteur Honoris Causa). The page announcing this event is in French and google translate does a good job in translating it to English. Yves Robert had slides for introducing Marc during the event.

Many of us know Marc (ever heard of the MPI standard and the book “MPI: The complete reference“). His work span complexity theory, to MPI standard, to parallel computing systems. And oh, he speaks French.

I was lucky to see his talk during the 30th anniversary of the LIP (but unlucky to miss the ceremony of Docteur Honoris Causa). He gave an overview of his involvement with building parallel machines: BlueGene, Blue Waters, SP/Vulcan, and others. His talk has many whimsical observations. Here are some:

• A supercomputer research prototype is an oxymoron.
• A supercomputer research design is either boring or unpractical.
• The main contribution [of all the supercomputer design projects]: The projects educated a generation of researchers.
• Theory informs practice, but should not be taken literally.

After stating

Often theory follows practice, rather than practice following theory

he discussed how his paper with Upfal and Felperin was motivated by Vulcan’s practically well behaving design of $\log N + O(1)$ stages. Back then, the theory demonstrated $2\log N$ stages to avoid worst cases. The cited paper shows $\log N + \log\log N$, where the extra term is $O(1)$ for practical purposes.

After the talk, I wondered which computer he helped to build was his favorite. He said, more or less,

I created them, so all are my favorite !

References

Eli Upfal, Sergio Felperin, and Marc Snir, Randomized routing with shorter paths, IEEE Transactions on Parallel and Distributed Systems, 7(4), pp. 356–362, 1996. (doi)

After CSC18

It has been long time we last blogged, due to Bora’s other professional engagements. There has been many things in between, including the 8th SIAM Workshop on CSC (CSC18), June 6–8, 2018, Bergen, Norway. The best paper of CSC18 by Kevin Deweese and John R. Gilbert, entitled Evolving Difficult Graphs for Laplacian Solvers is our subject.

Kevin is currently a PhD student at the University of California,  Santa Barbara, working on provably fast Laplacian solvers. See his web page for a few of his papers with experimental evaluation (most of the similar solvers are hard to implement).

Here is the abstract of the subject paper (Link to paper) by Kevin and John:

We seek to discover Laplacian linear systems that stress the ability of existing Laplacian solver packages to solve them efficiently. We employ a genetic algorithm to explore the problem space of graphs of fixed size and edge density. The goal is to measure the gap between theoretical and existing Laplacian solvers, by trying to find worst case example graphs for existing solvers. These problems may have little use inside any real world application, but they give great insight into solver behavior. We report performance results of our genetic algorithm, and explore the properties of the evolved graphs.

Kevin and John focus on the combinatorial solver by Kelner, Orecchia, Sidford, and Zhu (arXiv link) known as KOSZ on the provably fast solver side, and PCG with a Jacobi preconditioner on the traditional side. The genetic algorithms by Kevin and John create populations of graphs by starting with an initial population. Then, a Laplacian solver is run on all graphs and those which required the most work to solve are selected as parents. A random vertex is swapped between the selected parents to yield new individuals. Random edge mutations of the form edge removal and replacement are performed. The techniques are versatile: they are used for creating hard instances for KOSZ and PCG; they are also used to create instances in which the performance of KOSZ with respect to that of PCG varies. On a reported instance, KOSZ outperforms PCG by a factor of 2, and on another one PCG outperforms KOSZ by a factor of 140! In all experiments, the performance is measured in terms of the number of arithmetic operations. Future work includes combining different instances to yield larger problems which stress both solvers to understand our abilities (beware solvers!).

Recent news on the minimum fill-in problem

We have just seen a a paper in the Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2017. The proceedings is available online for the curious. A paper from the proceedings is the subject of this post.

Minimum fill-in: Inapproximability and almost tight lower bounds,
by, Yixin Cao and R. B. Sandeep (url).

The minimum fill-in problem is one of the core problems in sparse direct methods. This problem is NP-complete [6]. The NP-completeness of the problem was first conjectured to be true in 1976 by Rose, Tarjan, and Lueker [5] in terms of the elimination process on undirected graphs. Then Rose and Tarjan [4] proved in 1978 that finding an elimination ordering on a directed graph that gives minimum fill-in is NP-complete (there was apparently a glitch in the proof which was rectified by Gilbert [1] two years later). Finally, Yannakakis [6] proved the NP-completeness of the minimum fill-in problem on undirected graphs in 1981.

The sparse matrix community needs a heuristic to tackle the minimum fill-in problem, as direct methods are used in many applications. There are quite efficient and effective heuristics for this purpose, which are variants of the approximate minimum degree and incomplete nested dissection algorithms. These heuristics are efficiently implemented in programs that are wide spread. The mentioned heuristics do not have any performance guarantees (except for classes of graphs such as graphs with good separators) but they are very-well established. So there is an NP-complete problem, practitioners have some heuristics and are happy with what they have.

On the other hand, the minimum fill-in problem poses many challenges to the theoreticians. Natanzon, Shamir, and Sharan [2] obtained an algorithm that approximates the minimum fill-in ($k$) by bounding the fill by $8k^2$ in $O(k n^3)$ time, for a graph with $n$ vertices. The paper by Cao and Sandeep shows that unless P=NP, there is no polynomial time approximation scheme (PTAS) for the minimum fill-in problem. A PTAS is an algorithm which takes an instance of an optimization problem and a parameter $\epsilon > 0$ and, in polynomial time, produces a solution that is within a factor $1 + \epsilon$ of the optimum. This is a bad news in a way: no simple heuristic with a performance guarantee for theoretically oriented practitioners is in view.

The paper by Cao and Sandeep contains two other theorems, ruling out algorithms with approximation $1+\epsilon$ and with a running time $2^{O(n^{1-\delta})}$, and exact algorithms with running time in $2^{O(k^{1/2-\delta})}\cdot n^{O(1)}$, assuming exponential time hypothesis (ETH). Here $n$ is again the number of vertices, $k$ is an integer parameterizing the fill-in, and $\delta$ is a small positive constant. ETH posits that the satisfiability problem with at most three variables per clause cannot be solved in $2^{o(p+q)}$ time, where $p$ and $q$ denote the number of clauses and variables, respectively, in the problem.

If you are interested in these problems, then see the tree-width and minimum fill-in challenges. The minimum tree-width is related to the shortest elimination tree over all elimination orderings of an undirected graph, which one of us had proved to be NP-complete [3].

References

1. John R. Gilbert, A note on the NP-completeness of vertex elimination on directed graphs, SIAM Journal on Algebraic and Discrete Methods, 1 (1980), pp. 292–294 (link).
2. Assaf Natanzon, Ron Shamir, and Roded Sharan, A polynomial approximation for the minimum fill-in problem, SIAM Journal on Computing, 30, (2000), pp. 1067–1079 (link).
3. Alex Pothen, The complexity of optimal elimination trees,
Tech. Report, Department of Computer Science, Penn State University, 1988 (link).
4. Donald J. Rose and Robert E. Tarjan, Algorithmic aspects of vertex elimination in directed graphs, SIAM Journal on Applied Mathematics, 34 (1978), pp. 176–197 (link).
5. Donald J. Rose, Robert E. Tarjan, and George S. Lueker, Algorithmic aspects of vertex elimination on graphs, SIAM Journal on Computing, 5 (1976), pp. 266–283 (link).
6. Mihalis Yannakakis, Computing the minimum fill-in is NP-complete, SIAM Journal on Algebraic and Discrete Methods, 2 (1981), pp. 77–79 (link).

After CSC’16 (cont’): The best paper

Now that the Proceedings of the CSC Workshop 2016 has appeared (link), we can look at the papers. In this post, we are going to look at the best paper by Manne, Naim, Lerring, and Halappanavar, “On stable marriages and greedy matchings” (doi).

As noted in the citation of the award, this paper brings together  recent half-approximation algorithms  for  weighted matchings  and the classical  Gale-Shapley and McVitie-Wilson algorithms for the Stable Marriage problem. This is helpful in two ways.

First, the authors show that a  recent half-approximation algorithm for computing greedy matchings, the Suitor algorithm and its variants,  is equivalent to  the classical algorithms for the Stable Marriage problem. This correspondence enables the authors to propose multi-core and many-core parallel algorithms for the Stable Marriage problem, based on the greedy matching algorithms. This way, if I am not mistaken, they develop the first GPU algorithm for the Stable Marriage problem.

Second, the extensive theoretical work on the Stable Marriage algorithms  explains the  behavior of the Suitor matching algorithm. The worst-case number of proposals in the Suitor algorithm can be $O(n^2)$,  where n is the number of vertices  in the bipartite graph. However, if the weights are assigned randomly, the expected number of proposals is $O(n \log n)$, which follows from a classical analysis of Donald Knuth [1, 2].

This work represents a nice marriage between theory and practice: the practical algorithms for the greedy matching help in designing parallel algorithms for the Stable Marriage problem, and the theoretical understanding of the Stable Marriage problem sheds light into the behavior of the greedy weighted matching algorithms.

Vocabulary

Stable marriage problem: This is described on a full bipartite graph $G=(L\cup R, L\times R)$.  Each vertex on the left has a total ranking of the vertices on the right; similarly each vertex on the right has a total ranking of all vertices on the left. The aim is to find a matching $M$ such that no $l\in L$ and $r\in R$  would obtain a higher ranked partner if they were to abandon their current partners in $M$ and rematch with each other.

Greedy matching algorithm: Here we compute approximations to matchings of maximum  weight in weighted graphs. The Greedy algorithm  considers edges in a non-increasing order of weights and the heaviest remaining edge $(u,v)$ is added to the matching, whereupon all edges incident on $u$ and $v$ are removed. The Greedy matching is a half-approximate matching.

Suitor algorithm: This is a proposal based algorithm [3]. Vertices can propose in any order, however, each vertex proposes to a neighbor with the  heaviest weight  that already does not have a better weight offer to match with it.  A vertex could annul the proposal received by a neighbor if it has a better weight edge to offer the neighbor.  When two vertices propose to each other, they are matched. The Suitor algorithm computes the same matching as the one obtained by the Greedy algorithm and the Locally Dominant edge algorithm described by Robert Preis [4]!

References

1. Vicki Knoblauch, Marriage matching: A conjecture of Donald Knuth, Economics Working Papers. Paper 200715, http://digitalcommons.uconn.edu/econ_wpapers/200715, 2007.
2. Donald E. Knuth, Stable Marriage and its Relation to Other Combinatorial Problems, CRM Proceedings and Lecture Notes, Vol. 10 American Mathematical Society, (1997).
3. Fredrik Manne and Mahantesh Halappanavar, New effective multithreaded matching algorithms, in Proc. IPDPS 2014, IEEE 28th International Parallel and Distributed Processing Symposium, Phoenix, AZ, USA, pp. 519–528, 2014.
4. Robert Preis, Linear time $1/2$-approximation algorithm for maximum weighted matching in general graphs, in Proc. STACS 99, 16th Annual Symposium on Theoretical Aspects of Computer Science Trier, Germany, pp. 259–269, 1999.

After CSC16 (cont’)

Umit V. Çatalyürek presented our work on the directed acyclic graph (DAG) partitioning problem. In this problem, we are given a DAG $G=(V,E)$ and an integer $k\geq 2$. The aim is to partition the vertex set $V$ into $k$ parts $V_1,\ldots, V_k$ in such a way that the parts have (almost) equal weight and the sum of the costs of all those arcs having their endpoint in different parts minimized. Vertices can have weights, and the edges can have costs. Up to now, all is standard. What is not standard is that the quotient graph of the parts should be acyclic. In other words, the directed graph $G'=(V', E')$, where $V'=\{V_1,\ldots,V_k\}$ and $V_i\rightarrow V_j\in E'$ iff $v_i\rightarrow v_j\in E$ for some $v_i\in V_i$ and $v_j\in V_j$, should be acyclic.

John R. Gilbert wanted to understand the complexity of the problem, with respect to the undirected version. He is an expert on the subject matter (see, e.g., [2]). He asked what happens if we orient the edges of the $n\times n$ model problem. If you are not familiar with this jargon, it is the $n\times n$ mesh with each node being connected to its immediate neighbor in the four main directions, if those neighbors exist. See the small image for an $8\times 8$ example.

Partitioning these kind of meshes is a very hard problem. Gary Miller had mentioned their optimal partitioning in his invited talk (about something else). Rob Bisseling [Ch. 4, 1] has a great text about partitioning these meshes and their cousins in 3D. I had surveyed known methods in a paper with Anaël Grandjean [3]. In particular, Anaël found about discrete isoperimetric problems, showed that the shape of an optimal partition at a corner, or inside the mesh was discussed in the related literature. He also showed that the Cartesian partitioning is optimal for edge cut.  Anaël also proposed efficient heuristics which produced connected components. See the cited papers for nice images. Our were based on our earlier work with Umit [4].

Anyhow,  let’s return back to acyclic partitioning of DAGs, and John’s question. He suggested that we should look at the electrical spiral heater to get an orientation. This orientation results in a total order of the vertices. The figures below show the ordering of the $8\times 8$ and the $16\times 16$ meshes. Only some of the edges are shown; all edges of the mesh, including those that are not shown are from the lower numbered vertex to the higher numbered one.

As seen in the figures above, the spiral ordering is a total order and there is only one way to cut the meshes into two parts with the same number of vertices; blue and red show the two parts.

Theorem: Consider the $n\times n$ mesh whose edges are oriented following the electrical spiral heater ordering. The unique acyclic cut with $n^2/2$ vertices in each side has $n^2-4n+3$ edges in cut, for $n\geq 8$.

The theorem can be proved by observing that the blue vertices in the border (excluding the corners) has one arc going to a red vertex; those in the interior, except the one labeled $n^2/2$ has 2 such arcs;  the vertex labeled $n^2/2$ has three such arcs. The condition $n\geq 8$ comes from the fact that we assumed that there are blue vertices in the interior of the mesh. This is a lot of edges to cut!

Later, John said that he visited the Maxwell Museum of Anthropology at UNM after the CSC16 workshop, and saw that similar designs by the original native New Mexicans.

References

1. Rob H. Bisseling, Parallel Scientific Computation: A Structured Approach using BSP and MPI, 1st ed, Oxford University Press, 2004.
2. John R. Gilbert, Some nested dissection order is nearly optimal. Inf. Process. Lett. 26(6): 325–328 (1988).
3. Anaël Grandjean and Bora Uçar, On partitioning two dimensional finite difference meshes for distributed memory parallel computers. PDP 2014: 9–16.
4. Bora Uçar and Umit V. Çatalyürek, On the scalability of hypergraph models for sparse matrix partitioning. PDP 2014: 593–600.
5. Da-Lun Wang and Ping Wang, Discrete isoperimetric problems, SIAM Journal on Applied Mathematics, 32(4):860–870 (1977).

After CSC16

CSC16 was held last week. Kudos to Assefaw and Erik as the chair of the workshop.

There are so much to talk about. We will have a series of posts about the workshop and related things. Here are some bits and pieces.

The workshop had three invited talks, 19 contributed talks, and eight posters, and attended by 60+ people. There will be a proceedings with 11 papers. The proceedings will be published by SIAM and will be hosted at its publication platform.

We had also celebrated the 60th birthdays of Alex Pothen and Rob Bisseling.

There was a best paper award. It went to Fredrik Manne, Md. Naim, Håkon Lerring, and Mahantesh Halappanavar for their paper titled On Stable Marriages and Greedy Matching. Congratulations. The citation by the best paper award committee (Uwe Naumann, Alex Pothen, and Sivan Toledo) reads as:

for the way the paper brings together several decades of work on stable marriages with the more recent work on approximation algorithms for weighted matchings, and the consequences for the average case complexity of the latter algorithms.

A heads up: the CSC18 meeting will likely be in Bergen, Norway. Erik cracked a joke about this in saying that the best paper awardees should take on organizing the next meeting.

CSC Mini-symposium at SIAM PP16

SIAM Conference on Parallel Processing for Scientific Computing (PP16) took place in Paris, April 12–15, 2016. This was the first SIAM PP outside the US.

As announced before, we had a mini-symposium on CSC in three sessions. SIAM keeps records of the program, the speakers and the abstracts (here). As the organizers, we thought that we should take this one step ahead and make the pdf’s of the talks available as well, wherever possible.

Here is the list of talks, in the order of speaker line-up.

1. Computational surgery: Visualization with augmented matrices (Alex Pothen)

Authors: Alex Pothen (Purdue University, USA) and Mu Wang (Purdue University, USA)

Abstract. Not yet

Talk: No files yet.

Comments: Alex had a video showcasing the use of the solver, in real-time, updating the mesh and showing the result of the surgery. The video was prepared with the help of professionals. The audience was all captive and silent during the video!

2. Parallel combinatorial algorithms in sparse matrix computation? (Esmond Ng)

Authors: Mathias Jacquelin (Lawrence Berkeley National Laboratory, USA), Esmond Ng (Lawrence Berkeley National Laboratory, USA), Barry Peyton (Dalton State College, USA), Yili Zheng (Lawrence Berkeley National Laboratory, USA), and Kathy Yelick, (Lawrence Berkeley National Laboratory, USA).

Abstract. Combinatorial techniques are used in several phases of sparse matrix computation. For large-scale problems, while numerical phases are often executed in parallel, most of these combinatorial techniques are serial and can become bottlenecks. We are investigating the extent to which some of the combinatorial techniques can be performed in parallel.

Talk: No files yet.

Comments: RCM is discussed as the showcase. I think Aydin and Ariful were also involved (second slide of the talk had this information). Given the group’s experience in distributed memory BFS, it is of surprise that the RCM is implemented based on this. The target was not small-world graphs, neither social network graphs; graphs with large diameters were at the focus. So the parallelization problem is somehow tough. Sorting (by the vertex degrees) is required for a formal RCM (I could not catch the details of which sorting algorithm was used). This step incurred cost and was detrimental to performance. Maybe, in an application one can skip sorting and obtain a variant of RCM (after all, RCM is a heuristic). Also, Esmond pointed that the motivation for this work is that the matrix/graph could be already distributed in another context. Instead of collecting the global data to a central processor, solving it there, and distributing the result back to everyone, one could possibly solve the problem in parallel. In RCM,  pseudo-peripheral nodes are used traditionally. They are again found by BFS. There are recent work for finding the diameters in graphs with a few rounds of BFS. Maybe review this.

3. Parallel graph matching algorithms using matrix algebra (Ariful Azad)

Authors: Ariful Azad (Lawrence Berkeley National Laboratory, USA) and Aydin Buluç (Lawrence Berkeley National Laboratory, USA).

Abstract. We present distributed-memory parallel algorithms for computing matchings in bipartite graphs. We consider both exact and approximate algorithms for cardinality and weighted matching problems. We substitute the asynchronous data access patterns of traditional matching algorithms by a small subset of more structured, bulk-synchronous functions based on matrix algebra. Relying on communication-avoiding algorithms for the underlying matrix-algebric modules, different matching algorithms achieve good speedups on tens of thousands of cores on current supercomputers.

4. On the Birkhoff–von Neumann decomposition (Bora Uçar)

Authors: Michele Benzi (Emory University, USA), Fanny Dufossé (Inria Lille-Nord Europe, France),  Kamer Kaya (Sabanci University, Turkey), Alex Pothen (Purdue University, USA), and Bora Uçar (CNRS and ENS Lyon, France).

Abstract. Not yet

Talk: (boraUcar-pp16) file.

5. A Partitioning problem for load balancing and reducing communication from the field of quantum chemistry (Edmond Chow)

Authors: Edmond Chow (Georgia Institute of Technology, USA)

Abstract. We present a combinatorial problem and potential solutions arising in parallel computational chemistry. The Hartree-Fock (HF) method has a very complex data access pattern. Much research has been devoted over 20 years for parallelizing this important method, based primarily on intuition and experience. A formal approach for parallelizing HF while reducing communication may come from graph and hypergraph partitioning. Besides providing a potential solution, this approach may also shed light on the optimality of existing approaches.

Talk: (edmondChow-pp16) file.

6. Community detection on GPU (Fredrik Manne)

Authors: Md Naim (University of Bergen, Norway) and Fredrik Manne (University of Bergen, Norway,)

Abstract. There has been considerable interest in community detection for finding the modularity structure in real world data. Such data sets can arise from social networks as well as various scientific domains. The Louvain method is one popular method for this problem as it is simple and fast. It can also be used to detect hierarchical structures in the data. However, its inherently sequential nature and cache unfriendly workloads makes it difficult to parallelize. This is particularly true for co-processor architectures. In this work we show how these obstacles can be overcome and present results from implementing the algorithm on a GPU.

Talk: (fredrikManne-pp16) file.

Comments: Md Naim could not attend to the conference (dommage), and Fredrik replaced him.

7. Scalable parallel algorithms for de novo assembly of complex genomes (Evangelos Georganas)

Authors: Evangelos Georganas (University of California, Berkeley, USA)

Abstract. A critical problem for computational genomics is the problem of de novo genome assembly: the development of robust scalable methods for transforming short randomly sampled sequences into the contiguous and accurate reconstruction of complex genomes. While advanced methods exist for assembling the small and haploid genomes of prokaryotes, the genomes of eukaryotes are more complex. We address this challenge head on by developing HipMer, an end-to-end high performance de novo assembler designed to scale to massive concurrencies. HipMer employs an efficient Unified Parallel C (UPC) implementation and computes the assembly of the human genome in only 8.4 minutes using 15,360 cores of a Cray XC30 system.

Talk: (evangelosGeorganas-pp16) file.

8. Faster and more scalable sparse matrix-matrix multiplication (Aydin Buluç)

Authors: Aydin Buluç (Lawrence Berkeley National Laboratory, USA)

Abstract. We present a faster and more scalable implementation of the sparse matrix-matrix multiplication (SpGEMM) kernel. The implementation exploits multiple levels of parallelism, using a scalable three-dimensional algorithm for inter-node parallelism and multithreaded subroutines for intra-node parallelism. The three-dimensional formalism has characteristics that are special for the sparse case, which we thoroughly explain. We then provide results on applications in Markov graph clustering and Algebraic Multigrid based graph coarsening.

Talk: (aydinBuluc-pp16) file.

9. Directed graph partitioning (Umit V. Catalyurek)

Authors: Julien Herrmann (The Ohio State University, USA), Umit V. Catalyurek (The Ohio State University, USA), Kamer Kaya (Sabanci University, Turkey), and Bora Uçar (CNRS and ENS Lyon, France).

Abstract. In scientific computing directed graphs are commonly used for modeling dependencies among entities. However, while modeling some of the problems as graph partitioning problems, directionality is generally ignored. Accurate modeling of some of the problems necessitates to take the directionally into account, which adds additional constraints that cannot be easily addressed in the current state-of-the-art partitioning methods and tools. In this talk, we will discuss some example problems, models and potential solution approaches for them.

Talk: (pdf) file.

10. Parallel approximation algorithms for b-Edge Covers and data privacy (Arif Khan)

Authors: Arif Khan (Purdue University, USA), and Alex Pothen (Purdue University, USA).

Abstract. We propose a new 3/2-approximation algorithm, called LSE for computing $b$-Edge Cover and its application to a data privacy problem called adaptive $latex k$-Anonymity. $b$-Edge Cover is a special case of the well-known  Set Multicover problem and also a generalization of Edge Cover problem in graphs. The objective is to choose a subset of $latex C$ edges in the graph with weights on the edges, such that at least a specified number $latex b(v)$ of edges in $latex C$ are incident on each vertex $latex v$ and the sum of edge weights is minimized. We implement the algorithm on serial and shared-memory parallel processors and compare its performance against a collection of inherently sequential approximation algorithms that have been proposed for the Set Multicover problem. With LSE, i) we propose the first shared-memory parallel algorithm for the adaptive $latex k$-Anonymity problem and ii) give new theoretical results regarding privacy guarantees which are significantly stronger than the best known previous results.

Talk: (arifKhan-pp16) file.

11. Clustering sparse matrices with information from both numerical values and pattern (Daniel Ruiz)

Authors: Iain S. Duff (Science & Technology Facilities Council, United Kingdom and CERFACS, Toulouse, France), Philip Knight (University of Strathclyde, United Kingdom), Sandrine Mouysset (Université de Toulouse, France), Daniel Ruiz (ENSEEIHT, France), and Bora Uçar (CNRS and ENS Lyon, France).

Abstract. Considering any square fully indecomposable matrix $A$, we can apply a two-sided diagonal scaling to $latex |A|$ to render it into doubly stochastic form. The Perron-Frobenius theorem is a key tool to exploit and we aim to use spectral properties of doubly stochastic matrices to reveal hidden block structure in matrices. We also combine this with classical graph analysis techniques to design partitioning algorithms for large sparse matrices based on both numerical values and pattern information.

Talk: (danielRuiz-pp16) file.

12. Parallel graph coloring on manycore architectures (Mehmet Deveci)

Authors: Mehmet Deveci (Sandia National Laboratories, USA), Erik Boman (Sandia National Laboratories, USA), and Siva Rajamanickam (Sandia National Laboratories, USA).

Abstract. In scientific computing, the problem of finding sets of independent tasks is usually addressed with graph coloring. We study performance portable graph coloring algorithms for many-core architectures. We propose a novel edge-based algorithm and enhancements of the speculative Gebremedhin-Manne algorithm that exploit architectures. We show superior quality and execution time of the proposed algorithms on GPUs and Xeon Phi compared to previous work. We present effects of coloring on applications such as Gauss-Seidel preconditioned solvers.

Talk: (mehmetDeveci-pp16) file.

On HPC Days in Lyon

Last week (6–8 April, 2016) we had an incredible meeting called HPC Days in Lyon. This three day event featured only invited long talks and invited mini-symposia talks. The meeting was organized with generous support of Labex MILYON.

Rob Bisseling and Alex Pothen contributed to a mini-symposium on combinatorial scientific computing.

Rob talked about hypergraph partitioning and how to use it with an iterative solver. We usually get this question: how many mat-vecs (or iterations in a solver) one needs to perform to offset the use of hypergraph partitioning. Rob’s main point in this talk was that one can estimate the number of iterations and spend some more time partitioning the hypergraph, if the number of iterations allow it. He has an ongoing project of optimally bisecting sparse matrices (see the link); his talk included updates (theoretical and practical) to this project. He says he adds a matrix a day to this page. As of now, there are 263 matrices. Chapeau! as the French say.

Also, he said (well maybe slipped out after a few glasses of Côtes du Rhône) that the new edition of his book (Parallel Scientific Computation: A Structured Approach using BSP and MPI) will be coming out.  There are new materials; in particular a few sections on sorting algorithms and a complete chapter on graph algorithms (mainly matching). Stay tuned! Rob will be at SIAM PP next week. I will try to get more  information about his book.

[I have just realized that I did not put Alex’s photo anywhere yet. So let’s have his face too.]

Alex discussed approximation algorithms to matching and $b$-matching problems. He took up the challenge of designing parallel algorithms for matching problems, where the concurrency is usually limited. He discussed approximation algorithms with provable guarantees and great parallel performance for the $b$-matching and a related edge cover problem. He also discussed an application of these algorithms in a data privacy problem he has been working on.

Alex arrived earlier to Lyon and we did some work. With Alex, we always end up discussing matching problems. This was not exception. We looked at the foundations of bottleneck matching algorithms. Alex and I will be attending SIAM PP16 next week. If you know/like these algorithms, please attend CSC mini-symposia so that we can talk.

The talk was for 90 minutes, without break! His talk was very engaging and illuminating. I enjoyed very much and appreciated how he communicates deep math to innocent (or ignorant;)) computer scientists. His two books Iterative methods for sparse linear systems (2nd edition) and Numerical Methods for Large Eigenvalue Problems (2nd Edition) are available at his web page and attest this.
Here is a crash course on Krylov subspace methods from his talk.

Let $x_0$ be an initial guess and $r_0=b-Ax_0$ be the initial residual.
Define $K_m=\textrm{span}\{r_0, Ar_0,\ldots,A^{m-1}r_0\}$ and $L_m$ another subspace of dimension $m$.
Basic Krylov step is then:
$x_m=x_0 + \delta$ where $\delta\in K_m$ and $b-Ax_m \perp L_m$.

At this point, the reader/listener gets the principle and starts wondering what are the choices of $L_m$ that make sense? How do I keep all $m$ vectors? How do I get something orthogonal to them? Yousef had another slide:

1. $L_m=K_m$; class of Galerkin or orthogonal projection methods (e.g., CG), where $\|x^*-\tilde{x}\|=\min_{z\in K_m}\|x^*-z\|_{A}.$
2. $L_m=AK_m$; class of minimal residual methods (e.g., ORTHOMIN, GMRES) where $\|b-A\tilde{x}\|_2=\min_{z\in K_m}\|b-Az\|_2$.

So we learned the alternatives for $L_m$, and we probably guessed correctly that we do not need to keep all $m$ vectors in all cases (e.g., CG), sometimes need all (e.g., GMRES without restart), and even if we need we can short-cut and restart. Getting orthogonal vectors could be tougher, especially if we do not store all the $m$ vectors. Now that we have a guide, a feeling, and a few questions we can turn to resources to study.


text:
# Index of /tex-archive/fonts/cmll

Parent Directory  -
cmll.dtx20-Apr-2010 15:48 13K
cmll.ins20-Apr-2010 15:48 367
cmll.map20-Apr-2010 15:48 954
cmll.pdf20-Apr-2010 15:48 105K
install.sh20-Apr-2010 15:48 789
latex/20-Apr-2010 21:30 -
mf/20-Apr-2010 21:30 -
tfm/20-Apr-2010 21:30 -
type1/20-Apr-2010 21:31 -

```This directory contains the CMLL font. This font contains a handful of symbols
used in the linear logic coommunity, designed for use with standard Computer
Modern and AMS Euler fonts.

This package is dated April 20, 2010.

Installation
------------

* Using packages

CMLL is part of reasonable TeX distributions (including TeXLive and MikteX).

A Debian package is available at http://iml.univ-mrs.fr/~beffara/soft/, it can
be installed even if an older version of CMLL is installed using one of the
TeXLive packages, and it will have priority over it.

* Using the shell script (for Unix)

Say
./install.sh /usr/share/texmf
Replace "/usr/share/texmf" by the path of the TeX directory structure where
you want to install the files.
You may have to update TeX's databases by running "texhash" or "mktexlsr"
(this is for Kpathsea-based distributions like TeX Live) or a similar command.

* By hand

Copy the .mf files from the "mf" subdirectory somewhere in Metafont's search
path and the .sty and .fd files from the "latex" subdirectory somewhere in
LaTeX's search path.

Call TEXMF the base directory of your installation (on Unix this should be
something like /usr/share/texmf or ~/texmf for a single user installation).
Then copy the directories as follows:
copy "mf" as TEXMF/fonts/source/public/cmll
copy "latex" as TEXMF/tex/latex/cmll
If you want to install the fonts in Type1 format:
copy "type1" as TEXMF/fonts/type1/public/cmll
copy "tfm" as TEXMF/fonts/tfm/public/cmll
copy "cmll.map" as TEXMF/fonts/map/dvips/cmll/cmll.map
You may have to update TeX's databases by running "texhash" or "mktexlsr"
(this is for Kpathsea-based distributions like teTeX) or a similar command.

Usage
-----

When the files are correctly installed, compiling the file cmll.dtx with latex
will produce a documentation for the package, including the list of defined
symbols.

To summarise, just say \usepackage{cmll} to get the extra symbols. Class
options may be used to select a particular variant of the font, see the
documentations for details.

In order to use the Type1 versions, assuming the files are installed as
described above, you need to use the provided file "cmll.map". Please refer to
the documentation of you local installation for that.

Feedback
--------

Any comments and suggestions are welcome, feel free to drop me a note at the

format: plain


text:
# Can you explain remez exchange algorithm?

1. What is the diffeence between w and w cap?

2. What is the meaning of extremals?

3. What does it means to reject p-r superfluous potential...

• hm, that involves solving systems of equations with many unknowns, which is why it's a numerical algorithm and not something you do by hand. What kind of example do you hope for, and how would it differ from the text that you just posted? Aug 3 '21 at 15:17
• Ah sorry, I don't need an example. I edited the post. I just need the explanation of few questions I had above. My teacher has also told me to memorize this algorithm and write in exam. Aug 3 '21 at 15:20
• OK; so re: 2. "extremals" are.. extremals, there's a wikipedia article of "Extremal". Re: 3. Probably defined just half a page before. Re 1.: well, $\omega$ is a variable, and $\overset\frown\omega$ are specific values for $\omega$ as defined in the text you pasted. Aug 3 '21 at 15:22

1. $$\hat{\omega}_k$$ are specific frequencies and $$\omega$$ is a variable.
3. For an optimal filter, you only need $$r+1$$ extremals. The algorithm you state will give more. It's saying to ignore the ones you don't need to find the answer.


text:
# Phase angle operator, Implemention and drawbacks

Let assume we have a signal as:
$\color{blue} {x(t)=M e^{(-\beta.t)} e^{j(\sigma .t+\delta )}}$
By applying phase angle operator we have:
$\color{blue} {Phase[x(t)]=Phase[M e^{-\beta.t} e^{j(\sigma .t+\delta )}]=\sigma.t+\delta}$
I have two questions:
1. How can I implement the Phase angle operator, i.e. Phase, in practice ,like a chip.
2. Does phase angle operator increase the effect of noise in a noisy signal?(for example some operators like derivative operator increases the noise effect in a noisy signal)
Kind Regards

• I guess $\tau$ on the right-hand side should be $t$. If you already have a complex-valued signal (i.e. you don't need to generate an analytic signal from a real-valued signal), then the phase is simply the phase angle of the complex number represented by the signal at a given time $t$. So you basically need to implement atan2. – Matt L. Sep 22 '14 at 13:27
• Yes, I meant to present the time variable by writing $\tau$ However the signal is modified and 't' is substituted now. Also, Thanks for giving the hint of using atan2. Now I have two questions. First, How can I apply it to my signal? is this function within every microcomputer programming tool? Second, Does noise effect increase the error as derivative operator does? thanks @MattL. – Electricman Sep 22 '14 at 13:49

As mentioned in my comment, you need the atan2 function. If it is not implemented in the library you're using, you can implement it yourself quite easily according to this definition. If your signal is $x(t)=x_r(t)+jx_i(t)$, where $x_r(t)$ and $x_i(t)$ are the real and imaginary parts, respectively, then for a given time $t$, the phase is computed as $\phi(t)=\text{atan2}(x_i(t),x_r(t))$.


text:
### Home > CCG > Chapter 1 > Lesson 1.1.2 > Problem1-16

1-16.

Match each table of data below with the most appropriate graph and briefly explain why it matches the data. Homework Help ✎

Time will always be shown on the $x\text{-axis}$.

1. Boiling water cooling down

 Time (min) $0$ $5$ $10$ $15$ $20$ $25$ Temp ($^{\circ}$C) $100$ $89$ $80$ $72$ $65$ $59$

Determine if the $y\text{-values}$ are increasing or decreasing.

Since the numbers for the $y\text{-axis}$ are decreasing, the only graph which fits is Graph $3$.

2. Cost of a phone call

 Time (min) $1$ $2$ $2.5$ $3$ $4$ $5$ $5.3$ $6$ Cost (cents) $55$ $75$ $75$ $95$ $115$ $135$ $135$ $155$

Are the $y\text{-values}$ increasing at a constant rate?

This could be Graph $1$ or Graph $2$, but the table would not contain the point $(0,0)$, so it must be Graph $2$.

3. Growth of a baby in the womb

 Age (months) $1$ $2$ $3$ $4$ $5$ $6$ $7$ $8$ $9$ Length (inches) $0.75$ $1.5$ $3$ $6.4$ $9.6$ $12$ $13.6$ $15.2$ $16.8$

Identify the pattern of how the length increases.

Graph $4$ fits best.


text:
Find a particular solution for the differential equation by the method of undetermined coefficients.

Find a particular solution for the differential equation by the method of undetermined coefficients. $$2y'' - 16y' + 32y = -e^{4x}$$ Also, find the general solution of this equation.

The steps I took to solve this problem,

Find the auxiliary equation which is $2m^2-16m+32=0$ for which the roots are $m_1=4$ and $m_2=4$ so $m=4$ of multiplicity 2.

Solve for a general equation of $y_h(x) = C_1e^{4x}x + C_2e^{4x}$

When I try to find a particular solution by taking the derivates of the right hand side, I get \begin{align} y_p &= Ae^{4x}\\ y_p' &= 4Ae^{4x}\\ y_p'' &= 16Ae^{4x} \end{align} Substituting these values into the left hand side results in $0 = -e^{4x}$ which is not possible. Can someone identify what I am missing?

-

Your problem is $e^{4x}$ is part of your homogeneous solution, which explains why you get $0$ when you try $Ae^{4x}$ as a particular solution.

I would try $Ax^2e^{4x}$ as a particular solution.

Just to show it works, let me show you another way to solve the problem. Let

$$z=y'-4y,z'=y''-4y'$$ $$y''-8y'+16y=-\frac12e^{4x}$$ $$(y'-4y)'-4(y'-4y)=z'-4z=-\frac12e^{4x}$$ $$e^{-4x}z'-4e^{-4x}z=(e^{-4x}z)'=-\frac12$$ $$e^{-4x}z=-\frac12x+k_1,z=-\frac12xe^{4x}+k_1e^{4x}$$ $$y'-4y=-\frac12xe^{4x}+k_1e^{4x}$$ $$e^{-4x}y'-4e^{-4x}y=(e^{-4x}y)'=-\frac12x+k_1$$ $$e^{-4x}y=-\frac14x^2+k_1x+k_2,y=-\frac14x^2e^{4x}+k_1xe^{4x}+k_2e^{4x}$$

So our particular solution turns out to be $-\frac14x^2e^{4x}$

-
Why would we do this? –  Mike Beta Nov 20 '12 at 6:09
We start with a different starting point because a double root does not give us the two Linearly Independent solutions we are looking for. –  Aseem Dua Nov 20 '12 at 6:12
@MikeBeta Often in these kinds of problems, the solution is to multiply by $x$ when one particular solution doesn't work. $xe^{4x}$ is also part of the homogeneous solution, so multiply by $x$ again. If you want to try solving this problem a different way, try making the substitution $z=y'-4y$. It might help you understand. –  Mike Nov 20 '12 at 6:16


text:
# 9th Class Mathematics Mensuration Area of Plane Geometrical Figures

Area of Plane Geometrical Figures

Category : 9th Class

### Area of Plane Geometrical Figures

Area of Plane Figures

The area of a plane figure is the measurement of the surface enclosed by its boundry. In this chapter we will study about different plane figures with its area.

Area of Triangle

Area of $\Delta \text{ABC}=\frac{1}{2}\text{BC}\times \text{AD}$ square unit

Area of right triangle $=\frac{1}{2}\times \text{(perpendicular)}\times \text{Base}$ $=\frac{1}{2}\times AB\times \text{BC}$

Area of Triangle by Heron's Formula

Let a, b, c be the length of sides of a triangle

then area $=\sqrt{s(s-a)(s-b)(s-c)}$sq. unit where $s=-\frac{1}{2}(a+b+c)$

Area of Equilateral Triangle

Area $=\frac{\sqrt{3}}{4}{{(side)}^{2}}=\frac{\sqrt{3}}{4}{{a}^{2}}$ Area of isosceles triangle

$=\frac{1}{2}\times BC\times AD=\frac{1}{4}b\sqrt{4{{a}^{2}}-{{b}^{2}}}$

Find the area of the triangle whose base = 25 cm and height = 10.8 cm.

(a) $\text{125c}{{\text{m}}^{\text{3}}}$

(b) $\text{135c}{{\text{m}}^{\text{2}}}$

(c) $\text{124c}{{\text{m}}^{\text{2}}}$

(d) $\text{199}\,\text{c}{{\text{m}}^{\text{2}}}$

(e) None of these

Explanation

Area of the given triangle

$\text{=}\frac{1}{2}\times \text{base}\times \text{height}=\left( \frac{1}{2}\times \text{25}\times \text{1}0.\text{8} \right)\text{c}{{\text{m}}^{\text{2}}}=\text{135 c}{{\text{m}}^{\text{2}}}$

#### Other Topics

You need to login to perform this action.
You will be redirected in 3 sec


text:
## Interview of Michael Atiyah (aged 86!)

Inspirational interview by Michael Atiyah, winner of both Fields Medal and Abel Prize, currently age 86!

Excerpt from the interview:

Is there one big question that has always guided you?

I always want to try to understand why things work. I’m not interested in getting a formula without knowing what it means. I always try to dig behind the scenes, so if I have a formula, I understand why it’s there. And understanding is a very difficult notion.

People think mathematics begins when you write down a theorem followed by a proof. That’s not the beginning, that’s the end. For me the creative place in mathematics comes before you start to put things down on paper, before you try to write a formula. You picture various things, you turn them over in your mind. You’re trying to create, just as a musician is trying to create music, or a poet. There are no rules laid down. You have to do it your own way. But at the end, just as a composer has to put it down on paper, you have to write things down. But the most important stage is understanding. A proof by itself doesn’t give you understanding. You can have a long proof and no idea at the end of why it works. But to understand why it works, you have to have a kind of gut reaction to the thing. You’ve got to feel it.

Interesting comment that “A proof by itself doesn’t give you understanding. You can have a long proof and no idea at the end of why it works.”. Sometimes, intuitive understanding is needed, along with formal proof.

One example in high school mathematics is proving $\displaystyle \sum_{i=1}^n i^2=\frac 16n(n+1)(2n+1)$. It is possible to prove it by induction without actually understanding how the formula comes about!


text:
# unusual number

An or $\sqrt{n}$ $n$ is an integer with a greatest prime factor exceeding $\sqrt{n}$. For example, the greatest prime factor of 102 is 17, which is greater than 11 (the square root of 102 rounded up to the next higher integer). The first few unusual numbers are 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, 20, 21, 22, 23, 26, 28, 29, 31, 33, 34, 35, 37, 38, 39, 41, 42, 43, 44, 46, 47, etc., listed in A064052 of Sloane’s OEIS. In fact, Donald Knuth and Donald Greene, who coined the term “unusual number,” remark that these numbers occur so frequently they’re not all that unusual. Unusual numbers include all of the prime numbers and many composites. Richard Schroeppel proved in HAKMEM 239 that the probability that a random integer is unusual is $\log 2$ (about 0.69314718).

## References

• 1 Donald Greene & Donald Knuth, Mathematics for the Analysis of Algorithms, 3rd edition. Boston: Birkhäuser (1990): 95 - 98
Title unusual number UnusualNumber 2013-03-22 18:09:43 2013-03-22 18:09:43 PrimeFan (13766) PrimeFan (13766) 4 PrimeFan (13766) Definition msc 11A51


text:
# Light Trapping

The optimum device thickness is not controlled solely by the need to absorb all the light. For example, if the light is not absorbed within a diffusion length of the junction, then the light-generated carriers are lost to recombination. In addition, as discussed in the Voltage Losses Due to Recombination, a thinner solar cell which retains the absorption of the thicker device may have a higher voltage. Consequently, an optimum solar cell structure will typically have "light trapping" in which the optical path length is several times the actual device thickness, where the optical path length of a device refers to the distance that an unabsorbed photon may travel within the device before it escapes out of the device. This is usually defined in terms of device thickness. For example, a solar cell with no light trapping features may have an optical path length of one device thickness, while a solar cell with good light trapping may have an optical path length of 50, indicating that light bounces back and forth within the cell many times.

Light trapping is usually achieved by changing the angle at which light travels in the solar cell by having it be incident on an angled surface. A textured surface will not only reduce reflection as previously described but will also couple light obliquely into the silicon, thus giving a longer optical path length than the physical device thickness. The angle at which light is refracted into the semiconductor material is, according to Snell's Law, as follows:

## Snell's Law

${n}_{1}\mathrm{sin}{\theta }_{1}={n}_{2}\mathrm{sin}{\theta }_{2}$

where θ1 and θ2 are the angles for the light incident on the interface relative to the normal plane of the interface within the mediums with refractive indices n1 and n2 respectively. θ1 and θ2 are shown in the animation below.

Refraction of a ray of light at a dielectric boundary. You can adjust the angle of incidence and see how this affects the angle of the ray transmitted to the second medium by clicking in the right side of the graph and dragging the mouse to change the angle. When n2 has a higher refractive index than n1 the refracted ray is closer to normal than the incident ray.

By rearranging Snell's law above, the angle at which light enters the solar cell (the angle of refracted light) can be calculated:

## Snell's Law (rearranged)

${\theta }_{2}={\mathrm{sin}}^{-1}\left(\frac{{n}_{2}}{{n}_{1}}\mathrm{sin}{\theta }_{1}\right)$

In a textured single crystalline solar cell, the presence of crystallographic planes make the angle θ1 equal to 36° as shown below.

Reflection and transmission of light for a textured silicon solar cell.

The amount of light reflected at an interface is calculated from the fresnel reflection formula. For light polarised in the parrallel to the surface the amount of reflected light is:

## Fresnel Reflection (parrallel)

${R}_{\parallel }=\frac{{\mathrm{tan}}^{2}\left({\theta }_{1}-{\theta }_{2}\right)}{{\mathrm{tan}}^{2}\left({\theta }_{1}+{\theta }_{2}\right)}$

For light polarised perpendicular to the surface the amount reflected is:

## Fresnel Reflection (perpendicular)

${R}_{\perp }=\frac{{\mathrm{sin}}^{2}\left({\theta }_{1}-{\theta }_{2}\right)}{{\mathrm{sin}}^{2}\left({\theta }_{1}+{\theta }_{2}\right)}$

For unpolarised light the reflected amount is the average of the two:

## Fresnel Reflection (plane and perpendicular)

${R}_{T}=\frac{{R}_{\perp }+{R}_{\parallel }}{2}$

Light Trapping Calculator

If light passes from a high refractive index medium to a low refractive index medium, there is the possibility of total internal reflection (TIR). The angle at which this occurs is the critical angle and is found by setting θ2 in Snell's law to 0.

## Snell's Law (Critical Angle)

${\theta }_{1}={\mathrm{sin}}^{-1}\left(\frac{{\eta }_{2}}{{\eta }_{1}}\right)$

Total Internal Reflection Calculator

Using total internal reflection, light can be trapped inside the cell and make multiple passes through the cell, thus allowing even a thin solar cell to maintain a high optical path length.


text:
# Limits of correction for over dispersion with Poisson / binomial data

Reading many help pages, I see that a common way to correct for overdispersion is to fit models using quasibinomial or betabinomial distributions. However, I can't find help concerning how far correction is achieved nor how to be confident that a reliable model has been fitted.

I am interested in mutation data from many genes that fall into 10 ordered classes. Each observation comprises a number of bases surveyed (N) and the number of substitutions observed (S). Overdispersion is great (~22!) because the genes vary considerably in how fast they are evolving. There is also the issue that N also varies a lot from <100 up to >30,000.

I want to test the hypothesis that average substitution rate (S/N) increases with class number. I have tried the following options:

1. (awful!) Ignore the fact the data are binomial, set a minimum N>=1000, and fit a Gaussian model with S/N as the response. Fit is poor, though arguably not dreadful.

2. Use cbind(S, N-S) and fit a model with a quasibinomial error structure. Seems to give a similar answer that avoids the crazily low P-values I get when using family=binomial, but how do I know if the degree of correction is valid?

This seems a relatively simple problem, but I want to make sure the model is fitted properly and is, if anything, conservative.

-
 it is better to set a minimum success and fail counts rather than sample size. It doesn't need to be too high either. Say $min(S,N-S)\geq 10$ should be fine for normal distribution to work well. – probabilityislogic Aug 8 '12 at 21:39 But, even if you do that, you should use a variance-stabilizing transformation, as I said in my response below. That may be an "old tecnology" from the times when generalized linear models where not readily available in software, but it is still a good approach, especially for simple models. If you have many regressors, a GLM might be better, because the parameters are easier to inyetrpret. – kjetil b halvorsen Oct 7 '12 at 17:25

Just one idea: You can use a variance-stabilizing transformation. If you have $X \sim \text{Bin}(n,p)$, then the variance-stabilizing transformation is $Y=\arcsin(\sqrt(x/n))$, and now you can use (possibly weighted, with the differents $n$'s giving the weights) usual linear regression. This is often effective, and the overdispersion is automatically taken care of.


text:
# Why does tension in string become zero when it is at the top most point in a vertical circle?

In the question to find out the minimum speed of a stone fastened to a string at the top most point in a vertical circle, we consider tension $$T$$ to be zero and equate $$mv^2/r$$ to $$mg$$. But isn't it the tension which provides the centripetal force $$(mv^2/r)$$? When we consider this to be zero, how come do we equate centripetal force to gravitational force?

Also, the equation $$T-mg=mv^2/r$$ holds for the top most point. How is this true when we consider $$mv^2/r$$ to be centripetal force whose direction is always towards the center? If this equation holds true, won't this mean that tension is 'pushing' the stone outwards when tension is considered a pulling force?

• Hint: "But isn't it the tension which provides the centripetal force (mv²/r). " This is incorrect. The issue is probably a common misunderstanding of centripetal force. – garyp Aug 26 '19 at 17:13
• The tension does not in general become zero. It becomes zero in the specific case requested by the prompt. – dmckee --- ex-moderator kitten Aug 26 '19 at 17:16
• "How is this true..." It isn't true, because you have a sign wrong in your equation. – alephzero Aug 26 '19 at 21:52

First, some information to motivate my answer.

In circular motion, it is useful to break forces into components: the radial component $$F_r$$ (points towards or away from the center of the circle around which the particle is moving) and the tangential component $$F_\theta$$ (points tangent to the circle around which the particle is moving).

For planar motion, we can derive equations of motion for these components: $$\mathbf a=(\ddot r-r\dot\theta^2)\hat r+(r\ddot\theta+2\dot r\dot\theta)\hat\theta$$ where $$(r,\theta)$$ is the polar coordinate, and a dot above a variable represents a time rate of change (so, for example, $$\dot r$$ is just the time rate of change of $$r$$).

The case you are interested is circular motion, where $$\dot r$$ and $$\ddot r$$ are both $$0$$. Then we have $$\mathbf a=-r\dot\theta^2\hat r+r\ddot\theta\hat\theta$$

Therefore, using Newton's second law and using the relation $$\dot\theta=v/r$$, we have $$F_r=-\frac{mv^2}{r}$$ where the negative sign represents the fact that the net radial force component needs to point towards the center of the circle.

I want to point out to you a key thing in this line of reasoning. Instead of thinking of "which force is 'the centripetal force'?", instead all we need to do is determine all of the radial force components, and then we just set this net radial component equal to $$mv^2/r$$ towards the center of the circle. There is no single "centripetal force" in general.

So now, let's look at your question:

If we are looking at this stone moving in a vertical circle, and if we want to analyze the forces acting on the stone at the top of this circle, we need to consider the radial force components. Well, we know that the entire tension force acts towards the center of the circle, and we know that the weight of the particle acts downwards, which here is also towards the center of the circle. Therefore, based on the argument above it must be that $$-T-mg=-\frac{mv^2}{r}$$

Now, what if we want to think about the minimum speed the stone needs to have at the top of the circle to maintain circular motion? Well, the weight $$mg$$ is constant for our stone, so it must be that the speed $$v$$ determines the tension $$T$$ (or you could argue it is the other way around). Based on our above equation, we have $$v^2=\frac{(T+mg)r}{m}$$ You should convince yourself that based on this equation we can say that the minimum value of $$v$$ must mean that $$T$$ is also at its minimum value. Since the tension force cannot become a force that points away from the circle, it must be that the minimum of $$T$$ is $$0$$. Therefore, to determine the minimum velocity needed at the top of the circle for circular motion to still occur, it must be that $$T=0$$.

As for your second paragraph, you should now be able to see that the equation you have written is incorrect. However, that equation would be correct for looking at the bottom of the circle. But in this case tension cannot be $$0$$ (can you see why based on the information in this answer?).

Based on everything above, I want to specifically address your questions now

But isn't it the tension which provides the centripetal force $$mv^2/r$$?

Tension does always point towards the center of the circle, but this does not mean it is the only force that has a radial component. The weight of the stone also has a radial component (except for at points where the rope is horizontal and the weight is completely tangent to the circle). In general you should start with $$F_r=-mv^2/r$$ and then determine what $$F_r$$ is.

When we consider this to be zero, how come do we equate centripetal force to gravitational force?

Based on the above discussion, it should be obvious that since $$T+mg=mv^2/r$$ at the top of the circle, it must be true that $$T=0$$ means $$mg=mv^2/r$$. This makes sense, because now the only force acting on the stone is gravity, and this force only has a radial component.

Also, the equation $$T−mg=mv^2/r$$ holds for the bottom most point. How is this true when we consider mv2/r to be centripetal force whose direction is always towards the center? If this equation holds true, won't this mean that tension is 'pushing' the stone outwards when tension is considered a pulling force?

I have corrected the statement to correctly say this holds at the bottom of the circle. A better way to view this equation is $$T=mg+mv^2/r$$. This shows that at the bottom of the circle the tension force (still pointing in towards the center of the circle) is actually greater than just the weight of the stone.


text:
When I was an undergrad studying abstract algebra, we used the second edition of Artin and covered groups first and then rings. Fields, vector spaces, and algebras came later, I think.

I remember finding group theory difficult because of the number of concepts (cosets, group actions, &c) and the large amounts of only-slightly-different notations for things like orbits and stabilizers. Another thing I remember pretty clearly is being confused by the different meanings of juxtaposition in different contexts (e.g. $$gHg^{-1}$$ vs $$ghg^{-1}$$ vs $$gX$$ where $$X$$ is a set).

I'm wondering whether there are any books or perhaps courses that don't start with either groups or rings and instead pick something more unusual. I'm not a teacher; my interest in this is entirely theoretical.

Based on this question and this question, it seems like teaching groups or rings first is popular, with rings being firmly in second place.

There are other things though that are perhaps reasonable candidates for an introductory algebraic structure.

• Fields -- there are a few ready examples, $$\mathbb{Q}$$, $$\mathbb{R}$$, $$\mathbb{C}$$, and the finite fields. And there's cool stuff like $$\mathbb{H}$$ if we're willing to consider skew fields.
• Vector spaces -- row/column vectors with matrices as linear maps and some other examples should be familiar from linear algebra, which is usually taught first.
• Lattices -- lattices are reasonably straightfoward (in my opinion)

And there are some other things that are weird, but also perhaps reasonable choices.

• Monoids or semigroups
• Semirings -- rings without negation.
• In the second paragraph of the question, you list difficulties with group theory. It seems to me that the same difficulties afflict fields and vector spaces as well. Jun 23 at 22:48
• @AndreasBlass That's a fair point, but I remember fields and vector spaces being much easier to understand back then and not simply because they were introduced second. I can remove the anecdote if it's extraneous. Jun 23 at 23:26
• you could just take a linear algebra textbook that has a suitable "abstract" viewpoint (general base field, vector spaces) for the first part of the course. In Germany, two semesters of linear algebra are typically studied before abstract algebra. Sep 21 at 21:15

Not sure if this counts for the OP's purpose, but I started with Hungerford's Abstract Algebra: An Introduction. The first 3 chapters go like this:

1. Arithmetic in $$\mathbb Z$$ revisited
2. Congruence in $$\mathbb Z$$ and modular arithmetic (i.e., $$\mathbb Z_n$$)
3. Rings

Etc. The motivating thesis is explicitly laid out in the Preface and a Thematic Table of Contents -- that it's better to go from well-known concepts to more abstract in fairly small gradual steps (i.e., the reverse of OP's experience with Artin).

Ironically, I now look at a book that starts with groups enviously for its brevity and elegance (rings as a combination of two groups plus distribution), but it seems pretty easy to believe that Hungerford's approach is less of a shock-treatment to students.

• Agreed. I have an old abstract algebra textbook in my home library that spends probably half the book discussing $\mathbb Z$ and then uses that platform to motivate the development of groups and rings. Mind you, that presentation is going to bite any student who goes on to study non-commutative groups, but it was probably fine for someone who would never need to go deeper into the topic. Jun 23 at 13:56

A nice example is Paolo Aluffi's Algebra: Chapter 0. The first chapter (40 pages) is Preliminaries: Set theory and categories. Groups and rings follow in the next three chapters.

This book is special as it follows a cathegorically minded viewpoint (in the author's words), which I like very much. According to the introduction, the book is suitable for upper-level undergraduate or beginning graduate courses.


text:
Please use this identifier to cite or link to this item: http://arks.princeton.edu/ark:/88435/dsp01dz010q256
 Title: SILVER RHODIUM OXIDE AND RHODIUM(III) OXIDE AS PHOTOCATALYSTS FOR WATER SPLITTING Authors: Yano, Max Edwin Griffin Advisors: Bocarsly, Andrew Bruce Department: Chemistry Class Year: 2014 Abstract: Environmental degradation and depletion of carbon-based fuels necessitate the development of alternative forms of energy that do not harm the world’s ecosystems or rely on unsustainable resources. Solar power is an attractive option due to its abundance, but it must be paired with a form of energy storage to provide a steady energy output, a vital step to becoming a central part of the world’s infrastructure. One method of meeting this need is to use solar power to drive the dissociation of water to hydrogen and oxygen gases, which can then be burned even when the sun is not out. In this thesis, I describe the synthesis and characterization of silver rhodium oxide (AgRhO$$_{2}$$), a new photocatalyst for water splitting. I expand and improve upon published synthetic methods and find that the material is an effective catalyst for water splitting in neutral or slightly basic aqueous solution. I also investigate the utility of rhodium(III)oxide (Rh$$_{2}$$O$$_{3}$$) for the same application, finding that it too can photochemically split water but suffers from degradation to rhodium(III) hydroxide in the process. This work represents a significant advance by discovering a new photocatalyst for this reaction, as well as furthering the work by my research group to develop delafossite-structured photocatalysts. Extent: 66 pages URI: http://arks.princeton.edu/ark:/88435/dsp01dz010q256 Type of Material: Princeton University Senior Theses Language: en_US Appears in Collections: Chemistry, 1926-2016


text:
# How do you simplify 3sqrt8 + 4sqrt50?

26$\sqrt{2}$
$\sqrt{8}$ is 2$\sqrt{2}$, hence 3$\sqrt{8}$ is 6$\sqrt{2}$
$\sqrt{50}$ is 5$\sqrt{2}$, hence 4$\sqrt{50}$ is 20$\sqrt{2}$
Add both of the to get 26$\sqrt{2}$


text:
(This tutorial follows the $$\text{KL}(q\|p)$$ minimization tutorial.)

We seek to maximize the ELBO, \begin{aligned} \lambda^* &= \arg \max_\lambda \text{ELBO}(\lambda)\\ &=\; \arg \max_\lambda\; \mathbb{E}_{q(\mathbf{z}\;;\;\lambda)} \big[ \log p(\mathbf{x}, \mathbf{z}) - \log q(\mathbf{z}\;;\;\lambda) \big],\end{aligned} using a “black box” algorithm. This means generically inferring the posterior while making few assumptions about the model.

### The score function identity

Gradient descent is a standard approach for optimizing complicated objectives like the ELBO. The idea is to calculate its gradient \begin{aligned} \nabla_\lambda\; \text{ELBO}(\lambda) &= \nabla_\lambda\; \mathbb{E}_{q(\mathbf{z}\;;\;\lambda)} \big[ \log p(\mathbf{x}, \mathbf{z}) - \log q(\mathbf{z}\;;\;\lambda) \big],\end{aligned} and update the current set of parameters proportional to the gradient.

The score function gradient estimator leverages a property of logarithms to write the gradient as \begin{aligned} \nabla_\lambda\; \text{ELBO}(\lambda) &=\; \mathbb{E}_{q(\mathbf{z}\;;\;\lambda)} \big[ \nabla_\lambda \log q(\mathbf{z}\;;\;\lambda) \: \big( \log p(\mathbf{x}, \mathbf{z}) - \log q(\mathbf{z}\;;\;\lambda) \big) \big].\end{aligned} The gradient of the ELBO is an expectation over the variational model $$q(\mathbf{z}\;;\;\lambda)$$; the only new ingredient it requires is the score function $$\nabla_\lambda \log q(\mathbf{z}\;;\;\lambda)$$ (Paisley, Blei, & Jordan, 2012; Ranganath, Gerrish, & Blei, 2014).

Edward uses automatic differentiation, specifically with TensorFlow’s computational graphs, making this gradient computation both simple and efficient to distribute.

### Noisy estimates using Monte Carlo integration

We can use Monte Carlo integration to obtain noisy estimates of both the ELBO and its gradient. The basic procedure follows these steps:

1. draw $$S$$ samples $$\{\mathbf{z}_s\}_1^S \sim q(\mathbf{z}\;;\;\lambda)$$,
2. evaluate the argument of the expectation using $$\{\mathbf{z}_s\}_1^S$$, and
3. compute the empirical mean of the evaluated quantities.

A Monte Carlo estimate of the gradient is then \begin{aligned} \nabla_\lambda\; \text{ELBO}(\lambda) &\approx\; \frac{1}{S} \sum_{s=1}^{S} \big[ \big( \log p(\mathbf{x}, \mathbf{z}_s) - \log q(\mathbf{z}_s\;;\;\lambda) \big) \: \nabla_\lambda \log q(\mathbf{z}_s\;;\;\lambda) \big].\end{aligned} This is an unbiased estimate of the actual gradient of the ELBO.

### Implementation

Note: These details are outdated since Edward v1.1.3.

We implement $$\text{KL}(q\|p)$$ minimization with the score function gradient in the class KLqp. It inherits from VariationalInference, which provides a collection of default methods such as an optimizer.

class KLqp(VariationalInference):
def __init__(self, *args, **kwargs):
super(KLqp, self).__init__(*args, **kwargs)

def initialize(self, n_samples=1, ...):
...
self.n_samples = n_samples
return super(KLqp, self).initialize(*args, **kwargs)

def build_score_loss(self):
x = self.data
z = {key: rv.sample([self.n_samples])
for key, rv in six.iteritems(self.latent_vars)}

p_log_prob = self.model_wrapper.log_prob(x, z)
q_log_prob = 0.0
for key, rv in six.iteritems(self.latent_vars):
list(range(1, len(rv.get_batch_shape()) + 1)))

losses = p_log_prob - q_log_prob
self.loss = -tf.reduce_mean(losses)

Two methods are added: initialize() and build_score_loss(). The method initialize() follows the same initialization as VariationalInference, and adds an argument: n_samples for the number of samples from the variational model.

The method build_score_loss() implements the ELBO and its gradient. It draws self.n_samples samples from the variational model. It registers the Monte Carlo estimate of the ELBO in TensorFlow’s computational graph, and stores it negative in self.loss, to track progress of the inference for diagnostics.

The method returns an object whose automatic differentiation is the score function gradient of the ELBO. The TensorFlow function tf.stop_gradient() tells the computational graph to stop traversing nodes to propagate gradients. In this case, the only gradients taken are $$\nabla_\lambda \log q(\mathbf{z}_s\;;\;\lambda)$$, one for each sample $$\mathbf{z}_s$$. We multiply it by losses element-wise and return the mean.

There is a nuance here. TensorFlow’s optimizers are configured to minimize an objective function. So the gradient is set to be the negative of the ELBO’s gradient.

See the API for more details.

### References

Paisley, J., Blei, D. M., & Jordan, M. I. (2012). Variational bayesian inference with stochastic search. In International conference on machine learning (pp. 1367–1374).

Ranganath, R., Gerrish, S., & Blei, D. (2014). Black box variational inference. In Artificial intelligence and statistics.


text:
Publish here. Donate

# Powerball Winner

Match five + Power Play
Not to sound like a broken record, but tonight’s Mega Millions drawing is the largest Mega Millions drawing in history. However, to add a bit of flavor, it is the largest lottery drawing in American history in basic and comes with some insane odds. Remain tuned here for the winning Mega Millions numbers when the subsequent drawing occurs tonight,Tuesday, Oct. 23 at eight p.m. Players choose six numbers from two separate pools of numbers – 5 distinct numbers from 1 to 70 and one quantity from 1 to 25 (the Mega Ball quantity). Players can also use an straightforward pick feature, exactly where a computer selects random numbers for

br>If you chose to play the Megaplier, any non-jackpot prize you win is multiplied by the Megaplier number that is drawn. For an further $1, players can opt-in to play the Megaplier, which can considerably raise the value of the non-jackpot prizes. Taking the jackpot's cash value is an option favored by most winners. It is the seventh-largest jackpot in the history of Mega Millions drawings and the biggest considering that final October, the organization stat
br>$1 Million Winne
br>In Oregon, state lottery winnings of up to $600 from a single ticket or play are tax exempt. An agreement amongst 파워볼분석 Mega Millions and Powerball was reached in October
9.
If extra than one ticket holder scoops the jackpot, the prize is shared equally by all the winners. Lots of people today obtain lottery tickets as a group, such as an workplace lottery
l.
The subsequent drawing Tuesday has a starting value of$40 million, according to Mega Millions. If you do win, you most likely won't get the complete payout, given 파워볼분석 that the prize could be split among more than 1 jack

e

Mavis L. Wanczyk was announced as the winner of the $758.7 Million Powerball Jackpot in August of 2017. Mavis L. Wanczyk of Chicopee, Massachusetts, claimed the winning ticket for the$758.7 million Powerball jackpot in August of 2017, taking $480.5 million before taxes as the lump s

n

Watch the draw on TV TattsLotto, Monday & Wednesday Lotto, Oz Lotto and Powerball draws can be seen on 7TWO at approximately 8:30pm AEST on the night of the official draw. Set for Life results for each daily draw can be seen on Channel 7 and 7TWO at approximately 9:45pm AEST e

h

Jackpot
ners
He opted to take the lump-sum payout selection of$223 million, which after state and federal taxes will net him $158 million. Every person knew someone had purchased last week’s winning Powerball ticket worth$344.six million in Hope Mills, but Charles W. Jackson Jr. didn’t comprehend it was him till Tuesday morning. Charles W. Jackson Jr. purchased last week’s winning Powerball ticket worth $344.six million in Hope Mills. RALEIGH, NC – A man from North Carolina stated he made use of fortune cookie numbers to win the$344.six million Powerball jackpot Saturday evening, WSOCTV reports. The Mega Millions winner has the option to take aone-time lump sum or be paid in annual installmentsof

ar

When you pick your Mega Millions best playing numbers, choose a pretty even mix of odd and even numbers. All odd numbers or all even numbersare seldom drawn, occurring less than three% of the time. The ideal mix is to have three/2 or 2/three which suggests 3 odd and two even, or two odd and three even. Mega Millions at the moment holds the world record for both the largest jackpot ($1.six BILLION on ten/23/18) and the largest lottery prize won by a
le ticket.
In a regional lottery, you have to be physically present for the duration of the draw, but the odd of winning is higher compared with a nationwide lottery. You also have to note that your prize will also depend on how many tickets have a similar win
 quantity.
That comes with a cash solution payout of$345.2 million, according to contest officials. The approximate general odds of winning a Mega Millions prize are 1 in 24.00. For an more $1 per play, you could acquire 파워볼분석 theMegaplierfeature to improve non-jackpot prizes by 2, three, 4 or five times. The least drawn gold balls have been No. eight and No. 15, only six times
y (two.two%).
The typical American spends about$223 per year on lottery tickets, according to asurveyfrom LENDedu. Massachusetts residents have the biggest taste for playing the odds, spending practically 파워볼분석 $763 per year on lottery tickets,

iscovere

Please note that you will not be provided a 'win receipt' for a winning scratchcard. This is due to the fact scratchcards currently include all of the info required for you to know irrespective of whether or not y
ave won a prize.
Staunch naysayers who dismiss playing the lotto as paying a "voluntary tax" are suddenly appearing in lines to choose a handful of tickets. Florida Lottery Secretary Tom Delacenserie, left, presents Maureen Smith and David Kaltschmidt with their one particular-third share of the Jan. 13, globe record Powerball jackpot. Bigger wins amounting to millions go by way of a verification procedure which typically requires 5-10 business enterprise days. Most lottery websites that recognize as lottery agents take care of ticke
rchases for you.
BONITA SPRINGS, Fla –One fortunate ticket sold in Florida matched all six numbers in the Powerball Wednesday evening, according to lottery officials. One fortunate ticket sold in Florida matched all six numbers in the Powerball Wednesday evening and is worth$396.9 million, according to lottery officials. All National Lottery games can be played on the 파워볼분석 web soon after registering. In October 2002 operator Uthingo suggested a every day lottery to supplement the weekly draw. The Wednesday night Powerball game featur
$345 million prize.
You cannot return Powerball tickets when they are printed, so if you do not like the numbers you are offered, you cannot change them. If you are nevertheless hunting to play the lottery, check [https://Bepick.net/game/daily/nlotto_power 파워볼분석] out theLotter, an quick way to obtain lottery tickets on
 from around the world.
In the coming days, officials would find out that 1 "person" had secured not only the$27,036,142 jackpot, but six second prizes, 132 third prizes, and 135k minor prizes collectively worth a different $900k. How a rogue Romanian economist legally gamed the lottery and won millions of dollars about the world. Rhode Island Gov. Lincoln Chaffee was present for the historic win and praised her for waiting to claim her prize and finding skilled support as effectively. There is also no cap or rollover limit, meaning prizes can very easily run into the hundreds of millions of dollars. Pick out irrespective of whether to play the Mega
r for an additional$1.
As Mandel knew, the "buy all combinations" approach of winning the lottery was extra of a logistical than a financial challenge. In a Melbourne warehouse, he set up 30 computers and 12 laser printers, and hired 16 full-time staff to print millions of tickets pre-populated with each 파워볼분석 mixture — a method that took three months. He then shipped the one-tonne of paper weight to a point-per
in the US at a cost of \$60k.
As the name implies, players get discounts the much more draws they select to participate in. Playing lottery the conventional way signifies that you can only play lotteries that are accessible in your region. Going on the internet, on the other hand, opens the doors to a complete host of games. Most lottery sites—especially business stalwarts the likes of theLotter and WinTrillions—offer games from around the world. He hopes additional persons will play the lottery at his winning location, Obeissy mentione


text:
# LM 358 simple test circuit : how to improve it ?

#### Philexium

Joined Oct 15, 2017
43
Hi,

I had recently designed a circuit with a LM 358, which didn't work immediately and I suspected some of the LM 358 to be defective.
In fact I have discovered that depending on the manufacturers, there are some big differences (ie TI, SGS, ...)

So I have found here a schematic for a test circuit and it works.
It's basic but nice, cost effective and simple.

However, is there a possibility to modify it in order that the first OP AMP drives the second one, like it's possible with a CD 4093 schmitt trigger ?

#### Attachments

• 169.1 KB Views: 47

#### Irving

Joined Jan 30, 2016
3,133
A test circuit for the LM358 or ...? So what does this 'test circuit' actually test? Where did you find it?

And what would the point of connecting #2 to the output of #1 be? What are you trying to achieve? (and its nothing like a CD4093, completely different approach)

#### Philexium

Joined Oct 15, 2017
43
A test circuit for the LM358 or ...? So what does this 'test circuit' actually test? Where did you find it?

And what would the point of connecting #2 to the output of #1 be? What are you trying to achieve? (and its nothing like a CD4093, completely different approach)
Hi Irving

I am sorry but I am not familiar with OP AMP :-(
The purpose was just to design quickly a "go-no go" circuit

Concerning the CD 4093 it was just an "image" to explain I want to control the 2nd LM358 OP AMP with the 1st one

I mean :
- If the 1st one works and the 2nd too, both are blinking
- If the 1 st one doesn't, the 2nd would not blink

The idea is to identify which one is defective or both !

Hope its clear

#### Irving

Joined Jan 30, 2016
3,133
Ah right, a go/no-go for the LM358... so if it blinks its good? well yes, to an extent.

There is no easy way to connect #2 to the output of #1, and in any case, what happens if #2 is good but #1 bad?~ With your approach you'd never know if #2 was good if #1 is bad. 1/2 a package is still a useful thing...

#### Philexium

Joined Oct 15, 2017
43
Ah right, a go/no-go for the LM358... so if it blinks its good? well yes, to an extent.

There is no easy way to connect #2 to the output of #1, and in any case, what happens if #2 is good but #1 bad?~ With your approach you'd never know if #2 was good if #1 is bad. 1/2 a package is still a useful thing...
Thank you Irving you have drawn my attention : " you'd never know if #2 was good if #1 is bad"
Yes so tue !
The easiest solution remains to duplicate the crcuit as in the original schematic.

#### Irving

Joined Jan 30, 2016
3,133
Further thoughts, while there are minor variations between manufacturers they shouldn't materially impact on usage unless you're trying to do something the device really isn't appropriate for.. The test circuit is unlikely to tell you much about that...

What were you trying to do?

#### dl324

Joined Mar 30, 2015
15,114
So I have found here a schematic for a test circuit and it works.
You posted a schematic from an AAC member. The polite thing to do, regardless of the source, is to give attribution when you use the work of others.

The original thread by @Ford Prefect.
However, is there a possibility to modify it in order that the first OP AMP drives the second one, like it's possible with a CD 4093 schmitt trigger ?
Why would you want to do that? If one is bad, you need to do more work to figure out which one.

#### Philexium

Joined Oct 15, 2017
43
You posted a schematic from an AAC member. The polite thing to do, regardless of the source, is to give attribution when you use the work of others.

The original thread by @Ford Prefect.
Why would you want to do that? If one is bad, you need to do more work to figure out which one.
Hi Dennis

Thank you
Sorry I aplogize for forgetting it, I am just a beginner here and will remember it

It's for a field strenght meter

#### Irving

Joined Jan 30, 2016
3,133

#### dl324

Joined Mar 30, 2015
15,114
Sorry I aplogize for forgetting it, I am just a beginner here and will remember it
No problem.

Since you're learning about opamps, these clips from Signetics explain how the gain formulas were derived.

#### Philexium

Joined Oct 15, 2017
43
and...? why didn't it work?
I need the strenght meter to be very sensitive !

Due to the high gain (about 1 000), the offset voltage is multiplied too and so without any HF field the needle of the 100 ua galvanometer is deflecting ...

I am looking for a solution to reduce as much as possible the offset voltage.
Looking at the LM 358 data sheet indicates a min. 2 mV offset.
Please note that I am using a single voltage power supply so I didn't find any solution on the data sheets of the OP AMP.

I know there are some very high performance OP AMP like the LT 1077 with a very low offset but they are very expensive !

I am going to use another OP AMP it will be the best way

#### Attachments

• 52.4 KB Views: 9

#### dl324

Joined Mar 30, 2015
15,114
I am looking for a solution to reduce as much as possible the offset voltage.
You have another thread on this topic. You shouldn't cross post because you'll lose context.
Looking at the LM 358 data sheet indicates a min. 2 mV offset.
That's the typical value, the minimum could be lower. Conservative design would use the maximum.

It doesn't matter because you've probably been told in the other thread how to null the offset voltage.

#### MrChips

Joined Oct 2, 2009
27,129
I can think of only one way to test the functionality of an op-amp in a simple circuit.

#### Philexium

Joined Oct 15, 2017
43
I can think of only one way to test the functionality of an op-amp in a simple circuit.
Yes I own an old ! Tektronix 2245 a

#### Audioguru again

Joined Oct 21, 2019
5,175
I already explained why the field strength meter does not work on your other thread about it. Its + input is not biased at 0V, it floats up because of its positive-going input bias current causing the opamp output to go as high as it can with or without a signal.

#### Irving

Joined Jan 30, 2016
3,133
Re your field strength meter - what frequency is your tank circuit supposedly operating at? The OA85 is a blast from the past!

You will need a lower input offset but that need not cost the earth. Equally problematic with high gain is input noise, you need a low-noise op-amp. LM358 is exactly what you don't need. Here's the problem with the LM358 - the offset is too large so the output is close to the supply rail even with no, or a small, input... also,as has been said, R6 across the input is needed to maintain DC bias as your tank circuit has only a capacitor across the output so is floating.

Note the use of both halves of the device. Gains of 1000 with a single stage are not impossible, but its often better to cascade two stages, here giving 34x followed by 31x for just over 1000. The output volts are converted to a current by R5 and pot X1 and the latter provides a calibration mechanism to adjust for full scale.

Replacing the LM358 with something with a much lower input offset allows it to work. Here I've used an AD8572 but there are many suitable parts... The AD8572 is only one example and is only $5 so doesn't break the bank (its a dual device so only one needed). One caveat - with this low input voltage (< 5mV) and high gain, layout is critical. Making this work reliably on a breadboard is likely to be difficult, if not impossible. #### MrChips Joined Oct 2, 2009 27,129 I used a TLC555 (or LMC555) CMOS 555-timer circuit to generate a square wave. R3 and R4 form a voltage divider to attenuate the signal to about 200mV. You may substitute the 555-timer circuit with a function generator. The op-amp under test is configured with a moderate voltage gain of -10 (negative because the signal is inverted). The input is AC coupled via C2 while the non-inverting input is biased at 1/2 Vcc with R7 and R8. Vcc is a single supply, anything from 5 to 15V. When examining the output of the op-amp on an oscilloscope, we are looking for four things: 1) output should be centered about 1/2 Vcc 2) voltage gain of 10 3) phase inversion 4) rise and fall times on the transitions The first test is with an LM358 op-amp which has a gain-bandwidth product of 1MHz. The second test is with a TL072 op-amp which has a gain-bandwidth product of 5MHz. Notice the difference in the rise and fall times compared with the LM358. The phase inversion becomes more obvious. #### Audioguru again Joined Oct 21, 2019 5,175 Here is the LM358 opamp with mismatched input resistors and a gain of 1001 amplifying its own input bias current: #### Attachments • 83.5 KB Views: 9 Thread Starter #### Philexium Joined Oct 15, 2017 43 I used a TLC555 (or LMC555) CMOS 555-timer circuit to generate a square wave. R3 and R4 form a voltage divider to attenuate the signal to about 200mV. You may substitute the 555-timer circuit with a function generator. The op-amp under test is configured with a moderate voltage gain of -10 (negative because the signal is inverted). The input is AC coupled via C2 while the non-inverting input is biased at 1/2 Vcc with R7 and R8. Vcc is a single supply, anything from 5 to 15V. When examining the output of the op-amp on an oscilloscope, we are looking for four things: 1) output should be centered about 1/2 Vcc 2) voltage gain of 10 3) phase inversion 4) rise and fall times on the transitions View attachment 251223 The first test is with an LM358 op-amp which has a gain-bandwidth product of 1MHz. View attachment 251224 The second test is with a TL072 op-amp which has a gain-bandwidth product of 5MHz. Notice the difference in the rise and fall times compared with the LM358. The phase inversion becomes more obvious. View attachment 251225 Thank you @MrChips ! It's very interesting, a nice circuit and easy to test on my breadboard Thank you again for your time and help Best regards from Normandy, France Philippe Last edited: Thread Starter #### Philexium Joined Oct 15, 2017 43 Re your field strength meter - what frequency is your tank circuit supposedly operating at? The OA85 is a blast from the past! You will need a lower input offset but that need not cost the earth. Equally problematic with high gain is input noise, you need a low-noise op-amp. LM358 is exactly what you don't need. Here's the problem with the LM358 - the offset is too large so the output is close to the supply rail even with no, or a small, input... also,as has been said, R6 across the input is needed to maintain DC bias as your tank circuit has only a capacitor across the output so is floating. Note the use of both halves of the device. Gains of 1000 with a single stage are not impossible, but its often better to cascade two stages, here giving 34x followed by 31x for just over 1000. The output volts are converted to a current by R5 and pot X1 and the latter provides a calibration mechanism to adjust for full scale. View attachment 251214 Replacing the LM358 with something with a much lower input offset allows it to work. Here I've used an AD8572 but there are many suitable parts... The AD8572 is only one example and is only$5 so doesn't break the bank (its a dual device so only one needed).

One caveat - with this low input voltage (< 5mV) and high gain, layout is critical. Making this work reliably on a breadboard is likely to be difficult, if not impossible.

View attachment 251215
Hi @Irving

The circuit has to be tuned on 144 Mhz (I am a Ham F1 CUJ)

You're right I am using now OA95 , a still old diode but a Germanium one with a low forward voltage, lower than that of silicon

I just had a look at the Analog Device 8572 IC. This is really a very powerful chip !

I see you are using LTspice right ?

It's very interesting, not to be tested on my breadboard I have well understood that.
I use to make circuits with "Manhattan" method with epoxy clads for a quick prototyping
Thank you again for your time and help

Best regards from Normandy, France
Philippe