Tagged Questions
0
votes
2answers
43 views
Is there a simple method to do LU decomposition by hand?
Today my professor in numerical analysis pointed out that in the exam we will probably have to do LU decomposition by hand.
I'm understand how the decomposition works theoretically, but when it comes ...
2
votes
1answer
45 views
Proof of correctness of Putzers algorithm
I have a question regarding the proof (seen below) of Putzers algorithm for matrix exponentiation. It's written by our danish lecturer at the university, so I translated the important parts into ...
3
votes
1answer
52 views
Detect numbers surrounded by equal numbers in a matrix
I need an algorithm that extracts from a matrix those fields that are surrounded by equal values. I'll provide you an example to see it clearer.
This is my intitial matrix.
$$
...
1
vote
1answer
17 views
How to show quantisation error for frequency coefficient
I have the following question from an exam which reads:
For the second question my answer is:
24 5 2 3
9 2 1 3
2 3 2 2
1 1 1 0
I am unsure of what formula ...
0
votes
1answer
23 views
Explanation on step $\rho$ of the SHA-3 algorithm
I'm working on implementing SHA-3 in a PIC microcontroller.
In the block permutation, I don't quite understand step $\rho$:
Bitwise rotate each of the 25 words by a different triangular number 0, ...
1
vote
0answers
32 views
COLAMD matrix reordering algorithm
Background
I'm dealing with some variable size square sparse matrices resulting from a FEM analysis, and my next step is optimizing the system solving in terms of speed. This is a visualization of ...
1
vote
0answers
57 views
Complexity of SVD
I am working with $SVD$. Here they noted that, it's complexity is $O(n^3)$. I know that we need to find three matrices $ U,V,S $. i.e., If A is a matrix of order $m*n$ then $svd $ of A is ...
2
votes
0answers
71 views
all eigenvalues of a large sparse symmetric matrix
my question is similar to
how to diagonalize a large sparse symmetric matrix, to get the eigenvalues and eigenvectors
however i wish to be more concrete and ask if one can, on a standard PC
(e.g. a ...
0
votes
0answers
36 views
backward stability of full svd decomposition
Why is it impossible for the full SVD decomposition of a matrix A to be a backward stable algorithm? This was mentioned in one of my readings but it doesn't explain why.
1
vote
3answers
64 views
How to solve two recurrences dependent on each other
Let
$F_n = a_1*F_{n-1} + b_1*F_{n-2} + c_1*G_{n-3}$
$G_n = a_2*G_{n-1} + b_2*G_{n-2} + c_2*F_{n-3}$
We are given $ a_1,b_1,c_1,a_2,b_2,c_2$ and $ F_0,F_1,F_2, G_0, G_1,G_2 $. We have to calculate ...
4
votes
2answers
51 views
Sparse basis for linear subspace
Suppose I have a linear subspace of some vector space, e.g. described as the column space of some big matrix. How would I algorithmically find a basis of that same subspace where the basis matrix is ...
0
votes
1answer
106 views
2D Eculidian matrix to 2D cartesian graph/plan
Can anyone help ?
I am trying to convert a 2D matrix of distances to a 2D graph.
For instance, I would like to go from this :
...
2
votes
1answer
102 views
Lower bound for matrix sorting?
Consider the problem of sorting a $n$ by $n$ matrix i.e. the rows and columns are in ascending order. I want to find the lower and upper bound of this problem.
I found that it is $O(n^2logn)$ by just ...
3
votes
5answers
109 views
Translating matrix fibonacci into c++ (how can we determine if a number is fibonacci?)
Is it possible to determine if a number is a fibonacci number in less than N time (where N is the Nth fibonacci number) using the matrix method? I'm trying to exclude external libraries like cmath or ...
0
votes
2answers
117 views
How to test if a graph is fully connected and finding isolated graphs from an adjacency matrix
I have large sparse adjacency matrices that may or maybe not be fully connected. I would like to find out if a matrix is fully connected or not and if it is, which groups of nodes belong to a ...
7
votes
0answers
116 views
Determining sign(det(A)) for nearly-singular matrix A
Motivation: determining whether a point $p$ is above or below a plane $\pi$, which is defined by $d$ points, in a $d$-dimensional space, is equivalent to computing the sign of a determinant of a ...
1
vote
1answer
71 views
Generating random commuting hermitian matrices
How can I generate random commuting hermitian matrices ?
EDIT:
Another question: given a certain hermitian matrix, how can I generate a random hermitian matrix which commutes with it?
1
vote
0answers
34 views
Optimizing a matrix
input: $b_1,b_2,...,b_n$ positive integers.
$a_1<a_2<...a_n$ positive integers
output: positive integer
I'm given
$b_1$ columns of the form
...
0
votes
0answers
40 views
Another Matrix Algorithn
Another Matrix algorithm
input: $b_1,b_2,...,b_n$ positive integers.
$a_1<a_2<...a_n$ positive integers
output: positive integer
I'm given
$b_1$ columns of the form
$ \left( ...
1
vote
1answer
82 views
An algorithm for creating a matrix with certain properties
I'm searching for an algorithm that efficiently does the following
Input:
$n\in \mathbb{N}$
$j_1,j_2,\ldots ,j_n$ with the property $j_1<j_2<\cdots<j_n$
$b_1,\ldots ,b_n \in \mathbb{N}$
...
0
votes
0answers
62 views
Improve HouseHolder algorithm?
in QR decomposition with householder algorithm if matrix A in some state the algorithm will works better and better answer returns
my question is how matrix A should be for householder algorithm to ...
0
votes
0answers
111 views
Matlab, QR with columns pivoting
Is there any sample matlab code computing QR decomposition with columns pivoting for a matrix?
I do not need an internal function, I would like to know the method...
Thanks for your help...
0
votes
1answer
1k views
Convert a n by n matrix to upper triangular
How can we mathematically and algorithmic-ally convert a $n\times n$ matrix to a upper triangular matrix
0
votes
0answers
22 views
$M \cdot [x,y,z]^t=[x^2,y^2,z^2]^t$ - can this be solved similarly like the eigenvector-problem?
Given I have a matrix M, say 3x3, and invertible, and we want to determine the coefficients $[x,y,z]$ by the formula
$$ M \cdot \begin{bmatrix} x\\y\\z \end{bmatrix} = \begin{bmatrix} x^2\\y^2\\z^2 ...
1
vote
0answers
49 views
Optimized Algorithm for Distance Matrix Solution
I've been looking for an optimized algorithm for solving a distance matrix (a hollow, skew symmetric matrix), but I haven't been able to find anything but papers discussing repopulating sparse ...
3
votes
0answers
633 views
When does a Square Matrix have an LU Decomposition?
When can we split a square matrix (rows = columns) into it’s LU decomposition? The LUP (LU Decomposition with pivoting) always exists; however, a true LU decomposition does not always exist. How do ...
0
votes
0answers
64 views
Find a similarity to a normal matrix?
I am interested in finding a similarity to a normal matrix given a random real matrix (or even random complex).
A normal matrix $A$ is one that satisfies $AA^* = A^*A$. In words the matrix commutes ...
1
vote
1answer
233 views
is there are specific way to solve coupled first-order differential equations with coefficients varying?
suppose I have "n" coupled differential equation represented by the matrix, Y• = A Y , where Y• is the column matrix containing first derivatives, namely, y1•(t), y2•(t), ... ...
4
votes
1answer
211 views
Characterizing a real symmetric matrix $A$ as $A = XX^T - YY^T$
In my personal research and quest to better understand the subject, I have noticed something concerning the Cholesky factorization of symmetric matrices. Everything I have read states that a symmetric ...
4
votes
1answer
150 views
Permute the values in each row in a matrix such that the columns sum to the same amount.
The general problem
Given a matrix, I would like to permute the order of values in each row, so that all the columns of the matrix sums to the same value.
A simple example
For example, given:
...
5
votes
1answer
209 views
Algorithm to find conjugacy classes of subgroups/elements (in matrix groups)?
I'm looking for a simple (=doable to implement by myself) algorithm to compute the conjugacy classes of elements and subgroups of a given subgroup of $\text{P}{\Gamma}\text{L}(n,q)$. So given a group ...
1
vote
0answers
36 views
How to pick correct sign on matrices such that their sum is a nonnegative matrix?
Given a set of matrix $M_i$, by picking a sign coefficient $S_i\in\{-1,1\}$
How can I effectively find a combination that the sum $M^*= \sum_{i=1}^N S_iM_i$ is a nonnegative matrix.
i.e. ...
3
votes
1answer
82 views
matrix “flag” clearing
I have a large matrix that is populated with a list of people, and a 1 or 0 as to whether or not they have a particular flag. A person can have one or more flags, or none at all. For example:
$$
...
4
votes
2answers
304 views
Inverse of symmetric matrix $M = A A^\top$
I have a matrix, generated by the product of a non-square matrix with its own transpose:
$$M = A A^\top.$$
I need the inverse of $M$, assuming $\det(M) \neq 0$.
Given the nature of the matrix $M$, ...
0
votes
1answer
818 views
Inverse of symmetric matrix M = A*At [duplicate]
Possible Duplicate:
Inverse of symmetric matrix $M = A A^\top$
I have a matrix, generated by the product of a non-square matrix with its own transpose:
...
0
votes
0answers
262 views
Conversion of PID controller components with state feedback into single transfer function and discrete state-space form
I've been wrestling with this problem for about a week now, as a part of a year-long project. We're designing a controller for a specific reactor based on a model. After looking at this for a while, I ...
2
votes
2answers
272 views
Fast algorithm for LU factorization
If A is a symmetric matrix, is there a fast algorithm for LU factorization? I know this algorithm for non-symmetric matrix.
...
4
votes
1answer
254 views
Why does Strassen's algorithm work for $2\times 2$ matrices only when the number of multiplications is $7$?
I have been reading Introduction to Algorithms by Cormen et al. Before explaining Strassen algorithm the book says this:
Strassen’s algorithm is not at all obvious. (This might be the biggest ...
1
vote
0answers
54 views
Can parallelism make faster matrix inversion algortihms? How?
My concern is about matrix inversion. Consider This page. I was thinking about creating four different threads for every component of the final matrix. In order to be more specific, I am going to ...
1
vote
2answers
653 views
Block Diagonalizing an antisymmetric matrix
I was wondering how to block diagonalize a $10\times10$ antisymmetric matrix into block matrices along the diagonal. Can I just diagonalize each non-diagonal block?
Thanks!
0
votes
0answers
87 views
Creating a precision matrix for Gaussian markov random field
I am currently trying to create a precision matrix for a Gaussian markov random field. Lets say I have random variables in a spatial grid of 6x6. Then I will have a precision matrix of 36x36.
Now ...
2
votes
1answer
67 views
How to find a canonical member of an equivalence class of matrices under row and column swaps?
Call two matrices "swap-equivalent" if one matrix can be transformed into the other via some sequence of row swaps and column swaps.
I'd like a computationally efficient algorithm that can transform ...
0
votes
1answer
282 views
calculating matrix rank with gaussian elimination
[The answer to my problem has been found: it was a simple sign error. the pseudo code below is fine]
I have implemented an algorithm in c++ that should calculate the matrix rank of a given n x m ...
2
votes
1answer
217 views
Confusion with “trivial Givens rotations” being used to eliminate values in a vector
I am currently studying the QR algorithm described in Computing the eigenvalues of a
companion matrix and have come to something that has me scratching my head. I'm trying to work this method out on ...
0
votes
0answers
125 views
Binary matrix as a product of two matrices
Is it possible to represent a binary( 0 and 1) matrix $A$ of size $ m \times n$ as a product of two martices $B$ of size $m \times k$ and $C$ of size $k \times n$. Various cases can also be considered ...
6
votes
3answers
2k views
Get Transformation Matrix from Points
I have built a little C# application that allows visualization of perpective transformations with a matrix, in 2D XYW space. Now I would like to be able to calculate the matrix from the four corners ...
3
votes
2answers
125 views
No identical rectangles in a matrix
I have a matrix of dimensions N x M.
Every cell has an integer.
Now, I want for every 'rectangle', to verify that all its corners are not the same.
Example:
This matrix is fine:
This matrix is not:
...
2
votes
2answers
1k views
Can QR decomposition be used for matrix inversion?
Is there any simple algorithm for matrix inversion (that can be implemented using C/C++)?
Can QR decomposition be used for matrix inversion? How?
2
votes
1answer
88 views
Computing the point which is closest to many Planar surfaces
Suppose, i have been given different planes which orients to different direction (i.e. i know only the plane parameter of those planes). If i am able to find out planes (probably more than 3 planes) ...
2
votes
2answers
99 views
Formula for the number of 0's in an alternating 0-1 matrix
I was working with a piece of code when I stumbled across a matrix, which is similar to this:
$$\begin{matrix}
0&1&0&1&0&1&0&\cdots\\
...
