Questions on the various algorithms used in linear algebra computations (matrix computations).

learn more… | top users | synonyms

0
votes
0answers
38 views

Rank and solvability of a matrix

I am working with linear complementarity problems (LCPs) which look for a solution $\mathbf{x} \in \mathbb{R}^{n}$ in the form $$ \begin{matrix} \mathbf{x} & \geq & 0 \\ ...
1
vote
2answers
48 views

Square Idempotent matrix: efficient algorithms for finding eigenvectors

Given a square idempotent $N \times N$ matrix $A$ with large $N$, and a priori knowledge of the rank $K$, what is the most efficient way to compute the $K$ eigenvectors corresponding to the $K$ ...
0
votes
1answer
42 views

matrix exponential and Spectral abscissa

Prove that $\lim_{t \rightarrow \infty} \|e^{tA}\| = 0$ if and only if $\alpha(A) < 0 $, where $\alpha$ is the Spectral abscissa, defined as $\max{Re(\lambda_i)}$. I tried to approach this ...
0
votes
1answer
62 views

Can SVD help to solve (inequality) constrained least squares problem?

Consider the following minimization problem: $$ ||Q u - h^{o} ||^{2} \to min \;\;\; s.t. \; u \geq 0 $$ where $Q$ is $m \times n$ matrix and $u$ is $n$-dimensional vector and $h^{0}$ is ...
1
vote
2answers
49 views

non-sequential sequence function

if i remember correctly (i had one workshop on numerics years ago, sorry for my lack of knowledge) there is a way to create some sort of hash function that gives you a non sequential sequence. This ...
2
votes
0answers
31 views

Smallest set of Liner equations, which exactly fit a set of points

I have a set of 2-d points,(it can be of any arbitrary dimension n). I want to find the minimum set of straight lines(linear equations) which exactly passes through the given 2-d points (unlike ...
4
votes
4answers
150 views

Finding nonnegative solutions to an underdetermined linear system

Here's the environment of my problem: I have a linear system of 4 equations in 8 unknowns (i.e. $Ax = b$, where $A$ is $4 \times 8$, $x$ is $8 \times 1$, and $b$ is $4 \times 1$, with $A$ given and ...
0
votes
1answer
50 views

Is there a limit for how “good” a numerical method can be?

Multiplying two matrices $A \cdot B$ of size $n \times n$ in the trivial way requires $n^3$ computations. However, more efficient algorithms such as the Strassen algorithm have a lower complexity of ...
0
votes
3answers
62 views

About matrix products $A^{T}A$ and $ AA^{T} $

I'm investigating the relationship between 2-norms and eigenvalues of $A^{T}A$ and $ AA^{T} $, in order to better understand the SVD decomposition. How can I prove that $A^{T}A$ and $ AA^{T} $ are ...
1
vote
0answers
78 views

Inverse of the sum of a symmetric and diagonal matrices

I have two square matrices, $A$ and $B$. $A$ is a block symmetric matrix with 1's along the diagonal (and therefore 1's in whole blocks along the diagonal). $B$ is a block diagonal, with the same ...
0
votes
0answers
12 views

need to determine weights so that quadrature formula holds

Let $l$ be an interval on the real axis, $t_1,...,t_n$ be distinct $n$ points, then there exists n numbers $m_1,...,m_n$ such that the quadrature formula, $\int_l p(t)dt = m_1p(t_1) + ... + ...
0
votes
1answer
21 views

Complexity of sparse back substitution

What is the complexity of sparse backsubstitution $Rx = b$, given $n$, the dimensions of dense $x$ and $b$ as well as of the sparse $R$ and $nnz$, the number of nonzero entries in $R$?
1
vote
1answer
40 views

How to solve an Optimization problem with linear as well as Quadratic constraints.

I want to solve the following problem, \begin{equation} \begin{aligned} & \underset{\mathbf{x}}{\text{minimize}} & & \mathbf{x^T}\mathbf{Px} \\ & \text{subject to} & & ...
0
votes
0answers
54 views

Expressing rank condition of a matrix in terms of its elements

Let $x \in \mathbb{R}^{n}$, define $X = xx^{T}$. I have an optimization problem with some linear constraints and few quadratic constraints, and I have to solve for $x$. Using $X$ as the unknown ...
4
votes
2answers
462 views

Algorithm to find an orthogonal basis (orthogonal to a given vector)

Let $K$ be a given integer, with $K$ even (and "large"). Let $\mathbf{v} \in \mathbb{R}^{K \times 1}$ be a given non-zero (column) vector. Write a (possibly efficient) algorithm to construct a matrix ...
0
votes
1answer
36 views

Is it possible to solve a system of equations comprising FFTs?

Consider the following known matrices, A, B, C and these unknown matrices X,Y, all of which comprise values in the Real domain. Also consider $F(x)$ as the *Fast Fourier Transform function* (the ...
3
votes
1answer
113 views

How to solve this system of 3 equations with 3 variables?

I stumbled upon this system with constants $a_{i,j}>0$ that I want to solve for $x,y,z \in\mathbb{R}$: \begin{align} a_{2,1}y+a_{3,1}z=& x(y+z) \\ a_{1,2}x+a_{3,2}z=& y(x+z) \\ ...
0
votes
1answer
53 views

Inverse Square root of a rectangular matrix

I am trying to compute the inverse square root ($X^{-1/2}$) of a $n \times p$ matrix with $n > p$. I was wondering if we can compute it via SVD just as we do it for square diagonalizable matrices ...
2
votes
2answers
62 views

Matlab terminate code if warning occurs [closed]

I am running a code where by I want to maximise a parameter (basically the range of integration) by increasing it in steps until a warning occurs. It involves inverting a linear system Ax=b and I want ...
-1
votes
1answer
41 views

A problem on numerical analysis [closed]

Let $f(x)=e^x$ be approximated by Taylor's polynomial of degree n at the point $x=\frac{1}{2}$ and on the interval $[0,1]$. If the absolute error in this approximation does not exceed $10^{-2}$ , then ...
0
votes
1answer
23 views

Residual norm for iterative scheme

Consider a linear system $A\vec{x} = \vec{b}$, where $A \in \mathbb{R}^{m\times{}m}$ is non-singular and positive definite. Given the following iteration scheme $\vec{x}^{(k+1)} = \vec{x}^{(k)} + ...
5
votes
0answers
75 views

IEEE 754 as a mathematical space

Integer operations in computers (i.e. 32-bit integers) probably can be represented best by modular arithmetic (because of integer overflows/underflows). What about IEEE 754 floating point arithmetic? ...
1
vote
1answer
43 views

Special Matrix 2-norm and F-norm Inequalities

This is a homework problem for my Numerical Linear Algebra course. It states the following: If A is an mxm nonsingular matrix, prove the following: (1)$\|A+(A^{*})^{-1}\| _{2} \ge 2$ ...
1
vote
1answer
50 views

Using the Gauss-Seidel method, will the matrix A converge

Just came back from my Numerical Analysis midterm, posting up the questions and my solutions for an estimation as to how I did. If you were to perform the Gauss-Seidel method on a matrix $A$, where ...
0
votes
0answers
30 views

Find the Cholesky Factorization of the matrix A

Just came from my Numerical Analysis midterm. There were 3 questions on it, trying to check my solutions to estimate my grade. Find the Cholesky of $$A = \begin{pmatrix}25 & 15 & -5\\15 & ...
1
vote
0answers
13 views

Finding eigenvalues in a region

I have an eigenvalue problem (of a very large (n~1000000) but sparse complex system) wherein I need to determine all the eigenvalues in a certain region(a rectangle) in the positive half plane. I am ...
2
votes
1answer
61 views

Absolute values in linear programming

Suppose I have an objective function in my LP as follows $max$ $|x|$ Based on some googling, I have found there are two ways to convert this into a standard LP. Method 1. $|x|$ = $ x^+ + x^-$ $x ...
2
votes
1answer
39 views

Is it true: $||A||_2 = \min\{ ||A||_1 ,||A||_3,||A||_4,\ldots \ldots, ||A||_{\infty},\|A\|_F\} $?

While running one algorithm , I observed the following peculiar relationship (at-least to me). I am not quite sure whether it is true in general, but I could not succeeded either in producing any ...
1
vote
2answers
38 views

Relation between condition number and perturbed matrix

Prove that if $A\vec{x} = \vec{b}$ and $(A+\delta{}A)(\vec{x}+\delta\vec{x}) = \vec{b}$, then $\dfrac{\|\delta\vec{x}\|/\|\vec{x}+\delta\vec{x}\|}{\|\delta{}A\|/\|A\|} \le \kappa{(A)}$, where ...
1
vote
1answer
43 views

What does it mean for a matrix to be nearly singular?

I am currently enrolled in numerical analysis course, and a terminology I have not heard of came up; nearly singular matrix. I know that a non-singular matrix is one where the column vectors are ...
0
votes
0answers
9 views

Predict values of some numerical vectors by using other numerical vectors with all these vectors in the same vector set

I need to solve a problem about predicting values of some numerical vectors by using other numerical vectors with all these vectors in the same vector set, which is generated by one or more black box ...
0
votes
1answer
75 views

Condition number vs. reconstruction error

Suppose I want to solve a simple, linear inverse problem given by $\mathbf{y} = \mathbf{A} \cdot \mathbf{c}$ where $\mathbf{A}$ is an $M \times K$ matrix and I want to solve for $\mathbf{c}$ ($M$ = ...
2
votes
1answer
121 views

Parallel Algorithms for SVD

I just have completed a preliminar theoretical study of the important SVD decomposition. Now, I'm moving to numerical calculation of SVD. I would like to learn directly a parallel algorithm to ...
0
votes
0answers
18 views

How to go from linear “equality-constrained” least squares (LSE) to linear “less-equality-constrained” LSE

I am trying to figure out how to pass from one problem to other. The linear equality-constrained least squares problem can be solved using a generalized RQ factorization (lapack solves this using ...
1
vote
4answers
151 views

How to tell if two matrices are equal up to a permutation

Given two real rectangular matrices A, B how can I tell if they are equal up to a permutation of their rows/column without trying all possible permutations? (This is closely related to the question I ...
2
votes
0answers
43 views

Find the eigenvector with maximum overlap

Given a large symmetric matrix $A$, there are methods to find the largest or smaller eigenvalue, or the eigenvalue closest to some initial value. Is there any method to find the normalized ...
0
votes
1answer
33 views

A problem in a Question paper on Linear Transformation

anyone please solve it . Let the linear transformation $T: F^2\to F^3$ be defined by $T(x_1,x_2)=(x_1,x_1+x_2,x_2)$ . Then the nullity of T is 0 1 2 3 Also please mention how it is solved
1
vote
0answers
44 views

Representation of Uncertainty in linear systems

I have a linear uncertain system represented by a family of models: $\dot{x}=A_ix$,$i=1,\cdots,N$ I want to represent the system as: $A_i=A_0+B\Delta_iC$ subject to the condition that $\lVert ...
1
vote
0answers
62 views

Algorithm to determine matrix equivalence

I'm a physicist who's not particularly good at linear algebra so please accept my apologies if this is standard textbook stuff that I'm just unaware of. I have two real rectangular matrices $A_{mxn} ...
3
votes
0answers
46 views

Conditions of a Monotonic Process?

$f$ is the output of a discrete time process described by $f(k)=\sum_{i=1}^{k-1}w_{ki}f(i)$ where $f(1)\geq0$ is a known initial condition and $w_{ki}\geq0$ are weights of previous states on the ...
1
vote
1answer
51 views

Inverse of a triangular matrix in a statistical problem

Can any one give to me idea how to solve this problem? Find the inverse of the triangular matrix T, where $ T =\left[ \begin{array}{ccc} I & J & J \\ 0 & I & J \\ 0 & 0 & I ...
0
votes
2answers
37 views

What is a good unstructured matrix solver?

If I were to hand you a general unstructured matrix A and a right hand side b, what would be your preferred iterative solver for solving Ax=b? Why?
1
vote
0answers
83 views

is it possible to generate a unique number given a set of N integers regardless of their permutation?

I need to efficiently compute an "id" for a set of N integers, the id needs to be unique if any of the numbers is different from some other set. At the same time the id needs to be the same if the ...
0
votes
0answers
23 views

Matrix conditioning with one degree of freedom

Given a not so well conditioned, NxK, N>>K matrix A with a certain structure. I have just one degree of freedom: I can multiply each row with a different factor. In formula: $$ \mathbf{B} = ...
2
votes
2answers
98 views

QR-factorization of a tridiagonal matrix super diagonals question

I understand it is possible to QR-factorize a tridiagonal matrix A by performing Given's plane rotations: $$ J(n-1,n)J(n-2,n-1)... J(1,2) A =R$$ where $R$ is upper triangular. I have read that in ...
3
votes
2answers
117 views

Singular Values of Matrix as Optimization Problem

Assume that $A$ is a positive semidefinite symmetric matrix. It is known that $$\max_{||y||\leq1} \quad y^TAy$$ Has an analytical solution which is the maximum eigenvalue of $A$. This isn't hard ...
0
votes
0answers
49 views

How can solve this differential equation (third equation )?

How can I solve this differential equation? $$ \frac{dy}{dx}=\sqrt{\frac{A}{y}+\frac{B}{y^2}+\frac{C}{y^4}+\frac{D}{y^5}+\frac{1}{(\frac{1}{y}+\frac{3}{y^2})^2}} $$ where $A,B,C,D$ are constants.
0
votes
2answers
48 views

Estimated time required to apply to matrix

I'm completely lost on this question, any help would be appreciated. Suppose the application of the Gaussian Elimination algorithm on a 50 by 50 matrix is timed at 500 μ seconds. How much time do you ...
0
votes
0answers
38 views

algorithm to separate the roots of a polynom

I need an algorithm to separate the roots of a polynom. The degree of the polynom is n (10 < n < 20) and the polynom has the same number of roots as it's degree. All roots are real. I need to ...
2
votes
2answers
50 views

Solve linear equation system $A'Ax=A'Bz$

For $A$ and $B$ known matrices which are not square matrices, I have the following equation sistem i would like to solve numerically \begin{equation} A'Ax=A'Bz \end{equation} I want to know which is a ...