Maximum of arithmetic operations needed

posuchmex
Messages
5
Reaction score
0
Hello, I tried to figure out what is the maximum count of arithmetic operation (*,:,+,-) need for gauss elimination and gauss-jordan elimination, but can not get it right.

what I get from wikipedia is
Gaussian elimination to solve a system of n equations for n unknowns requires n(n+1) / 2 divisions, (2n3 + 3n2 − 5n)/6 multiplications, and (2n3 + 3n2 − 5n)/6 subtractions,[4] for a total of approximately 2n3 / 3 operations. Thus it has arithmetic complexity of O(n3). However, the intermediate entries can grow exponentially large, so it has exponential bit complexity.
but I don't understand how to get to this result.

Thanks for any help.
 
Physics news on Phys.org

Thread 'Trouble understanding an online solution to an exercise in Dummit & Foote'

##\textbf{Exercise 10}:## I came across the following solution online: Questions: 1. When the author states in "that ring (not sure if he is referring to ##R## or ##R/\mathfrak{p}##, but I am guessing the later) ##x_n x_{n+1}=0## for all odd $n$ and ##x_{n+1}## is invertible, so that ##x_n=0##" 2. How does ##x_nx_{n+1}=0## implies that ##x_{n+1}## is invertible and ##x_n=0##. I mean if the quotient ring ##R/\mathfrak{p}## is an integral domain, and ##x_{n+1}## is invertible then...
View full post »

Thread 'Questions about non existence of GCDs vs (coimages, cokernels)'

The following are taken from the two sources, 1) from this online page and the book An Introduction to Module Theory by: Ibrahim Assem, Flavio U. Coelho. In the Abelian Categories chapter in the module theory text on page 157, right after presenting IV.2.21 Definition, the authors states "Image and coimage may or may not exist, but if they do, then they are unique up to isomorphism (because so are kernels and cokernels). Also in the reference url page above, the authors present two...
View full post »

Thread 'Decomposition into irreps of compact Lie group'

When decomposing a representation ##\rho## of a finite group ##G## into irreducible representations, we can find the number of times the representation contains a particular irrep ##\rho_0## through the character inner product $$ \langle \chi, \chi_0\rangle = \frac{1}{|G|} \sum_{g\in G} \chi(g) \chi_0(g)^*$$ where ##\chi## and ##\chi_0## are the characters of ##\rho## and ##\rho_0##, respectively. Since all group elements in the same conjugacy class have the same characters, this may be...
View full post »

Similar threads

B A proper comprehensive rule for arithmetic operation precendence
Replies
1
Views
1K
I don't understand kind of program the instructions want
Replies
4
Views
3K
Matrix Operation: Why n^2 Steps Needed for Elimination of First Row?
Replies
5
Views
3K
Arithmetic Sequences: Examples & Solutions for 35th, 57th Terms
Replies
7
Views
3K
I Some notes on stochastic physics
Replies
1
Views
2K
Challenge Micromass' big September challenge
2
Replies
77
Views
12K
I Micromass' big October challenge
3
Replies
125
Views
19K
B Time-reversal of an unknown quantum state
Replies
1
Views
1K
Challenge Math Challenge - November 2019
Replies
42
Views
12K
What is the CORDIC Algorithm and How Does it Work?
Replies
1
Views
3K

Hot Threads

Recent Insights

Back
Top